Conference rusure::math

    
	To calculate the cube root of c:

	newguess = (2*oldguess + c/oldguess**2)/3

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

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

|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

> 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