Solution to square root puzzle

SquareRootSolver.java

package square;

import java.math.BigInteger;

// Solution to square root puzzle on http://corner.squareup.com/
public class SquareRootSolver {
  // Conservative defaults for reasonable reliability.
  // Set lower for better performance.
  private static final int LOOPS = 100;
  private static final int VOTES = 4;

  // Time how long it takes to check the answer.
  // Repeat LOOP times to get a good measure
  private static long timeCheckAnswer(BigInteger guess) {
    long before = System.nanoTime();
    for (int i = 0; i < LOOPS; i++) {
      SquareRoot.answer(guess);
    }
    return System.nanoTime() - before;
  }

  // Time how long division takes, to have something to compare against
  private static long timeDivide(BigInteger answer, BigInteger guess) {
    long before = System.nanoTime();
    for (int i = 0; i < LOOPS; i++) {
      answer.divide(guess);
    }
    return System.nanoTime() - before;
  }

  // Check if a guess is probably higher or lower than SquareRoot.n.
  // Compare the time it takes to divide a bigger and smaller number by that
  // guess to how long the SquareRoot class takes to check the answer
  private static boolean isProbablyAboveN(final BigInteger guess) {
    long above = timeDivide(guess.add(BigInteger.ONE), guess);
    long below = timeDivide(guess.subtract(BigInteger.ONE), guess);
    long t = timeCheckAnswer(guess);

    return (above - t) < (t - below);
  }

  // Repeat the process a few times to make it a bit more robust
  private static boolean isAboveN(BigInteger guess) {
    int trueVotes = 0;
    for (int i = 0;; i++) {
      if (isProbablyAboveN(guess)) {
        trueVotes++;
      }
      // stop when "true" or "false" has at least VOTES votes
      if (trueVotes >= VOTES || i - trueVotes >= VOTES) {
        return trueVotes >= VOTES;
      }
    }
  }

  // Now plug that into a binary search on all squares between 0 and 2^BITS - 1
  public static void main(String[] args) {
    BigInteger min = BigInteger.ZERO;
    BigInteger max = BigInteger.valueOf(2).pow(SquareRoot.BITS)
        .subtract(BigInteger.ONE);

    while (max.compareTo(min) > 0) {
      int bitsRemaining = max.subtract(min).bitLength();
      if (bitsRemaining % 100 == 0) {
        System.out.println("bits remaining: " + bitsRemaining);
      }

      BigInteger mid = max.add(min).divide(BigInteger.valueOf(2));
      if (isAboveN(mid.multiply(mid))) {
        min = mid.add(BigInteger.ONE);
      } else {
        max = mid;
      }
    }
    SquareRoot.answer(min);
  }
}

I believe the logic in method isProbablyAboveN is incorrect - in that it's actually returning false when should be returning true. The code still works due to the logic in Main around isAboveN is also reversed. i.e. if isAboveN you would really set max = mid. I forked it and updated the logic.