A solution to http://corner.squareup.com/2013/03/puzzle-square-root.html...

FindSquareRoot.java

import square.SquareRoot;
import java.security.SecureRandom;
import java.math.BigInteger;
import java.math.BigDecimal;

public class FindSquareRoot {
    public static SquareRoot sr = new SquareRoot();
    
    public static long timeAnswer(BigInteger ans) {
        long startTime = System.nanoTime();
        for (int i=0;i<500;i++) // Enough reps to smooth out transients
            sr.answer(ans);
        return System.nanoTime() - startTime;
    }
    
    // Square Root function from http://www.java-examples.com/find-square-root-biginteger-example
    // Based on Newton's method
    public static BigInteger sqrt(BigInteger n) {
        int firsttime = 0;      
        BigDecimal myNumber = new BigDecimal(n);
        BigDecimal g = new BigDecimal("1");
        BigDecimal my2 = new BigDecimal("2");
        BigDecimal epsilon = new BigDecimal("0.0000000001");

        BigDecimal nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);
       
        //Get the value of n/g
        BigDecimal nBygPlusg = nByg.add(g);
       
        //Get the value of n/g + g
        BigDecimal nBygPlusgHalf = nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);
       
        //Get the value of (n/g + g)/2
        BigDecimal saveg = nBygPlusgHalf;
        firsttime = 99;
       
        do {
            g = nBygPlusgHalf;
            nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);
            nBygPlusg = nByg.add(g);
            nBygPlusgHalf = nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);
            BigDecimal savegdiff  = saveg.subtract(nBygPlusgHalf);
               
            if (savegdiff.compareTo(epsilon) == -1) {
                firsttime = 0;
            }
            else {
                saveg = nBygPlusgHalf;
            }   
        } while (firsttime > 1);
   
        return saveg.toBigInteger();
    }
    
    public static void main(String[] args) {
        BigInteger upper = BigInteger.ONE.shiftLeft(SquareRoot.BITS*2+1); // surely larger than the root squared
        BigInteger lower = BigInteger.ONE;
        
        // OBS: BigInteger.divide() is much faster if divisor > dividend (quotient = 0)... make this the baseline
        long fastDivideThresh = timeAnswer(upper) * 2;
        System.out.println("time thresh: " + new Long(fastDivideThresh).toString());
        
        // Bisect space to find root^2...
        do {
            BigInteger midpt = upper.subtract(lower).shiftRight(1).add(lower);
            if (timeAnswer(midpt) <= fastDivideThresh) {
                upper = midpt;
            }
            else {
                lower = midpt;
            }
        } while (upper.subtract(lower).compareTo(BigInteger.ONE) == 1);
        System.out.println("Bisection done.");

        // Figure out root
        BigInteger root = sqrt(upper);
        System.out.println("Root calculated.");

        // Try answer...
        sr.answer(root);
    }
}