PulserVkinul.java

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);
    }
}