nth root

[MRAB]

Tim wrote:
> In PythonWin I'm running a program to find the 13th root (say) of 
> millions of hundred-digit numbers.  I'm using
>     n = 13
>     root = base**(1.0/n)
> which correctly computes the root to a large number of decimal 
> places, but therefore takes a long time.  All I need is the integer 
> component.  Is there a quicker way?
>  
Have you tried an iterative approach?

def root_13(x):
     step = 1
     while step ** 13 < x:
         step *= 2
     root = 0
     while step:
         if (root + step) ** 13 <= x:
             root += step
         step //= 2
     return root

Probably not that fast in Python, though. numpy or psyco might help.