Create a gist now

Instantly share code, notes, and snippets.

anonymous /PulserVkinul.java Secret
Created Mar 25, 2013

What would you like to do?
package square;
import java.math.BigInteger;
import java.security.SecureRandom;
/**
* You'll possibly need to tune the NUM_CYCLES value in accordance to your JVM performance
* It is highly recommended to run with -ea -Djava.compiler=NONE
* By Sergey Mkhitaryan
*/
public final class PulserVkinul {
private static final int NUM_CYCLES = 230;
private static final long BIN_SEARCH_THRESHOLD_L = 100L;
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2L);
private static final BigInteger BIN_SEARCH_THRESHOLD = BigInteger.valueOf(BIN_SEARCH_THRESHOLD_L);
private static final SecureRandom RANDOM = new SecureRandom();
private static long timeFullDivision = -1L;
public static void main(final String... args) {
final long startTime = now();
assert lessThan(BigInteger.ZERO, ONE);
timeFullDivision = calcTimeOfFullDivision();
print("timeFullDivision=" + timeFullDivision);
BigInteger right = null;
while (right == null || isLessOrEqualToAnswer(right)) {
print("trying new right...");
right = newRandomNumber(SquareRoot.BITS + 1);
}
print("right found.");
BigInteger left = null;
while (left == null || !isLessOrEqualToAnswer(left)) {
print("trying new left...");
left = newRandomNumber(SquareRoot.BITS - 1);
}
print("left found.");
binSearch(left, right);
final long spent = now() - startTime;
print("Spent " + (spent / (60L * 1000L)) + " minutes");
}
private static void binSearch(BigInteger left, BigInteger right) {
long missCounter = 0L;
while (true) {
assert lessThan(left, right);
final BigInteger diff = right.subtract(left);
print("diff [" + diff.bitLength() + "]: " + diff.toString(16));
if (!isLessOrEqualToAnswer(left)) {
print("Whoops! left seems too big");
left = left.subtract(diff.divide(TWO));
missCounter++;
continue;
}
if (isLessOrEqualToAnswer(right)) {
print("Whoops! right seems too small");
right = right.add(diff.divide(TWO));
missCounter++;
continue;
}
if (lessThan(diff, BIN_SEARCH_THRESHOLD)) {
print("Hit threshold! doing linear now.");
linearSearch(left.subtract(ONE));
break;
}
final BigInteger m = right.add(left).divide(TWO);
if (isLessOrEqualToAnswer(m)) {
left = m;
} else {
right = m;
}
}
print("Number of misses on binary search: " + missCounter);
}
private static void linearSearch(final BigInteger startWith) {
BigInteger x = startWith;
for (long l = 0L; l < BIN_SEARCH_THRESHOLD_L + 1L; l++) {
SquareRoot.answer(x);
x = x.add(ONE);
}
}
private static long calcTimeOfFullDivision() {
long sumFull = 0L;
final int n = 200;
for (int i = 0; i < n; i++) {
final long slow = timeSpent(newRandomNumber(SquareRoot.BITS - 5));
sumFull += slow;
print("time fast division=\t" + timeSpent(newRandomNumber(SquareRoot.BITS + 5)) + "\ttime slow division=\t" + slow);
}
return Math.round(0.8 * sumFull / n);
}
private static BigInteger newRandomNumber(final int bits) {
return new BigInteger(bits, RANDOM);
}
private static boolean lessThan(final BigInteger x, final BigInteger y) {
return x.compareTo(y) < 0;
}
private static boolean isLessOrEqualToAnswer(final BigInteger x) {
final long timeSpent = timeSpent(x);
final boolean less = timeSpent > timeFullDivision;
return less;
}
private static long timeSpent(BigInteger x) {
x = x.multiply(x);
for (int i = 0; i < NUM_CYCLES / 10; i++) {
SquareRoot.answer(x);
}
final long t = now();
for (int i = 0; i < NUM_CYCLES; i++) {
SquareRoot.answer(x);
}
return now() - t;
}
private static long now() {
return System.currentTimeMillis();
}
private static void print(final String s) {
System.out.println(s);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment