Calculate Square Root and Cubic Root

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.

1. Start with a seed x, assume S is the real number we want to know its square root, calculate S/x. 
2. 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.
3. 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 (x0, y0) on the curve, we draw a tangent, assume the tangent across x axis at x1. Assume the root is xr, f(xr) = 0, we have |x1-xr| < |x0-xr|. If we keep draw tangent at x1, 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.