[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1982.0. "Algorithm for a CUBE root" by SWAM1::WOLFE_LE () Tue Jul 11 1995 06:27

    Does anyone have an algorithm for calculating a cube root.  My
    instructor says the following code can be modified from performing a
    square root function, to a cube root function with 1 line change
    
    Begin
       NewGuess:=1.0   (take a first guess)
       repeat
         OldGuess:=NewGuess
    	 NewGuess:=((Number / OldGuess) + OldGuess) / 2
       until abs (NewGuess - OldGuess) < EPSILON  (Difference is itsy-bitsy)
    
    
    This code is very elegant and simple, and each NewGuess will be closer
    to correct than the OldGuess, regardless of how far off the first guess.
    
    
    -LW
T.RTitleUserPersonal
Name
DateLines
1982.1try thisHERON::BLOMBERGTrapped inside the universeTue Jul 11 1995 08:325
    
	To calculate the cube root of c:

	newguess = (2*oldguess + c/oldguess**2)/3
1982.2Why it worksWIBBIN::NOYCEThe brakes still work on this busTue Jul 11 1995 14:4621
This technique is called Newton's method, or the Newton-Raphson method
(who was Raphson, and what did he(?) contribute?).

Given an approximation x0 to a solution to an equation f(x)=0,
find the slope of f at x0, and solve for the intersection of that line
at 0:
	x1 = x0 - f(x0)/f'(x0)

if	f(x) = x**2 - Number
then	f'(x) = 2x
so the approximation is
	x1 = x0 - (x0**2-Number)/(2*x0)
	   = x0 - x0/2 + Number/(2*x0)
	   = (x0 + Number/x0) / 2

if	f(x) = x**3 - Number
then	f'(x) = 3x**2
so the approximation is
	x1 = x0 - (x0**3-Number)/(3*x0**2)
	   = x0 - x0/3 + Number/(3*x0**2)
	   = (2*x0 + Number/x0**2) / 3
1982.3HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Tue Jul 11 1995 15:5926
How about just changing this line:

    	 NewGuess:=((Number / OldGuess) + OldGuess) / 2

to:

    	 NewGuess:=((Number / OldGuess / OldGuess) + OldGuess) / 2

In other words, we take the number and divide by the candidate cube root
twice.  If it really *was* the cube root, we'll get the candidate exactly.

For example, if number is 27 and candidate is 3, divide 27 by 3 giving 9,
then divide by 3 again, giving 3.

If we *don't* get the candidate exactly, then we'll get something that's
"on the other side".  In other words, if candidate was too large, we'll
get something too small AND VICE VERSA.

Because it's "on the other side", averaging what we get with the candidate
will produce something closer.  That's what the "+ OldGuess) / 2)" does is
AVERAGE, and hence this part works the same for square roots and cube
roots.

Thanks.

/Eric
1982.4slower but not all together wrongHDLITE::GRIESTue Jul 11 1995 16:5941
|How about just changing this line:
|
|    	 NewGuess:=((Number / OldGuess) + OldGuess) / 2
|
|to:
|
|    	 NewGuess:=((Number / OldGuess / OldGuess) + OldGuess) / 2
|

Eric this will work but will take longer to converge.

If we look at the problem like the greeks did. 

then 

cube root x = a + e where a is a guess and e is the error in that guess.

then x = (a + e)**3

or x = a**3 + 3a**2*e + 3a*e**2 + e**3

so if we divide x by a**2 we get 

x/a**2 = a + 3e + 3e**2/a + e**3/a**2

so in you "code"  a1 = (a + 3e + 3e**2/a + e**3/a**2 + a)/2

or a1 is abour a + 3/2e (assuming e smaller than a)

where as the newton code a1 is a + e + e**2/a + e**3/3a**2

The greek found root by this method (ie the "long division" method for finding roots)

ie if rem = x - a**3
      then a1 = a + rem/(3a**2)

The necessary and sufficient for this method to work is that the remainder is calculate without an error.

(note there can be an error in the rem/(3a**2) calculation)

gries
1982.5Origional Newton's methodWRKSYS::ROTHGeometry is the real life!Tue Jul 11 1995 17:2937
> This technique is called Newton's method, or the Newton-Raphson method
> (who was Raphson, and what did he(?) contribute?).

   Newton origionally described a way of approximating the roots
   of polynomials, by "shifting" the polynomial by a change of
   variable, so that the new one had a root near zero.

   Suppose he had a guess, c, for the root of

	P(x) = an x^n + ... + a1 x + a0

   He substituted x = y + c getting a P(y) with y nearly zero.

	P(y) = bn y^n + ... + b1 y + b0

   Then, since higher powers of y are going to be small, the root of
   the new polynomial is nearly

	- b0 / b1 = - P(0) / P'(0)

   and the process of shifting can be repeated.

   Raphson interpreted this in terms of derivatives.

   Shifting can be done efficiently by Horners method.  It's also a key
   idea in eigenvalue solvers such as in EISPACK.

   The reason for not using the method in .3 is that it is not
   quadratically convergent because the linear terms of the
   error don't cancel out - Newton's method squares the small
   error term each iteration, doubling the number of corrrect digits.

   This can be used for fast formal manipulation of polynomials and
   power series as well, where the number exact terms doubles
   each iteration...

   - Jim