Finding the square root of a number using binary search

The other day I was going through a hard drive full of homework assignments I did years ago in college.

I found one of the assignments interesting enough that I thought I would include the solution on here. The goal of the assignment was to write a function that didn't use any built in math library calls to calculate the square root of a number. 

The instructions stated that 1000 test cases would be performed, and they ALL had to pass in less than a second. In other words: the sum of all the runtimes of each of the test cases had to total less than a second -- which is pretty much to force the coder to get creative and not write a brute force solution (a bruteforce solution.. while easy to code, would perform horrendously). 

For reference, a brute force solution would look something like this:

public static double bruteForceSQRT(double num) {
    final double precision = 0.00000001D;
    double result = num;
    if (num < 1.0D) {
        if (num == 0) {
            return 0;
        } else if (num < 0) {
            // Handle these cases Like Math.sqrt() does it
            return Double.NaN;
        }
        result *= 2;
    } else {
        result /= 2;
    }
    while(result*result > num) {
        result -= precision;
    }
    return result;
}

In the brute force approach we halve the number we are given and then decrement that by a certain precision decimal value until we reach an approximated value that is extremely close to the square root of that number. Unfortunately, the greater the accuracy that you desire, the drastically slower the runtime is going to be. It took more than 2 seconds! for the bruteforce code to calculate the square root of 25 - which of course is ridiculous. 

The approach I went with for the homework assignment utilized binary search instead. Binary search provides superior performance and accuracy, and looks something like this:

public static double bin_sqrt(double num) {

double left = 0.0D, right = num;

if (num < 1.0D) {

if(num == 0) {

return 0;

}

else if (num < 0) {

// Handle these cases Like Math.sqrt() does it

return Double.NaN;

}

// If we got to here then 0 < num < 1

// so we want to actually set LEFT to num, and RIGHT to 1

// The resulting square root value will be GREATER than num

// (i.e: the square root of 0.25 is 0.50)

left = num;

right = 1.0D;

}

double middleNumber = (right + left) / 2;

double lastMiddleNumber = num;

double mSquared = middleNumber * middleNumber;

while (lastMiddleNumber != middleNumber) {

if (mSquared > num) {

right = middleNumber;

} else if (mSquared < num) {

left = middleNumber;

}

lastMiddleNumber = middleNumber;

middleNumber = (right + left) / 2;

mSquared = middleNumber * middleNumber;

}

return middleNumber;

}

The binary search method is clearly faster than the bruteforce approach - but you might be wondering -  how does it stack up against the built in Math.sqrt() function? 

Below is a table I put together which shows the results of runtimes for the binary search version (bin_srt) vs. the standard Math.sqrt();

As you might expect, Math.sqrt() in almost all cases is still significantly faster than the binary search method - sometimes almost 5 times as fast (on modern day systems, Math.sqrt() is likely to execute the square root hardware instructions directly - which is likely going to beat any homegrown software solution any day). 

Nevertheless - I could see the binary search method being useful in some niche cases: like if you can't or don't want to include a standard math library due to size constraints for a game jam, or solving an algorithm question, or, as in my original case - solving a homework problem. In those cases this is a perfectly fine solution that offers a good balance between speed, efficiency, and accuracy. 

Lastly (and arguably most importantly), this example stands as another testament to the power and efficiency of binary search and the many use cases it can be applied to.

A Java version of the binary search square root implementation can also be found on my github here: https://gist.github.com/edev90/bda51627b722a0d825453b3d797b7283