Create a gist now

Instantly share code, notes, and snippets.

anonymous /FindRoot.java Secret
Created Mar 21, 2013

What would you like to do?
import square.SquareRoot;
import java.math.BigInteger;
public class FindRoot {
private static final int TIME_COUNT = 100;
public static void main(String[] args) {
// The maximum number of bits in SquareRoot.n
int maxBitsInN = SquareRoot.BITS * 2;
// debugging... must make SquareRoot.n public first
// System.out.println("Number to get root of: \n" + SquareRoot.n.toString(2));
// Invariant: max >= SquareRoot.n, min < SquareRoot.n
BigInteger max = BigInteger.ONE.shiftLeft(maxBitsInN).subtract(BigInteger.ONE);
BigInteger min = BigInteger.ZERO;
// BigInteger.divide operations take *much* longer when the numerator > denominator.
// Determine the value of SquareRoot.n by calling SquareRoot.answer, and do a binary search
// using the time it takes to make the call.
while (max.compareTo(min.add(BigInteger.ONE)) > 0) {
BigInteger mid = max.add(min).shiftRight(1);
if (containsSquareRootN(max, mid)) {
// mid < SquareRoot.n
min = mid;
} else {
// mid >= SquareRoot.n
max = mid;
}
}
//System.out.println("Calculated number to get root of: \n" + max.toString(2));
// get the square root
BigInteger n = max;
max = BigInteger.ONE.shiftLeft(SquareRoot.BITS).subtract(BigInteger.ONE);
min = BigInteger.ZERO;
// invariant:
while (max.compareTo(min.add(BigInteger.ONE)) > 0) {
BigInteger mid = max.add(min).shiftRight(1);
int comp = mid.multiply(mid).compareTo(n);
if (comp < 0) {
min = mid;
} else if (comp > 0) {
max = mid;
} else {
// found!
//System.out.println("Guessed root: " + mid.toString(2));
SquareRoot.answer(mid);
return;
}
}
System.out.println("Oops... no perfect root!");
}
// determine if val1 <= SquareRoot.n <= val2
private static boolean containsSquareRootN(BigInteger val1, BigInteger val2) {
// since these timings aren't perfect, take the concensus of five rounds of speed testing
int fasterCount = 0;
if (isFaster(val1, val2)) fasterCount++;
if (isFaster(val1, val2)) fasterCount++;
if (isFaster(val1, val2)) fasterCount++;
if (isFaster(val1, val2)) fasterCount++;
if (isFaster(val1, val2)) fasterCount++;
return fasterCount >= 3;
}
// Return true if executing SquareRoot.answer(val1) is at least twice as fast as
// SquareRoot.answer(val2)
private static boolean isFaster(BigInteger val1, BigInteger val2) {
long time0 = System.nanoTime();
for (int i = 0; i < TIME_COUNT; i++) {
SquareRoot.answer(val1);
}
long time1 = System.nanoTime();
for (int i = 0; i < TIME_COUNT; i++) {
SquareRoot.answer(val2);
}
long time2 = System.nanoTime();
return (time2 - time1) > (time1 - time0) * 2;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment