(See the previous iteration.)My two previous methods for computing the integer square root of a number \$N\$ ran in the \$\mathcal{O}(\sqrt{N})\$ worst case time. Now I have added a method (intSqrt3) that runs in \$\mathcal{O}(\log \sqrt{N})\$ time:Main.java:import java.util.Random;import java.util.function.Function;public class Main {    public static long intSqrt1(long number) {        long sqrt = 0L;        while ((sqrt + 1) * (sqrt + 1) <= number) {            sqrt++;        }        return sqrt;    }    public static long intSqrt2(long number) {        if (number <= 0L) {            return 0L;        }        long sqrt = 1L;        while (4 * sqrt * sqrt <= number) {            sqrt *= 2;        }        while ((sqrt + 1) * (sqrt + 1) <= number) {            sqrt++;        }        return sqrt;    }    public static long intSqrt3(long number) {        if (number <= 0L) {            return 0L;        }        long sqrt = 1L;        // Do the exponential search.        while (4 * sqrt * sqrt <= number) {            sqrt *= 2;        }        long left = sqrt;        long right = 2 * sqrt;        long middle = 0;        // Do the binary search over the range that is guaranteed to contain         // the integer square root.        while (left < right) {            middle = left + (right - left) / 2;            if (middle * middle < number) {                left = middle + 1;            } else if (middle * middle > number) {                right = middle - 1;            } else {                return middle;            }        }        // Correct the binary search noise. This iterates no more than 3        // times.        long ret = middle + 1;        while (ret * ret > number) {            --ret;        }        return ret;            }    public static long intSqrt4(long number) {        return (long) Math.sqrt(number);    }    private static void profile(Function<Long, Long> function, Long number) {        long result = 0L;        long startTime = System.nanoTime();        for (int i = 0; i < ITERATIONS; ++i) {            result = function.apply(number);        }        long endTime = System.nanoTime();        System.out.printf(Time: %.2f, result: %d.\n,                           (endTime - startTime) / 1e6,                          result);    }    private static final int ITERATIONS = 1_000;    private static final long UPPER_BOUND = 1_000_000_000_000L;    public static void main(String[] args) {        long seed = System.nanoTime();        Random random = new Random(seed);        long number = Math.abs(random.nextLong()) % UPPER_BOUND;        System.out.println(Seed =  + seed);        System.out.println(Number:  + number);        profile(Main::intSqrt1, number);        profile(Main::intSqrt2, number);        profile(Main::intSqrt3, number);        profile(Main::intSqrt4, number);    }}The performance figures I get looks like this:Seed = 19608492647714Number: 54383384696Time: 531.18, result: 233202.Time: 218.41, result: 233202.Time: 1.81, result: 233202.Time: 0.43, result: 233202.Above, intSqrt3 took 1.81 milliseconds.Critique requestIs there something I could improve? Naming/coding conventions? Performance? API design?
Computing integer square roots in Java - follow-up
java;algorithm;reinventing the wheel;numerical methods
When using function parameters, use the primitive types when available:Function<Long, Long> functionis a red-flag, and should be LongUnaryOperator.Your code will spin in to an infinite loop for 25% of all long values .... anything larger than Long.MAX_VALUE/4 will cause this loop to become infinite:    // Do the exponential search.    while (4 * sqrt * sqrt <= number) {        sqrt *= 2;    }About that loop.... why do you have a magic number 4....? What does it do?This code needs more testing... and magic numbers need to be removed.