# Java's Missing Algorithm: BigInteger Sqrt

August 22, 2009 | View Comments

Java's BigInteger and BigDecimal libraries don't contain an algorithm to find the root of a number so you have to develop your own. I've coded a square root algorithm for BigInteger library (I can't remember how I've learned the original algorithm. If I do, I'll add it). Feel free to use it, but remember it only finds square roots of a number.

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); }

Here's an example usage:

BigInteger n = new BigInteger("34598734524213124593869456843967349872984172392043275489357439720358723"); BigInteger temp = new BigInteger(sqrt(n).toString()); System.out.println(temp.toString());

I've implemented as an "integer" type on purpose. you can easily change type to "decimal" if you want to.