## Square Roots – Newton’s Method Revisited

In a previous post I calculated the square root of six using  Newton’s method.   It occurred to me then that a possibly faster implementation of the process could be to do the iteration algebraically and then do a single numerical calculation.  I tried the algebraic simplification by hand but bogged down after the third step.  A CAS (Computer Algebra System) was needed.  Our department had just purchased Mathematica  and I wanted to learn how to use it.  This project was the perfect opportunity.

To find the square root of a number $a$, Newton’s method uses this iterative formula $x_{n+1}=\frac{x_n^2+a}{2x_n}$, where $x_0$ is the initial “guess” at the root.  My idea was to come up with a formula, a ratio of two polynomials, for $x_7$ say, given a fixed $x_0$, fixed in the sense that the same $x_0$ would be chosen for any $a$.  I created a function, $g(x,a)=\frac{x^2+a}{2x}$ and its seven fold iterate $g(g(g(g(g(g(g(x,a),a),a),a),a),a),a)$ and first explored what initial guess worked best.  Since I needed only to be able to calculate square roots of numbers between one and one hundred ($\sqrt{5682}=\sqrt{56.82}\sqrt{100}$ and $\sqrt{.05682}=\sqrt{5.682}\sqrt{\frac{1}{100}}$ for example), I plotted initial guess versus error  for calculating the square root of 99.  Ninety-nine was chosen since by rough fiddling I found that it seemed to be a “hard” root for Newton’s method to calculate – clearly a figment of my imagination but it would do.  Here is the plot from Mathematica. ( I haven’t  learned out to clean up Mathematica  graphs yet.)  From the plot it looks like $x_0=5$ would work okay. and that seven iterates is overkill.

I created an iterated Newton’s method function using $x_0=5$ as the initial guess and it at looked like (four iterations),

Sample Iterated Function - Four Times - Unsimplified

and then I used Mathematica functions to simplify it to this ratio of polynomials.

Sample Iterated Function - Four Times - Ratio of Polynomials

When I tried to simplify the seventh iterate, Mathematica took a long time.  By long time I  mean get the process started and go grade papers for a while.  Anyway I studied the speeds of the different expressions up to the fifth iterate.  By that time I could see what was happening.

My conclusion:  With  five as the first guess, the ratio of polynomials method reduced the calculation time by about thirty percent.  But then it dawned on me to try a simple Do loop for the iteration.  Here is the snippet of code.

Do Loop Mathematica Code

This method turned out to be twice as fast as the polynomial ration method.  Oh well another brilliant idea down the tubes.

None of the above is definitive.  Mathematica has all kinds of optimizing tricks which it employs behind the scenes.  I really need to write the code in python or some other language to really see which is fastest.  Even this would depend on how good a programmer I am.  Given the preliminary results I don’t think it will be worth my effort.  Anyway I got to play with square roots again.