Square-Root Algorithm and Kth-Root Algorithm

w ~ z - F(z)/S(z) = z - (z^{2} - N)/(2z) = (z^{2} + 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 ~ (z^{2} + 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%.

You can find the *k*^{th}-root of N by solving the equation ^{k} - N = 0.

w ~ z - (z^{k} - N)/(*k*z^{k-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 ^{k} > N.

Example: To find the cube root of 40, solve the equation ^{3} - 40 = 0.

w ~ z - (z^{3} - 40)/(3z^{2})

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

w ~ 4 - (4^{3}- 40)/(3*4^{2}) = 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.5^{3}- 40)/(3*3.5^{2}) = 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, e^{2pi/k}, e^{4pi/k}, e^{6pi/k}, ... e^{(2k-2)pi/k}.

Note that e^{pi} = -1.

Example: The three cube roots of 27 are 3, 3e^{2pi/3}, and 3e^{4pi/3}.

The four 4^{th}-roots of 16 are 2, 2e^{pi/2}, -2, and 2e^{3pi/2}.

URL http://members.aceweb.com/patrussell/approximations/RootAlgorithms.htm

Unpublished Work. © Copyright 2001 Pat Russell. Updated April 17, 2009.