How can I find the Square Root of a Java BigInteger?

Solution 1:

Just for fun:

public static BigInteger sqrt(BigInteger x) {
    BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
    BigInteger div2 = div;
    // Loop until we hit the same value twice in a row, or wind
    // up alternating.
    for(;;) {
        BigInteger y = div.add(x.divide(div)).shiftRight(1);
        if (y.equals(div) || y.equals(div2))
            return y;
        div2 = div;
        div = y;
    }
}

Solution 2:

I know of no library solution for your question. You'll have to import an external library solution from somewhere. What I give you below is less complicated than getting an external library.

You can create your own external library solution in a class with two static methods as shown below and add that to your collection of external libraries. The methods don't need to be instance methods and so they are static and, conveniently, you don't have to instance the class to use them. The norm for integer square roots is a floor value (i.e. the largest integer less than or equal to the square root), so you may need only the one static method, the floor method, in the class below for the floor value and can choose to ignore the ceiling (i.e. the smallest integer greater than or equal to the square root) method version. Right now, they are in the default package, but you can add a package statement to put them in whatever package you find convenient.

The methods are dirt simple and the iterations converge to the closest integer answer very, very fast. They throw an IllegalArgumentException if you try to give them a negative argument. You can change the exception to another one, but you must ensure that a negatve argument throws some kind of exception or at least doesn't attempt the computation. Integer square roots of negative numbers don't exist since we are not in the realm of imaginary numbers.

These come from very well known simple iterative integer square root algorithms that have been used in hand computations for centuries. It works by averaging an overestimate and underestimate to converge to a better estimate. This may be repeated until the estimate is as close as is desired.

They are based on y1 = ((x/y0) + y0) / 2 converging to the largest integer, yn, where yn * yn <= x.

This will give you a floor value for a BigInteger square root, y, of x where y * y <= x and (y + 1) * (y + 1) > x.

An adaptation can give you a ceiling value for BigInteger square root, y, of x where y * y >= x and (y - 1) * (y - 1) < x

Both methods have been tested and work. They are here:

import java.math.BigInteger;

public class BigIntSqRoot {

public static BigInteger bigIntSqRootFloor(BigInteger x)
        throws IllegalArgumentException {
    if (x.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("Negative argument.");
    }
    // square roots of 0 and 1 are trivial and
    // y == 0 will cause a divide-by-zero exception
    if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
        return x;
    } // end if
    BigInteger two = BigInteger.valueOf(2L);
    BigInteger y;
    // starting with y = x / 2 avoids magnitude issues with x squared
    for (y = x.divide(two);
            y.compareTo(x.divide(y)) > 0;
            y = ((x.divide(y)).add(y)).divide(two));
    return y;
} // end bigIntSqRootFloor

public static BigInteger bigIntSqRootCeil(BigInteger x)
        throws IllegalArgumentException {
    if (x.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("Negative argument.");
    }
    // square roots of 0 and 1 are trivial and
    // y == 0 will cause a divide-by-zero exception
    if (x == BigInteger.ZERO || x == BigInteger.ONE) {
        return x;
    } // end if
    BigInteger two = BigInteger.valueOf(2L);
    BigInteger y;
    // starting with y = x / 2 avoids magnitude issues with x squared
    for (y = x.divide(two);
            y.compareTo(x.divide(y)) > 0;
            y = ((x.divide(y)).add(y)).divide(two));
    if (x.compareTo(y.multiply(y)) == 0) {
        return y;
    } else {
        return y.add(BigInteger.ONE);
    }
} // end bigIntSqRootCeil
} // end class bigIntSqRoot

Solution 3:

Strange that nobody has mentioned it earlier but in java 9 you have sqrt in BigInteger, so you can just use it like that:

BigInteger nine = BigInteger.valueOf(9);
BigInteger three = nine.sqrt();

https://docs.oracle.com/javase/9/docs/api/java/math/BigInteger.html#sqrt--

EDIT-1

Adding that there is another flavour of this function that, in addition to the floored square root, also returns the remainder.

sqrtAndRemainder() BigInteger[]

Returns an array of two BigIntegers containing the integer square root s
of this and its remainder this - s*s, respectively.

Solution 4:

I can't verify the accuracy of them but there are several home grown solutions when googling. The best of them seemed to be this one: http://www.merriampark.com/bigsqrt.htm

Also try the Apache commons Math project (once Apache recovers from its bombardment after the JCP blog post).

Solution 5:

As Jigar states, Newton's iteration is both quite simple to understand and to implement. I'll leave it up to others decide whether it is the most efficient algorithm or not for finding the square root of a number.

With recursion it can be done in just about two lines.

private static BigInteger newtonIteration(BigInteger n, BigInteger x0)
{
    final BigInteger x1 = n.divide(x0).add(x0).shiftRight(1);
    return x0.equals(x1)||x0.equals(x1.subtract(BigInteger.ONE)) ? x0 : newtonIteration(n, x1);
}

Where n is the number we want to find the square root of, and x0 is the number from the previous call, which will always be 1 when initiate the first call from another method. So preferably, you will complement it with something like this as well;

public static BigInteger sqrt(final BigInteger number)
{
    if(number.signum() == -1)
        throw new ArithmeticException("We can only calculate the square root of positive numbers.");
    return newtonIteration(number, BigInteger.ONE);
}