Talk:Nth root algorithm
I've been playing around with finding (integer) nth roots for large n. Unfortunately, the following implementation of Newton's method (in Python) is ridiculously slow:
def nthroot(y, n):
x, xp = 1, -1
while abs(x - xp) > 1:
xp, x = x, x - x/n + y/(n * x**(n-1))
while x**n > y:
x -= 1
return x
For example, nthroot(12345678901234567890123456789012345**100,100) takes several minutes to finish.
Using binary search, the solution can be found in seconds.
Am I just doing something wrong, or is Newton's method inherently inefficient for integers and such large n? - Fredrik | talk 23:22, 24 May 2005 (UTC)
- Brief answer (let me know if you need more information): Are you sure that the standard datatype of Python can handle 125-digit integers? I think you need a special library for this. Besides, it may be necessary to start the iteration with a more sensible initial guess than x = 1 (generally, Newton's method may not converge unless the initial guess is close to the answer, but extracting N-th roots may be a special case). -- Jitse Niesen 19:39, 6 Jun 2005 (UTC)