Monday, 23 April 2007

square_root

these days, we are ordered to finish a simple calcuator program, everyone is wounding how java api can get sqrt so easy. so I google the web and find out some really internesting stuff. enjoy!

Square Root Approximation Library

Successive Approximation Algorithm
Successive approximation is an iterative algorithm for approximating the square root of a number. The algorithm is based on the following observations:

If x is the square root of N then,
(1) (N/x) = x so
(2) (x + (N/x)) / 2 = x.

It can be shown that if y is an approximation of the square root of N then,
(3) (y + (N/y)) / 2 is a better approximation.

Using equation (3) repeatedly allows an approximation for the square root of N to be continuously refined. The refinement of the approximation may be stopped once the difference between successive approximations is less than some threshold.

Bisection Algorithm
Bisection is another iterative process used to approximate the square root of number. The algorithm works by repeatedly reducing the range of values which the square root of a value is known to exist in. Given an initial value N and an approximate square root guess of x, the bisection algorithm is implemented using the following steps:

Step 1. Set the square root upper bound to N.
Step 2. Set the square root lower bound to 1.*
Step 3. If (x)2 is close enough to N, x is the square root. Exit.
Step 4a. If (x)2 <> N, set the upper bound to x, and let x be half way between the lower bound and the old x.
Step 5. Go to Step 3.

*NOTE: For N between 0 and 1, set the lower bound to 0 and the upper bound to 1


other reference:

Ancient Square Roots

Square root

No comments: