Last week I was talking with a system architect and the possibility of developing your own method to compute the square root of a double / float came up. You can find square root methods in most (never say all) computer programming languages. There might be a situation where you are not able to use it because of limited resources. My advice is to always try to use standard libraries in order to make sure you do not have to spend time developing and testing new methods (do not reinvent the wheel).
My first idea was to mimic in code how humans compute the square root of a positive real number. I did not give the idea more thought. That is; until last night. I have read several approaches but have not looked into the source code for such method. In Java in the Math library you have the sqrt() method.
I first look around on the web and decided to give a try a method that uses
an algorithm similar to a binary search.
Following is a screen capture of the console on my Eclipse IDE:
>>> val: 17
<<< val: 17.0
Step Number Low Mid High Square Result
1 17.0000 0.0000 8.5000 17.0000 72.2500 – high
2 17.0000 0.0000 4.2500 8.5000 18.0625 – high
3 17.0000 0.0000 2.1250 4.2500 4.5156 – low
4 17.0000 2.1250 3.1875 4.2500 10.1602 – low
5 17.0000 3.1875 3.7188 4.2500 13.8291 – low
6 17.0000 3.7188 3.9844 4.2500 15.8752 – low
7 17.0000 3.9844 4.1172 4.2500 16.9512 – low
8 17.0000 4.1172 4.1836 4.2500 17.5025 – high
9 17.0000 4.1172 4.1504 4.1836 17.2257 – high
10 17.0000 4.1172 4.1338 4.1504 17.0882 – high
11 17.0000 4.1172 4.1255 4.1338 17.0197 – high
12 17.0000 4.1172 4.1213 4.1255 16.9854 – low
13 17.0000 4.1213 4.1234 4.1255 17.0025 – high
14 17.0000 4.1213 4.1224 4.1234 16.9940 – low
15 17.0000 4.1224 4.1229 4.1234 16.9983 – low
16 17.0000 4.1229 4.1232 4.1234 17.0004 – high
17 17.0000 4.1229 4.1230 4.1232 16.9993 – low
18 17.0000 4.1230 4.1231 4.1232 16.9999 – low
19 17.0000 4.1231 4.1231 4.1232 17.0001 – high
20 17.0000 4.1231 4.1231 4.1231 17.0000 – low
21 17.0000 4.1231 4.1231 4.1231 17.0001 – high
<<< root: 4.12311 time: 17641392 ns
<<< root: 4.12311 time: 10587 ns
I entered 17 as a test. The value is echoed to the screen. The square root method is called. As it iterates you can see how the mid value converges into the 4.12311 solution. In my HP 50g calculator I get 4.12310562562 as a result. Based on the selected precision (you will see it in the code) the results are good.
You always need to compare results to make sure there are no issues. The following line displays the time the Math.sqrt() method took to compute the square root. Please disregard the displayed value. Java as well as many (never use the word all) other programming languages, tend to be slow when code runs for the first time in an application. Always run a test at least five times. Discard the slowest and the fastest results. Average the rest of the values.
The following screen capture illustrates the output from a modified program in order to eliminate output while the new method executes. I/O is orders of magnitude slower than the CPU.
>>> val: 17 <== number whose square root is required
<<< val: 17.0
<<< root: 4.12311 time: 49564 ns <== first (slowest) pass
<<< root: 4.12311 time: 7218 ns <== first (slowest) pass
<<< root: 4.12311 time: 4331 ns
<<< root: 4.12311 time: 0 ns
<<< root: 4.12311 time: 3849 ns <== fastest pass
<<< root: 4.12311 time: 0 ns <== fastest pass
<<< root: 4.12311 time: 4331 ns
<<< root: 4.12311 time: 481 ns
<<< root: 4.12311 time: 3850 ns
<<< root: 4.12311 time: 481 ns
In this simple test case, one can see that the new method (first results in each pass) is considerably slower than the equivalent version in the Java Math library.
Following is the test code:
package john.squareroot;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
// **** ****
final int MAX_VAL = 40;
final int TOTAL_LOOPS = 5;
// **** ****
double root;
long begin, end;
Scanner sc = new Scanner(System.in);
// **** ceiling square root ****
// for (int n = 1; n <= MAX_VAL; n++) {
// SquareRoot sr = new SquareRoot();
// int root = sr.newton(n);
// System.out.printf(“<<< n: %3d root: %2d perfect: %3s\n”, n, root, ((root * root) == n) ? “yes” : “no”);
// }
// **** ****
double val;
System.out.print(“>>> val: “);
val = sc.nextDouble();
System.out.println(“<<< val: ” + val);
SquareRoot sr = new SquareRoot();
// **** ****
for (int i = 0; i < TOTAL_LOOPS; i++) {
// **** new method ****
begin = System.nanoTime();
root = sr.sqrt(val);
end = System.nanoTime();
System.out.printf(“<<< root: %.5f time: %8d ns\n”, root, (end – begin));
// **** library method ****
begin = System.nanoTime();
root = Math.sqrt(val);
end = System.nanoTime();
System.out.printf(“<<< root: %.5f time: %8d ns\n\n”, root, (end – begin));
}
// **** ****
sc.close();
}
}
The code for the SquareRoot class follows:
package john.squareroot;
public class SquareRoot {
// **** constructor ****
public SquareRoot() {}
/**
* Integer approximation. !!! NOT USED IN THIS POST !!!
*/
public int newton(int n) {
// **** ****
if (n < 0) {
System.out.println(“newton <<< unexpected n: ” + n + ” < 0″);
throw new IllegalArgumentException(“unexpected n: ” + n + ” < 0″);
}
// **** ****
int x = Integer.SIZE;
x /= 2;
x = (int)Math.ceil(x);
x = 2 ^ x;
// **** ****
int y;
while (true) {
y = Math.floorDiv(x + Math.floorDiv(n, x), 2);
if (y >= x)
return x;
x = y;
}
}
/**
* Approximation for square root of specified number.
*/
public double sqrt(double val) {
// **** constant(s) ****
final double precision = 0.00001;
// **** ****
double low, high, mid, prevMid, midSqr = 0.0;
int step = 0;
// **** convert value to positive (just in case) ****
// val = Math.abs(val);
if (val < 0.0) {
val *= -1.0;
}
// **** initialization ****
low = 0.0;
high = mid = val;
prevMid = -1.0;
// // **** display header ****
//
// System.out.printf( “%4s %10s %10s %10s %10s %10s %s\n”,
// “Step”, “Number”, “Low”, “Mid”, “High”, “Square”, “Result”);
// **** loop until desired precision is achieved ****
while (Math.abs(prevMid – mid) > precision) {
// **** save previous mid point ****
prevMid = mid;
// **** compute current mid point ****
mid = (high + low) / 2.0;
// **** square the mid point ****
midSqr = mid * mid;
// // **** display data for this step ****
//
// System.out.printf( “%4d %10.4f %10.4f %10.4f %10.4f %10.4f “,
// ++step, val, low, mid, high, midSqr);
// **** update the high or low (as needed) ****
if (midSqr > val) {
high = mid;
// System.out.printf (“- high\n”);
} else {
low = mid;
// System.out.printf (“- low\n”);
}
}
// **** ****
return mid;
}
}
I really liked the simplicity of the approach. A similar algorithm may be used to derive values for many mathematical functions.
If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail
Follow me on Twitter: @john_canessa