Re: Algorithms to calculate square root (correction)
- To: mathgroup at smc.vnet.net
- Subject: [mg16515] Re: [mg16454] Algorithms to calculate square root (correction)
- From: BobHanlon at aol.com
- Date: Tue, 16 Mar 1999 03:59:58 -0500
- Sender: owner-wri-mathgroup at wolfram.com
I've added to my earlier response below a FixedPoint implementation that
automatically uses the required number of iterations.
Bob Hanlon
In a message dated 3/13/99 12:13:34 PM, ajith.pn at pcm.bosch.de writes:
>This question is about the calculation of square root using numerical
>analytical algorithms. I found the formula (from the book "Numerical
>Recipes in C - The Art of Scientific Computing" )
>
> if
> U[i+1] = 0.5 * U[i] * ( 3 - V * U[i] * U[i] )
>then U[infinity] converges quadratically to 1/sqrt(V). A final
>multiplication by V gives sqrt(V).
>
>Are there any other similar algorithm to calculate square root?
>
Ajith,
I don't have Knuth's book handy, but I believe this algorithm is in it:
For y = Sqrt[x], y[n] = (y[n-1] + x/y[n-1])/2
y[n_Integer?Positive, x_?Positive] := NestList[((# + x/#)/2.)&,x, n];
(* If you only want the final result,
use Nest vice NestList *)
y[x_?Positive] := FixedPointList[(# + x/#)/2.&, x];
(* If you only want the final result,
use FixedPoint vice FixedPointList *)
y[16]
{16, 8.5, 5.191176470588235, 4.136664722546242,
4.002257524798522, 4.000000636692939, 4.00000000000005,
4., 4.}
y[8, 16]
{16, 8.5, 5.191176470588235, 4.136664722546242,
4.002257524798522, 4.000000636692939, 4.00000000000005,
4., 4.}
Bob Hanlon