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)
- I thought a bit more about it now. Basically, you are right: Newton's method is inefficient for large n. There are two reasons for it. Firstly, the computation of x**(n-1) in exact arithmetics is expensive if x is a large integer, so every iteration takes a long time. Secondly, the method needs a lot of iterations. For instance, nthroot(1234567890123456789012345**10, 10) requires 4725 iterations (note that I replaced 100 in your example with 10), while a binary search requires about 100 iterations. However, the method improves if you give a good initial guess. After replacing the first line of the nthroot function with x, xp = int(y**(1.0/n)), -1, the above example gets the correct answer in only 3 iterations.
- The current article is rather bad: it only presents the algorithm, which is trivial if you know Newton's method. There is no analysis, no discussion on how to get the initial guess and no references. I am not convinced that the algorithm is used that often; I thought the common approach is to use exponential and logarithms. Bignum arithmetics is a separate issue. I hope you can find the time to improve the article. -- Jitse Niesen 23:37, 7 Jun 2005 (UTC)
- The catch with that solution is that y**(1.0/n) overflows for large y. Fortunately this can be avoided by using B**int(log(y, B)/n) with some integer B instead. However, this still leaves Newton (as implemented above) significantly slower than bsearch for very large n (a test with n=300 is nearly instantaneous with bsearch, but takes several seconds with Newton). I'll do some more detailed benchmarking when I get time, hopefully soon. For reference, I'll provide my bsearch implementation here: - Fredrik | talk 00:24, 8 Jun 2005 (UTC)
# Returns a tuple of the (floor, ceil) values of the exact solution
def nthroot_bsearch(x, n):
guess = 1 # Initial guess must be less than the result
step = 1
while 1:
w = (guess+step)**n
if w == x:
return (guess+step,) * 2
elif w < x:
step <<= 1
elif step == 1:
return guess, guess+1
else:
guess += step >> 1
step = 1
More timing results
Newton steps and time bsearch steps and time
2-root of 123^13 5 in 0.000125 s 512 in 0.002273 s
3-root of 123^13 4 in 0.000078 s 215 in 0.001215 s
15-root of 123^13 1 in 0.000054 s 0 in 0.000028 s
37-root of 123^13 185 in 0.002199 s 2 in 0.000038 s
68-root of 123^13 0 in 0.000038 s 0 in 0.000027 s
111-root of 123^13 0 in 0.000029 s 0 in 0.000021 s
150-root of 123^13 0 in 0.000028 s 0 in 0.000021 s
2-root of 123^15 5 in 0.000080 s 527 in 0.003278 s
3-root of 123^15 7 in 0.000124 s 280 in 0.001331 s
15-root of 123^15 97 in 0.001060 s 21 in 0.000137 s
37-root of 123^15 536 in 0.008385 s 5 in 0.000070 s
68-root of 123^15 0 in 0.000043 s 0 in 0.000027 s
111-root of 123^15 0 in 0.000029 s 0 in 0.000022 s
150-root of 123^15 0 in 0.000029 s 0 in 0.000021 s
2-root of 123^74 9 in 0.000194 s 14802 in 0.094982 s
3-root of 123^74 8 in 0.000213 s 5701 in 0.046656 s
15-root of 123^74 13 in 0.000266 s 251 in 0.001899 s
37-root of 123^74 679 in 0.016080 s 59 in 0.000460 s
68-root of 123^74 1471 in 0.058908 s 22 in 0.000211 s
111-root of 123^74 4564 in 0.750007 s 5 in 0.000107 s
150-root of 123^74 5358 in 1.143395 s 3 in 0.000089 s
2-root of 123^137 9 in 0.000340 s 53058 in 0.502107 s
3-root of 123^137 7 in 0.000924 s 26394 in 0.367341 s
15-root of 123^137 28 in 0.000750 s 1175 in 0.016602 s
37-root of 123^137 517 in 0.015574 s 124 in 0.001387 s
68-root of 123^137 2814 in 0.280755 s 87 in 0.000930 s
111-root of 123^137 4291 in 0.631678 s 31 in 0.000436 s
150-root of 123^137 4360 in 0.710123 s 8 in 0.000165 s
2-root of 123^150 9 in 0.000386 s 68097 in 0.705352 s
3-root of 123^150 8 in 0.001245 s 29225 in 0.449962 s
15-root of 123^150 30 in 0.001161 s 1535 in 0.021984 s
37-root of 123^150 29 in 0.000814 s 183 in 0.002368 s
68-root of 123^150 705 in 0.026171 s 74 in 0.000900 s
111-root of 123^150 2709 in 0.246143 s 25 in 0.000391 s
150-root of 123^150 13713 in 10.545980 s 21 in 0.000322 s
This clearly shows Newton being superior for small n, and bsearch superior for large n. Interesting, eh? Fredrik | talk 10:47, 25 August 2005 (UTC)