Skip to content

Instantly share code, notes, and snippets.

@eranation
Last active December 15, 2015 08:09
Show Gist options
  • Save eranation/f5ce9a6ecc20633b8fd3 to your computer and use it in GitHub Desktop.
Save eranation/f5ce9a6ecc20633b8fd3 to your computer and use it in GitHub Desktop.
package square;
import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.Random;
/**
* A suggested solution to the puzzle by Wouter Coekaerts from Square.
* The puzzle can be found <a href="http://corner.squareup.com/2013/03/puzzle-square-root.html">here</a>
*
* @author Eran Medan
*/
public class Solution {
private static long MIN_BENCH_DURATION = 5000000000L; // in nanoseconds
// a copy of the test class, for benchmarking purposes
public static class SquareRoot2 {
public static final int BITS = SquareRoot.BITS;
// this is our copy, so we can make it public :)
public static BigInteger n = new BigInteger(BITS, new SecureRandom()).pow(2);
public static void answer(BigInteger root) {
if (n.divide(root).equals(root)) {
System.out.println("Square root!");
}
}
}
public static void main(String[] args) {
//take a number that was generated the same way the secret one was for benchmarking
BigInteger ourNumber = SquareRoot2.n;
// a number slightly below our "lab test" number
BigInteger ourNumberMinusSome = ourNumber.subtract(BigInteger.valueOf(new Random().nextInt(100)));
// a number slightly above our "lab test" number (benchmark is actually
// faster, might be surprising, but it's because BigInteger first checks if the dividend less than divisor)
BigInteger ourNumberPlusSome = ourNumber.add(BigInteger.valueOf(new Random().nextInt(100)));
System.out.println("Benchmarking");
// do a benchmark of the lower number, this should take more time as it has
// to really do the division + equals without shortcuts
double minusSomeTime = benchmarkSample(ourNumberMinusSome);
// do a benchmark of the higher number, this should take less time as as if first does a compare and skips the division)
double plusSomeTime = benchmarkSample(ourNumberPlusSome);
// the maximum number for n: (2^10000-1)^2, used as the upper bound for the
// "guess the number" search
BigInteger upperBound = BigInteger.valueOf(2).pow(SquareRoot.BITS).subtract(BigInteger.ONE).pow(2);
// the starting lower bound is 0
BigInteger lowerBound = BigInteger.valueOf(0);
long lastGCTime = System.currentTimeMillis();
while (true) {
//if we ran a bit, let's do some garbange collection and let the system do some resting in order to lessen the chance of benchmark glitches
long timeSinceLastGC = System.currentTimeMillis() - lastGCTime;
if (timeSinceLastGC > 10000) {
System.out
.println("garbage collecting, and letting the system rest a little");
System.gc();
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
lastGCTime = System.currentTimeMillis();
}
// current guess is the middle point between lower and upper bounds
BigInteger curGuess = upperBound.add(lowerBound).divide(
BigInteger.valueOf(2));
// used as a primitive "progress bar"
BigInteger upperMinusLower = upperBound.subtract(lowerBound);
System.out.println("upperMinusLower: " + upperMinusLower);
if (upperMinusLower.compareTo(BigInteger.ONE) != 1) {
// when we are converging
System.out.println("Starting to calculate square root");
BigInteger sqrt = sqrt(curGuess);
System.out.println("Calculated square root");
SquareRoot.answer(sqrt);
// in case we missed a little try to explore up and down a bit
for (int i = 0; i <= 1000; i++) {
BigInteger add = curGuess.add(BigInteger.valueOf(i));
BigInteger sub = curGuess.subtract(BigInteger.valueOf(i));
sqrt = sqrt(add);
SquareRoot.answer(sqrt);
sqrt = sqrt(sub);
SquareRoot.answer(sqrt);
}
break;
}
// first benchmark to our current guess
double time1 = benchmarkBigIntOperation(curGuess, new TestSubject() {
@Override
public void test(BigInteger guess) {
SquareRoot.answer(guess);
}
}, true);
// second benchmark to our current guess
double time2 = benchmarkBigIntOperation(curGuess, new TestSubject() {
@Override
public void test(BigInteger guess) {
SquareRoot.answer(guess);
}
}, true);
// take the average of both benchmarks (not sure why it's better than
// simply doing a longer benchmark, but it seems to have less errors)
double averageTime = (time1 + time2) / 2;
// find how far is our benchmark from each of the initial ones
double diffLess = Math.abs(averageTime - minusSomeTime);
double diffMore = Math.abs(averageTime - plusSomeTime);
// filter out noisy benchmarks
if (averageTime < plusSomeTime * 1.5) {
// if our benchmark is about or less than the time it took to divide a
// larger number (as dividing by a larger number is actually quick as it
// only compares)
// then our guess is larger than the secret number, then the upper bound
// can be set to our current guess
upperBound = curGuess;
} else if (averageTime > minusSomeTime / 1.5) {
// if our benchmark is larger than the time it took to divide a smaller
// number (as dividing by a smaller number is actually slow as it needs
// to actually do some work)
// then our guess is smaller than the secret number, therefore the lower
// bound can be set to our current guess
if (diffLess < minusSomeTime * 0.5) {
lowerBound = curGuess;
} else {
System.out.println("Not close enough, skipping");
}
} else {
System.out.println("too risky");
}
}
}
/**
* Benchmark a numbrer using our "lab" version of the SquareRoot class
*
* @param guess the number to benchmark against
* @return
*/
private static double benchmarkSample(BigInteger guess) {
double minusSomeTime = benchmarkBigIntOperation(guess, new TestSubject() {
@Override
public void test(BigInteger guess) {
SquareRoot2.answer(guess);
}
}, false);
return minusSomeTime;
}
/**
* finds a square root of a BigInteger
*
* Credit: based on a blog post from here: http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
*
* @param n the number to find the square root for
* @return the square root
*/
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8"))
.toString());
while (b.compareTo(a) >= 0) {
BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
if (mid.multiply(mid).compareTo(n) > 0)
b = mid.subtract(BigInteger.ONE);
else
a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
/**
* a helper interface for the benchmarkBigIntOperation
* used to pass a piece of code to be under benchmark against a BigInteger
*/
public static interface TestSubject {
public void test(BigInteger guess);
}
/**
* Benchmark an operation (divide in this case) on a BigInteger
*
* Credit: based on https://github.com/tbuktu/bigint/blob/master/src/main/java/DivBenchmark.java
*
* @param b the number used to test on, e.g. to execute <code>testSubject.test(b)</code>
* @param testSubject the piece of code that needs to benchmark
* @param fast if true, will perform a faster benchmark (less acurate though)
* @return
*/
private static double benchmarkBigIntOperation(BigInteger b, TestSubject testSubject, boolean fast) {
long minBenchDuration = MIN_BENCH_DURATION;
if (fast) {
minBenchDuration = minBenchDuration / 100;
}
int numIterations = 0;
long tStart = System.nanoTime();
do {
testSubject.test(b);
numIterations++;
} while (System.nanoTime() - tStart < minBenchDuration);
b = new BigInteger(b.toByteArray());
tStart = System.nanoTime();
for (int i = 0; i < numIterations; i++)
testSubject.test(b);
long tEnd = System.nanoTime();
long tNano = (tEnd - tStart + (numIterations + 1) / 2) / numIterations;
return tNano;
}
}
@eranation
Copy link
Author

I'm sure there can be better and more elegant solutions, but this one worked for me
It takes a little while to converge, but if I decrease the benchmark time for each iteration, I get occasional errors (one error is enough to miss the result) so the trade-off is between running time and chance for an error.

the minBenchDuration / 100; line can be changed to try running faster (e.g. instead of 100, try with 1000, but it might not reach the correct result)

This current implementation above took 1 hour and 14 minutes to converge on an i5, but I'm sure it can be much improved

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