-
-
Save benmmurphy/a8e2a9278944692016fd to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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