java's missing algorithm: biginteger sqrt

Aug 23, 2009

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

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