Nam H. Pham

Hi,

I cam across the Wikipedia page talking about methods of computing square roots (here). Very interesting.

Here is a method that Babylonian used – so simple and clear to understand.

1. Given number n

2. Roughly approximate n1 ~ √n ( worst case n1 = n)

3. Repeat this step

n2 = n1;

n1 = (n2 + n/n2) / 2;

until |n1-n2| < eps

4. Return n1;

For example: To calculate √2 . Set n1 = 3/2 which is n1 * n1 = 9/4 > 2. So n1 is a little bit larger than 2. Therefore 2/n1 will be smaller than 2. So we can conclude √2 is between (2/n1, n1). How’s about we divide this range by 2 ?

n2 = 1/2 * (n1 + 2/n1).

√2 is must be in (n2,n1) or (2/n1, n2).  There is, however, a better way to shorten the range is that √2 must be in (n2,2/n2) !!!

Why ? Because there are two possible case that n2 > √2 or n2 <= √2.

…… 2/n1 ……. 2/n2 ……….. √2 ……….. n2 ………… n1

…….2/n1………n2……………√2…………2/n2………..n1

In both case range (2/n2,n2) is clearly smaller than range with n1 or 2/n1 at one end.

Here the algorithm implemented in Java:

1
2
3
4
5
6
7
8
9

public double square(double x){
		if (x <= 0) return x; //input validation 		double x1 = 0;  		double x2 = x;//no estimation here -> a little bit slow
		eps = 0.000001;
		do{
			x1 = x2;
			x2 = 0.5*(x1+x/x1);
		} while (Math.abs(x1-x2) > eps);
		return x2;
	}