Create a gist now

Instantly share code, notes, and snippets.

@benmmurphy /Answer.java Secret
Created Mar 20, 2013

What would you like to do?
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.
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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment