**Problem:**Calculate the square root of a non-negative real number.

**Solution:**The basic idea is to start with a seed, then begin trial. If our guess (seed) is smaller, than we increase it. Otherwise, we decrease it. However, to get a good convergence speed, we need guess the square root in a smart way. The following describes Babylonian method, which is a quadratically convergent algorithm.

- Start with a seed
*x*, assume S is the real number we want to know its square root, calculate S/*x*. - Then the square root of S must be in between
*x*and S/*x*. We choose the average of*x*and S/*x*as the new guess and repeat step 1. If certain accuracy is achieved, we stop. - To select the starting seed, if S has
*d*digits and S>1, choose 2*10^((d-1)/2) if S is odd, choose 6*10^((d-2)/2) if S is even. The case for S<1 is similar.

**More:**This is actually a special case of Newton's method. Newton's method can be used to find the roots of a real value function. The basic idea is that from a point (

*x*0,

*y*0) on the curve, we draw a tangent, assume the tangent across

*x*axis at

*x*1. Assume the root is

*xr*, f(

*xr*) = 0, we have |

*x*1-

*xr*| < |

*x*0-

*xr*|. If we keep draw tangent at

*x*1, we will be even closer to

*xr*. Basically we have x_k+1 = x_k- f(x_k) / f'(x_k).6

**More more:**This method can be extended to calculate the cubic root as well. The only thing we need to change is rather than calculating the average of

*x*and S/

*x*as the new guess, we calculate the average of

*x , x*and S/

*x^2*as the new guess. Therefore,

*x*' = (2*x+S/x^2)/3.

## No comments:

## Post a Comment