Computing integer square roots in Java (See the next iteration.)
There was a question in Quora about an interview question that asks to write a function for computing integer square roots, so I rolled two of them for fun:
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) &lt;= number) {
            sqrt++;
        }

        return sqrt;
    }

    public static long intSqrt2(long number) {
        if (number &lt;= 0L) {
            return 0L;
        }

        long sqrt = 1L;

        while (4 * sqrt * sqrt &lt;= number) {
            sqrt *= 2;
        }

        while ((sqrt + 1) * (sqrt + 1) &lt;= number) {
            sqrt++;
        }

        return sqrt;
    }

    public static long intSqrt3(long number) {
        return (long) Math.sqrt(number);
    }

    private static void profile(Function&lt;Long, Long&gt; function, Long number) {
        long result = 0L;
        long startTime = System.nanoTime();

        for (int i = 0; i &lt; ITERATIONS; ++i) {
            result = function.apply(number);
        }

        long endTime = System.nanoTime();

        System.out.printf(&quot;Time: %.2f, result: %d.\n&quot;, 
                          (endTime - startTime) / 1e6,
                          result);
    }

    private static final int ITERATIONS = 1000;
    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(&quot;Seed = &quot; + seed);
        System.out.println(&quot;Number: &quot; + number);

        profile(Main::intSqrt1, number);
        profile(Main::intSqrt2, number);
        profile(Main::intSqrt3, number);
    }
}

The performance figures are as follows:


Seed = 137967850680858
Number: 18973198056
Time: 278.29, result: 137743.
Time: 15.65, result: 137743.
Time: 0.38, result: 137743.


(The first time of intSqrt1, the second time of intSqrt2, and so on.)
My main question here is: is it possible to make the two methods any faster while not actually using the Math.sqrt?
I think binary search will be super fast too (without divisions):

public static long intSqrtBinarySearch(long number) {
    long l = 0L, r = Integer.MAX_VALUE;
    while (l &lt; r) {
        long mid = (l + r + 1L) / 2L; // div 2 - bitwise operation
        if (mid * mid &lt;= number) {
            l = mid;
        } else {
            r = mid - 1L;
        }
    }
    return l;
}


Also, your implementation of intSqrt2() may produce overflow error.
Test:

Failed number : 383100999
Bad answer    : 383100999
Correct       : 19572