Index

Successive Approximations Examples:
Square-Root Algorithm and Kth-Root Algorithm

 

Square-Root Algorithm

You can use the square-root algorithm to compute square roots without a calculator. Find the square-root of a number N by solving the equation w2 - N = 0. Approximate solution w from estimate z with

w ~ z - F(z)/S(z) = z - (z2 - N)/(2z) = (z2 + N)/2z

Pick a perfect square near N, and use its square-root as the first estimate, z.

Example: The square-root of 130 can be approximated from estimate z = 11:

w ~ (z2 + N)/2z = [(11)2 + 130]/(2* 11) = 251/22 = 11.40909

The first approximation differs from the true square-root (11.40175) by 0.064%, which is close enough if you have no calculator. If you have a cheap calculator available, a second approximation based on the first approximation will give a better estimate:

w ~ [(11.40909)2 + 130]/(2*11.40909) = 11.40176

The second approximation differs from the true square-root by 0.00002%.

 

Kth-Root Algorithm

You can find the kth-root of N by solving the equation wk - N = 0. The approximation function is

w ~ z - (zk - N)/(kzk-1)

This approximation doesn't simplify as nicely as the square-root approximation. Approximations will converge faster if the first-estimate is larger than the solution. Therefore, pick an integer for first-estimate z, such that zk > N.

Example: To find the cube root of 40, solve the equation w3 - 40 = 0. Approximate solution w from estimate z with

w ~ z - (z3 - 40)/(3z2)

If we choose z = 4 as a first estimate, then the first approximation is

w ~ 4 - (43- 40)/(3*42) = 4 - 24/48 = 3.5

The first approximation is 2.3% greater than the true cube-root, 3.41995. If you have a cheap calculator available, you can compute another approximation:

w ~ 3.5 - (3.53- 40)/(3*3.52) = 4 - 2.875/36.75 = 3.42177

This result is only 0.05% greater than the true cube root. A third approximation returns the true cube root to 5 decimal places.

If you need to express all k roots of N in complex form, then multiply solution w by the factors

1, e2pi/k, e4pi/k, e6pi/k, ... e(2k-2)pi/k.

Note that epi = -1.

Example: The three cube roots of 27 are 3, 3e2pi/3, and 3e4pi/3.

The four 4th-roots of 16 are 2, 2epi/2, -2, and 2e3pi/2.

 

Index

URL http://members.aceweb.com/patrussell/approximations/RootAlgorithms.htm
Unpublished Work. © Copyright 2001 Pat Russell. Updated April 17, 2009.