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;
  }
}

I ran it, it does not work. I tried 10 times or so.

With some debug printing, it is close (the most significant 100 digits or so match), but off.

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.