Faruk Akgul

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.

Share:Tweet

blog comments powered by Disqus