fast square root java

fast_sqroot.java

/** Calculate the square root of a BigInteger in logarithmic time */
public BigInteger squareRoot(BigInteger x) {
      BigInteger right = x, left = BigInteger.ZERO, mid;
      while(right.subtract(left).compareTo(BigInteger.ONE) > 0) {
            mid = (right.add(left)).shiftRight(1);
            if(mid.multiply(mid).compareTo(x) > 0)
                  right = mid;
            else
                  left = mid;
      }
      return left;
}