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**