# 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 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 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 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 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 at 20:35
show 1 more comment

## 3 Answers

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

1
oh better use a goto for the Fortran folks.... While[Abs[f[x0]] > .0001, x0 -= f[x0]/fd[x0];] – george2079 Feb 15 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 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
````

-
lang-mma
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9245907068252563, "perplexity_flag": "middle"}