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

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.

-
It's wholly unclear what you are asking -- what is it "outside the loop" that you need to check? Also, what's the role of your function f: what does this have to do with your question? In order to find x for which x^2 == k, you want equivalently x^2 - k == 0, so the function to iterate is f[x_] := x^2 - k. (And you have the syntax for defining f wrong: you missed the pattern character _ in the left-hand side.) –  murray Feb 15 '13 at 19:50
Why do you want to use a For loop? You can just use Nest or NestWhile, or if you want to see all the iterates, NestList or NestWhileList. Or is this homework exercise where somebody is forcing you to use explicitly a For loop? If so, you cannot expect us to do your homework for you; at the very least you need to show us the code you already have for the iteration with For. –  murray Feb 15 '13 at 19:52
@murray my initial understanding of Newton's Method was poor, I am correcting my attempts with the suggestions you made, thank you. (The syntax was wrong due to a missed typing error when I was trying to format correctly, I apologize) Also, I don't "need" to use all of those loops, those are just the ones at my disposal at this point, so I was wondering any combination/use of any of them. –  julesverne Feb 15 '13 at 19:54
The way the question stands, you are asking for us to create a Newton's Method algorithm using "Do/While/For" loops. However, it is much more functional and cogent to utilize the recursive elements of the function with NestWhile. Unless your aim really is to use only those three looping functions, could you please edit your question to be less specific about which functions to use? –  VF1 Feb 15 '13 at 19:58
One of the "Applications" given in the help for Nest shows how to perform a fixed number of Newton-Raphson iterations to find $\sqrt{2}$. Use NestWhile, as suggested by @Murray, to make this more flexible. NestWhileList will return the intermediate results. –  whuber Feb 15 '13 at 20:35

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

-
oh better use a goto for the Fortran folks.... While[Abs[f[x0]] > .0001, x0 -= f[x0]/fd[x0];] –  george2079 Feb 15 '13 at 20:16
superb, thank you. I was wondering at first about the break as well, and ended up finishing it within the If –  julesverne Feb 15 '13 at 22:17

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 &]

-
 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
`

-