user6302469 - 1 year ago 99
Java Question

# how to calculate nth root of large and long number in android programmatically?

I am developing a simple android app and trying to get

`nth`
root of a large and long number programmatically.
I have searched many links here , but I haven't found a correct solution in android.

How can I get
`nth`
root of large number in android programmatically?

You can use `bitLength` to compute the number of bits of your number. If the bit length is k, then your number x is 2k-1 ≤ x < 2k. So 2k/n will be a reasonable upper bound for your n-th root. Hence your solution will have no more than m = ⌈k/n⌉ bits (or `m = (k - 1)/n + 1` in integer arithmetic).

Now iterate over each of these m bits, starting with the bit of highest value (position m-1 and value 2m-1). For each bit, decide whether it has to be set or not. Which means take the number you had before (initially zero), set the bit at the given position. Compute the n-th power of that (using the `BigInteger.pow` method, or perhaps using repeated squaring if someone reading this is using a different big integer implementation). If the result is bigger than your input x, then clear the bit again, otherwise, leave the bit set. Continue to the next bit, until you either found an exact match or have decided on the last bit and thus found the floor of the actual non-integer root.

I don't say that this algorithm is optimal, but it should be feasible for many applications, and reasonably easy to understand and implement as well.

Here is some working code:

``````BigInteger root(int n, BigInteger x) {
BigInteger y = BigInteger.ZERO;
for (int m = (x.bitLength() - 1)/n; m >= 0; --m) {
BigInteger z = y.setBit(m);
int cmp = z.pow(n).compareTo(x);
if (cmp == 0) return z; // found exact root
if (cmp < 0) y = z;     // keep bit set
}
return y; // return floor of exact root
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download