Square Root

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

Leave a Reply

Your email address will not be published. Required fields are marked *