user6302469 - 6 months ago 35

Java Question

I am developing a simple android app and trying to get

`nth`

I have searched many links here , but I haven't found a correct solution in android.

How can I get

`nth`

Answer

You can use `bitLength`

to compute the number of bits of your number. If the bit length is *k*, then your number *x* is 2^{k-1} ≤ x < 2^{k}. So 2^{⌈k/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 2^{m-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
}
```