4
\$\begingroup\$

(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?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I guess you could try one of the algorithms mentioned on Wikipedia. This is probably more a mathematical problem rather than a real programming question. \$\endgroup\$
    – Marvin
    Jan 16 '16 at 15:33
  • \$\begingroup\$ Assuming you can't use Math.log or any similar function either, consider a binary search of the space [0, n/2]. This might be faster than starting with 1 and doubling as in your second approach. \$\endgroup\$
    – user1149
    Jan 16 '16 at 19:51
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ For anybody else wondering, this solution is slower than Math.sqrt by a factor of 100 for 10000000 random ints from 0 to 10000. (on my machine) \$\endgroup\$
    – findusl
    Apr 10 at 21:12
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.