Finding the square root of a random number with Newton's method, using While/Do/For loops?

Question

I am trying to construct a program that will find the square root of a number, using Newton's method, which is

$$x(n+1) = x_n- f(x) / f'(x_n)$$

The number, will be a random number, generated by: RandomInteger[{1000000, 10000000}]

I am setting the first Newton estimate to be 1, so I can iterate my loop until the difference in the estimate from Newton's method after n iterations to the first estimate of 1, being less than 0.001. Since I am trying to construct this fully, I am not using any Sqrt[x] function or $n^.5$ relationship either.

My current thoughts:

So I have set:

f[x]:=x^2 + k

where

k = RandomInteger[{1000000, 10000000}]

Since I want to know what number I am taking the SQRT of, I am Printing that information out with:

Print["The Square Root of ", k, " is ", ---]

where --- will be my program.

Since I need to take an unknown number of iterations, I am thinking of using a For loop, as that checks the loop invariant condition until it is False then stops. This is the part I am stuck on -- what I can't grasp: how do I make the loop check for a condition that is outside of the loop?

Any help or hints would be greatly appreciated.

Answer 1

If you want a more "traditional" solution, you can try a While with a Break[] (Your Fortran friends will understand this better ;)

z = 81.;  (*number to take its square root*)
f[x_] := x^2 - z;
fd[x_] := 2 x;
x0 = 1;  (*initial guess *)

While[True,
 x1 = x0 - f[x0]/fd[x0];
 If[Abs[x1 - x0] < 0.001, Break[]];
 x0 = x1
 ]

check

x1
(* 9.000000000007093`*)

Or to make it a little more robust, you always add a guard against run-away-cases and use a flag

z = 81.;  (*number to take its square root*)
f[x_] := x^2 - z;
fd[x_] := 2 x;
x0 = 1;  (*initial guess *)
maxIterations = 20;
keepSearching = True;
iter = 0;
rootWasFound = False;

While[keepSearching,
  x1 = x0 - f[x0]/fd[x0];
  If[Abs[x1 - x0] < 0.001 || iter > maxIterations,
   If[Abs[x1 - x0] < 0.001, rootWasFound = True];
   keepSearching = False
   ,
   x0 = x1;
   iter++
   ]
  ];

now

If[rootWasFound,
 Print["root ", x1, " was found in ", iter, " iterations"],
 Print["No root was found, try increasing max iterations "]
 ]

gives

 root 9. was found in 6 iterations

Answer 2

As you have defined in your question, Newton's Method gives us the next value in the iteration by following the tangent of the curve you are approximating.

Thus, we can create a function (using your f[x_, sq_] = x^2 - sq) that gives us the next x value when looking for the square root of sq.

getNext[x_, sq_] = x - f[x, sq]/D[f[x, sq], x];

(Notice I do not use delayed set so that the derivative is evaluated only once)

Now, instead of a For-loop, which usually calls for a definite number of iterations, or even a While-loop, which uses just a test as an ending condition, I recommend using NestWhile, which, appropriately, nests a function on an expression until the given test fails.

The testing function and recursive function to be nested are passed as pure functions.

sqrt[sq_, start_: 1.] := NestWhile[getNext[#, sq]&, start, Abs[f[#, sq]] > .001 &]

Answer 3

 nwt[k_, tol_: (10^-4)] := Row[{"The Square Root of ", k, " is ", 
  N@FixedPoint[(# + k/#)/2 &, 1,  SameTest -> (Abs[#1 - #2] < tol &)]}]
 nwt /@ RandomInteger[{10, 100}, {10}] // Column