Computing integer square roots in Java - follow-up

Question

(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 = 19608492647714
Number: 54383384696
Time: 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 request

Is there something I could improve? Naming/coding conventions? Performance? API design?

Answer 1

When using function parameters, use the primitive types when available:

Function<Long, Long> function

is 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.

Answer 2

You want something fast and efficient.

But did you really check what this method does :

public static long intSqrt1(long number) {
    long sqrt = 0L;

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

    return sqrt;
}

Your adding 1 to sqrt 3 times.

I don't see any reason why you should do that, but I'm guessing it's for the easy part for returning sqrt.

Let's refactor just this to a more efficient method.

First of all, a while loop where you need to count your steps, that's called a for loop.

public static long intSqrt1(long number) {
    long sqrt;
    for (sqrt = 1; (sqrt * sqrt) <= number; sqrt++) {}
    return --sqrt;
}

This method is doing all the same but I do raise the sqrt only once each time and if I return it, I will decrease it.

Now I did write some basic test, it's not a how a real performance test should be but in this case you will see the difference because it's big :

public static void main(String[] args) {
    long startTime = System.nanoTime();
    for (int i = 0; i < 10000; i++) {
        intSqrt1(902545489); // new one
    }
    long midTime = System.nanoTime();
    for (int j = 0; j < 10000; j++) {
        intSqrt2(902545489); // old one
    }
    long endTime = System.nanoTime();
    System.out.println((midTime - startTime) + " vs " + (endTime - midTime));
}

As you can see, the for I initialize 2 time a new integer and I put the new method first because we can have a delay with the startup so there could be time faults in the first method.

Still I got this as output: (I put dot's for easy reading)

175.509.799 vs 360.087.176

As you can see I halved the time.

Answer 3

Since you know Long.MAX_VALUE in advance, you can hard-code it's square root. You can then perform a binary search between 1 and this pre-computed maximum.

It will remove the questionable "exponential search".

You will then also achieve a \$\mathcal{O}(\log \sqrt{Long.MAX\_VALUE})\$ complexity, which is actually \$\mathcal{O}(1)\$ as observed by @Simon Forsberg. This means that the execution duration can be bounded by a constant time (this does not necessary means that this algorithm is the fastest).

Answer 4

For the hell of micro-benchmarking without the likes of Java Microbenchmarking Harness or jmicrobench(no idea whether this is official) (or that most visible one for those who don't have issues with empires), I tinkered around picking up ideas from rolfl and chillworld

private static void profile(UnaryLongFunc function, Random r) {
    long
        result = 0L,
        iterations = function.count,
        startTime = System.nanoTime();
    StringBuilder results = new StringBuilder(123);

    for (long i = 0; i < iterations; ++i) {
        long t = r.nextLong() % UPPER_BOUND;
        result = function.apply(t < 0 ? t + UPPER_BOUND : t);
        if (i < 7)
            results.append(", ").append(result);
    }

    long endTime = System.nanoTime();

    System.out.printf("%-12s %11.2f%s\n", function.label,
        (double)(endTime - startTime) / iterations, results);
}

// private static final int ITERATIONS = 1_000;
private static final long UPPER_BOUND = 1_000_000_000_000L;//Long.MAX_VALUE;
/** increment sqrt just once per iteration (chillworld) */
public static long intSqrt11(long number) {
    long sqrt;
    for (sqrt = 1; (sqrt * sqrt) <= number; sqrt++) {}
    return --sqrt;
}
/** source-level strength reduction */
public static long intSqrt12(long number) {
    for (long sq = 0, inc = 1 ; ; sq += inc, inc += 2)
        if (number <= sq)
            return (inc >>> 1) - 1;
}
/** int for increment & square up to Integer.MAX_VALUE */
static int SQUARE_LIMIT = (Integer.MAX_VALUE-Character.MAX_VALUE)>>>1;
public static long intSqrt13(long number) {
    int sq = 0,
        limit = (int) Math.min(SQUARE_LIMIT, number),
        inc = 1;
    while (sq < limit) {
        sq += inc;
        inc += 2;
    }
    if (number <= sq)
        return (inc >>> 1) - 1;
    long lsq = sq, linc = inc;
    while (lsq < number) {
        lsq += linc;
        linc += 2;
    }
    return (linc >>> 1) - 1;
}
/** int for increment for number below Integer.MAX_VALUE**2
 *  & for square up to Integer.MAX_VALUE */
public static long intSqrt14(long number) {
    int sq = 0,
        limit = (int) Math.min(SQUARE_LIMIT, number),
        inc = 1;
    while (sq < limit) {
        sq += inc;
        inc += 2;
    }
    if (number <= sq)
        return (inc >>> 1) - 1;
    long lsq = sq,
        longLimit = Math.min((Integer.MAX_VALUE-1L) * Integer.MAX_VALUE, number);
    while (lsq < longLimit) {
        lsq += inc;
        inc += 2;
    }
    if (number <= lsq)
        return (inc >>> 1) - 1;

    long linc = inc;
    while (lsq < number) {
        lsq += linc;
        linc += 2;
    }
    return (linc >>> 1) - 1;
}

static abstract class UnaryLongFunc { // imitates LongUnaryOperator
    final String label;
    long count;
    UnaryLongFunc(String label, long callCount) {
        this.label = label;
        count = callCount;
    }
    abstract long apply(long to);
}

static UnaryLongFunc return1;
static UnaryLongFunc []candy = {
        new UnaryLongFunc("Sqrt1", 5000) {
            @Override long apply(long to) { return intSqrt1(to); }
        },
        new UnaryLongFunc("Sqrt11", 10000) {
            @Override long apply(long to) { return intSqrt11(to); }
        },
        new UnaryLongFunc("Sqrt12", 10000) {
            @Override long apply(long to) { return intSqrt12(to); }
        },
        new UnaryLongFunc("Sqrt13", 10000) {
            @Override long apply(long to) { return intSqrt13(to); }
        },
        new UnaryLongFunc("Sqrt14", 10000) {
            @Override long apply(long to) { return intSqrt14(to); }
        },
        new UnaryLongFunc("Sqrt2", 10000) {
            @Override long apply(long to) { return intSqrt2(to); }
        },
        new UnaryLongFunc("Sqrt3", 20000000) {
            @Override long apply(long to) { return intSqrt3(to); }
        },
        new UnaryLongFunc("Sqrt4", 100000000L) {
            @Override long apply(long to) { return intSqrt4(to); }
        },
    // one call overhead less
        return1 = new UnaryLongFunc("return 1", 1) {
            @Override long apply(long to) { return 0; }
        }
    };

public static void main(String[] args) {
    long seed = System.nanoTime();

    System.out.println("Seed = " + seed);

    for (long count = 1000 ; count <= 10000000L ; count *= 10) {
        return1.count = count;
        profile(return1, new Random(seed));
    }
    System.out.println("warmup ...");
    long total = 0;
    for (int i = Integer.MAX_VALUE / 500 ; 0 <= --i ; )
        for (long l = 42 ; 0 < l ; l >>= 1)
            for (UnaryLongFunc luo: candy)
                total += luo.apply(l);
    System.out.println(total);
    System.gc();
    for (int cd = 5 ; 0 <= --cd ; )
        profile(return1, new Random(seed));
    System.out.println(total);
    for (int cc = candy.length, ulf = cc, change = -1 ; (ulf += change) < cc ; ) {
        System.gc();
        profile(candy[ulf], new Random(seed));
        if (ulf <= 0)
            change = 1;
    }
}

In my environment, warmup of the empty/non-method made a ratio in execution time of about 100:1.