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.

No comments:

Post a Comment

With great power comes great responsibility