## 28/10/2013

### [Java] BigInteger square root

Recently I was following a cryptography course and one assignment required us to compute square roots of very huge numbers. In Java, you require a BigInteger object to correctly represent numbers bigger than 231-1 (Integer max size).

Those BigInteger objects come with the basic operations implemented (addition, subtraction, multiplication and division) plus some other useful ones (exponentiation and modulus for example) but lack a method to compute the square root and it's highly unlikely that it will be added in the future[citation needed]. The only solution is either to implement your own method or find a reliable library.
Scouring the internet, I found a fast and reliable method which computes the square root of a given BigInteger and returns it floored (remember: floor of a number with no decimal part is the same number!):

`````` //compute the square root of a BigInteger. If it's not a perfect square, returns floor(sqrt)
static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
while(b.compareTo(a) >= 0) {
BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
else a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
``````

In case you needed a ceil instead of a floor, you can add 1 (BigInteger.ONE) to the returned value after checking if the method indeed returned something which wasn't a perfect square with divideAndRemainder; which will return an array of BigIntegers with the remainder in the second position; if it's not zero, then you may proceed in adding one.

#### Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.