Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Solution to square root puzzle
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment