# BigInteger nth root

• 08-29-2011, 06:33 AM
BigInteger nth root
Dear Anybody!

Could someone help me! I need a function, which give back the nth root of a BigInteger. I use one, that makes the root with the newton method, but it is too slow for my algorithm. Some ideas?

Thanks!
• 08-29-2011, 09:47 AM
JosAH
Quote:

Dear Anybody!

Could someone help me! I need a function, which give back the nth root of a BigInteger. I use one, that makes the root with the newton method, but it is too slow for my algorithm. Some ideas?

Thanks!

If you apply that naive Newton (Raphson) method you're using to many calculations per step; consider the following method:

Let xl and xh be such that xl**n <= x <= xh**n (** is the power operator)
A better estimation would be (xl+xh)>>1

Continue the above steps until you have found the n-th root or xh-xl <= 1

Calculating the n-th power can be done as follows (the example uses simple ints)

Code:

```int pow(int x, int n) {   if (n == 0) return 1;   if (n == 1) return x;   int r= pow(x, n>>1);   int t= r;   if ((n&1) == 1) r*= x;   return t*r; }```
kind regards,

Jos