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!

Printable View

- 08-29-2011, 06:33 AMadamkoeBigInteger 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 AMJosAH
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;

}

Jos