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!

Quote:

---

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)

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