FindRoot.java

import square.SquareRoot;

import java.math.BigInteger;

public class FindRoot {
  private static final int TIME_COUNT = 100;

  public static void main(String[] args) {
    // The maximum number of bits in SquareRoot.n
    int maxBitsInN = SquareRoot.BITS * 2;

    // debugging... must make SquareRoot.n public first
    // System.out.println("Number to get root of: \n" + SquareRoot.n.toString(2));

    // Invariant: max >= SquareRoot.n, min < SquareRoot.n
    BigInteger max = BigInteger.ONE.shiftLeft(maxBitsInN).subtract(BigInteger.ONE);
    BigInteger min = 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.
    while (max.compareTo(min.add(BigInteger.ONE)) > 0) {
      BigInteger mid = max.add(min).shiftRight(1);
      if (containsSquareRootN(max, mid)) {
        // mid < SquareRoot.n
        min = mid;
      } else {
        // mid >= SquareRoot.n
        max = mid;
      }
    }

    //System.out.println("Calculated number to get root of: \n" + max.toString(2));

    // get the square root
    BigInteger n = max;
    max = BigInteger.ONE.shiftLeft(SquareRoot.BITS).subtract(BigInteger.ONE);
    min = BigInteger.ZERO;

    // invariant:
    while (max.compareTo(min.add(BigInteger.ONE)) > 0) {
      BigInteger mid = max.add(min).shiftRight(1);
      int comp = mid.multiply(mid).compareTo(n);
      if (comp < 0) {
        min = mid;
      } else if (comp > 0) {
        max = mid;
      } else {
        // found!
        //System.out.println("Guessed root: " + mid.toString(2));
        SquareRoot.answer(mid);
        return;
      }
    }

    System.out.println("Oops... no perfect root!");
  }

  // determine if val1 <= SquareRoot.n <= val2
  private static boolean containsSquareRootN(BigInteger val1, BigInteger val2) {
    // since these timings aren't perfect, take the concensus of five rounds of speed testing
    int fasterCount = 0;
    if (isFaster(val1, val2)) fasterCount++;
    if (isFaster(val1, val2)) fasterCount++;
    if (isFaster(val1, val2)) fasterCount++;
    if (isFaster(val1, val2)) fasterCount++;
    if (isFaster(val1, val2)) fasterCount++;
    return fasterCount >= 3;
  }

  // Return true if executing SquareRoot.answer(val1) is at least twice as fast as
  // SquareRoot.answer(val2)
  private static boolean isFaster(BigInteger val1, BigInteger val2) {
    long time0 = System.nanoTime();
    for (int i = 0; i < TIME_COUNT; i++) {
      SquareRoot.answer(val1);
    }
    long time1 = System.nanoTime();
    for (int i = 0; i < TIME_COUNT; i++) {
      SquareRoot.answer(val2);
    }
    long time2 = System.nanoTime();
    return (time2 - time1) > (time1 - time0) * 2;
  }
}