squareup solution: http://corner.squareup.com/2013/03/puzzle-square-root.html somewhat unreliable :( and very slow. accuracy can be improved by doing more timeAnswer calls in accurateTimeAnswer method. increasing N can also improve accuracy but can also increase chance of GC during a timing and thus reduce accuracy.

Answer.java

package square;

// N or the number of trials to perform in accurateTimeAnswer may need tweaking
// depending on the speed of the machine :)


import java.math.*;

public class Answer {
  static final int N = 1000;

  static double THRESHOLD = 0.0;

  public static BigInteger binarysearch(BigInteger min, BigInteger max) {

    while (!min.equals(max)) {
      
      // uncomment + make n public for finding out when it goes wrong :)

      /*if (SquareRoot.n.compareTo(min) < 0 || SquareRoot.n.compareTo(max) > 0) {
        System.out.println("fucked up!");
        System.exit(1);
      }*/

      BigInteger guess = min.add(max).divide(BigInteger.valueOf(2));

      System.out.println("bounds: " + max.subtract(min).bitCount());



      if (isGreaterThanOrEqual(guess)) {
        System.out.println("guess is greater or equal");
        max = guess;
      } else {
        System.out.println("guess is less");
        min = guess.add(BigInteger.ONE);
      }
    }

    return min;

  }

  public static boolean isGreaterThanOrEqual(BigInteger root) {
    double time = accurateTimeAnswer(root);

    System.out.println("time: " + time);
    return time < THRESHOLD;
  }

  static BigInteger dummy;

  public static void dummyAnswer(BigInteger root) {
    if (dummy.divide(root).equals(root)) {
      System.out.println("DUMMY");
    }
  }


  public static long accurateTimeAnswer(BigInteger root) {
    return Math.min(timeAnswer(root), Math.min(timeAnswer(root), Math.min(timeAnswer(root), timeAnswer(root))));
  }

  public static long accurateTimeDummyAnswer(BigInteger root) {
    return Math.min(timeDummyAnswer(root), Math.min(timeDummyAnswer(root), Math.min(timeDummyAnswer(root), timeDummyAnswer(root))));
  }


  public static long timeAnswer(BigInteger root) {
    long start = System.currentTimeMillis();

    for (int i = 0; i < N; ++i) {
      SquareRoot.answer(root);
    }

    long duration = System.currentTimeMillis() - start;

    return duration;
  }

  public static long timeDummyAnswer(BigInteger root) {
    long start = System.currentTimeMillis();

    for (int i = 0; i < N; ++i) {
      dummyAnswer(root);
    }

    long duration = System.currentTimeMillis() - start;

    return duration;
  }

  public static BigInteger squareRoot(BigInteger x) {
      if (x.compareTo(BigInteger.ZERO) < 0) {
          throw new IllegalArgumentException("Negative argument.");
      }

      if (x == BigInteger.ZERO || x == BigInteger.ONE) {
          return x;
      } 

      BigInteger two = BigInteger.valueOf(2L);
      BigInteger y;
      for (y = x.divide(two);
              y.compareTo(x.divide(y)) > 0;
              y = ((x.divide(y)).add(y)).divide(two));
      return y;
  }


  public static void main(String[] args) {

    dummy = BigInteger.valueOf(2).pow(20000);

    System.out.println("dummy bitcount: " + dummy.bitLength());

    long warm = 0;
    for (int i = 0; i < 10; ++i) {
      warm += accurateTimeAnswer(dummy.add(BigInteger.ONE));
      warm += accurateTimeDummyAnswer(dummy.subtract(BigInteger.ONE));
      warm += accurateTimeDummyAnswer(dummy.add(BigInteger.ONE));
    }

    System.out.println("warm: " + warm);

    double small = accurateTimeDummyAnswer(dummy.add(BigInteger.ONE));

    double large = accurateTimeDummyAnswer(dummy.subtract(BigInteger.ONE));

    THRESHOLD = (0.5 * small + 0.5 * large);

    System.out.println(small + "/" +  large + "/" + THRESHOLD);

    BigInteger result = binarysearch(BigInteger.ONE,  BigInteger.valueOf(2).pow(10001).pow(2));
    System.out.println(result);
    System.out.println("calculating result...");
    SquareRoot.answer(squareRoot(result));
  }
}