Calculating 4th Roots, 5th Roots...

Date: 05/05/99 at 03:44:44
From: Mark Smith
Subject: Calculation of Roots

Is there an EASY way to calculate roots of any given depth?

For example, if I wanted to solve for this:

z = y  _______  Where: y=2 would indicate I need the Square root of X
   \  /         Where: y=3 would indicate I need the Cube root of X
    \/   X      Where: y=4 etc.....

Is there an easy way to solve for z, and is there an easy way to 
solve for X ?

Please help.

Date: 05/05/99 at 08:29:08
From: Doctor Jerry
Subject: Re: Calculation of Roots

Hi Mark,

Do you want to calculate roots by hand?  If so, then there are 
several methods.  

1. Use logs.

   z = x^{1/y}

   log(z) = (1/y)log(x)

Look up the log of x and divide by y. Then look up the antilog of the 
result. This was used in the past, before scientific calculators, 
which do the calculation using logarithms (if y = 2, they use another 
method).

2. Use Newton's method. Suppose we want a^{1/n}, where n is a positive 
integer.

Look at f(x) = x^n-a.

The x-intercept of this function, that is, where x^n-a = 0, is the 
value of x you are looking for. Let x1 be a guess of this value. 
Improvements x2,x3,... on this guess are calculated from Newton's 
formulas:

x2 = x1-(x1^n-a)/(n*x1^{n-1})

x3 = x2-(x2^n-a)/(n*x2^{n-1})

etc.

For example, suppose we want 5^{1/4}, the fourth root of 5.

Let x1 = 1.5; then
    x2 = 1.495370
    x3 = 1.495349


If you take the fourth power of x3 you'll obtain something close to 5.

- Doctor Jerry, The Math Forum
  http://mathforum.org/dr.math/   

Date: 05/05/99 at 08:56:22
From: Doctor Rob
Subject: Re: Calculation of Roots

Thanks for writing to Ask Dr. Math.

When you say "solve for z" and "solve for X," I assume from your first
paragraph that you mean find numerical values. I also assume from the
message that you want y to be an integer. The following algorithm
will find z very quickly:

   0. Pick a level of approximation you are willing to live with,
      that is, a number e > 0 such that your answer and the actual
      answer differ by less than e.
   1. Let z(0) = a first guess at the value of the root.
   2. Let n = 0.
   3. Compute z(n+1) = (1-1/y)*z(n) + (1/y)*x/z(n)^(y-1).
   4. If |z(n+1)-z(n)| < e, stop and declare that z = z(n+1).
   5. Replace n with n+1 and go to Step 3.

This is called Newton's Method, after Sir Isaac Newton. It converges
on the right answer very quickly, and more so if your guess z(0) is a
good one.

Example: Find the fifth root of 11 to 8 decimal places.

   0. e = 1/10^8
   1. z(0) = 2
   2. n = 0
   3. z(1) = (4/5)*2 + (1/5)*11/2^4 = 1.6 + 0.1375 = 1.7375
   4. |z(1)-z(0)| = 0.2625 > e
   5. n = 1
   3. z(2) = (4/5)*1.7375 + (1/5)*11/1.7375^4 = 1.631392308
   4. |z(2)-z(1)| = 0.106107692 > e
   5. n = 2
   3. z(3) = (4/5)*1.631392308 + (1/5)*11/1.631392308^4 = 1.615704970
   4. |z(3)-z(2)| = 0.015687338 > e
   5. n = 3
   3. z(4) = 1.615394386
   4. |z(4)-z(3)| = 0.000310584 > e
   5. n = 4
   3. z(5) = 1.61539426620220.
   4. |z(5)-z(4)| = 0.000000119475 > e
   5. n = 5
   3. z(6) = 1.61539426620218
   4. |z(6)-z(5)| = 0.00000000000002 < e  Stop.

The fifth root of 11 is 1.61539427 to 8 decimal places.

Now to solve for X, you have X = z^y. Since y is an integer, this is
just a matter of repeated multiplication. You can shortcut this a
little if y is of a fair size in the following way.

Compute z^2, z^4, z^8, z^16, ..., z^(2^n), where 2^n <= y < 2^(n+1).
You do this by squaring each term to get the next one. Now figure
out which of these to multiply together to get z^y = X. That is done
by figuring out how to write y as a sum of powers of 2, that is, how
to write y in base 2 (or binary).

Example: What number has 20-th root 3?

Here z = 3, y = 20. Writing y in binary, y = 10100, y = 2^4 + 2^2,
z^20 = z^16 * z^4. Then z^2 = 9, z^4 = 81, z^8 = 6561, and
z^16 = 43046721, so z^20 = 81*43046721 = 3486784401. This reduces
the calculation from y - 1 = 19 multiplications to just 5.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/