1. Member Join Date
Aug 2011
Posts
1
Rep Power
0

## 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!  Reply With Quote

2. ##  Originally Posted by adamkoe 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)

Java 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
Last edited by JosAH; 08-29-2011 at 10:24 AM. Reason: typo ...  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•