user6302469 user6302469 - 1 year ago 60
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

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
root of large number in android programmatically?

Answer Source

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