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

FindRoot.java

import square.SquareRoot;

import java.math.BigInteger;

public class FindRoot {
  private static final int TIMING_LOOP_COUNT = 10;

  public static void main(String[] args) {
    // max and min bound the square-root of n: min < sqrt(n) <= max
    // maxN and minN bound the square, n (i.e. SquareRoot.n): minN < n <= maxN
    BigInteger max = BigInteger.ONE.shiftLeft(SquareRoot.BITS).subtract(BigInteger.ONE);
    BigInteger maxN = max.multiply(max);
    BigInteger min = BigInteger.ZERO;
    BigInteger minN = BigInteger.ZERO;

    // BigInteger.divide operations take *much* longer when the numerator > denominator.
    // Determine the value of SquareRoot.n by calling SquareRoot.answer, and do a binary search
    // using the time it takes to make the call.
    // Keep track of the square-root along the way
    while (max.compareTo(min.add(BigInteger.ONE)) > 0) {
      BigInteger mid = max.add(min).shiftRight(1);
      BigInteger midN = mid.multiply(mid);
      if (containsSquareRootN(maxN, midN)) {
        // midN < SquareRoot.n
        min = mid;
        minN = midN;
      } else {
        // midN >= SquareRoot.n
        max = mid;
        maxN = midN;
      }
    }

    // if all went well, maxN now holds the value of SquareRoot.n, and max is the root
    SquareRoot.answer(max);
  }

  // determine if val1 <= SquareRoot.n <= val2
  private static boolean containsSquareRootN(BigInteger val1, BigInteger val2) {
    return timeForAnswerMethod(val2) > timeForAnswerMethod(val1) * 2;
  }

  // Return the execution time of the SquareRoot.answer method. Since gc pauses
  // can wreak hacov on these kinds of timings, use the minimum of several runs
  private static long timeForAnswerMethod(BigInteger val) {
    long min = Integer.MAX_VALUE;
    for (int i = 0; i < TIMING_LOOP_COUNT; i++) {
      long start = System.nanoTime();
      SquareRoot.answer(val);
      long end = System.nanoTime();
      min = Math.min(min, end - start);
    }
    return min;
  }
}

The technique also fails badly if the number is small -- BigInteger takes a shortcut if the magnitude is small enough to do ordinary integer division, so if the square is less than 2^31 this will either guess a much larger number, or 1.