Computing integer square roots in Java

Question

(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) <= 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) {
        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 = 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("Seed = " + seed);
        System.out.println("Number: " + 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?

Answer 1

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 < r) {
        long mid = (l + r + 1L) / 2L; // div 2 - bitwise operation
        if (mid * mid <= 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

Answer 2

You won't get too much farther with these approaches (you can marginally improve it by multiplying by larger factors such as 100, then 10, then 5, then 2, then 1.2 etc). There are many known ways to calculate square roots of numbers numerically, one of the more famous ones being Newton's method. I've implemented it below and on my machine seems to run only twice as slowly as the native sqrt.

public static long intSqrtNewtonMethod(long number) {
    if (number <= 0L) {
        return 0L;
    }

    double sqrt = 1;

    for (int i = 0; i < 25; i++) {
        sqrt = sqrt - (sqrt * sqrt - number) / (2 * sqrt);
    }

    return (long)sqrt;
}

Firstly you will note that the result is approximate, but with double-precision (single-precision float should really not be used for this) and 25 iterations, I can't seem to find any inaccuracies. If you do find some, just add another 5 iterations and if you want to be really safe, you can fallback to your slower methods.

The key reason this is faster than your solutions is that Newton's method makes very large jumps when it is far away from the root. For example starting from 10 and searching for the root of 612 converges to 24 in only 3 iterations: 10->35.6->26.4->24.7 = 24 after truncation.