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.

Advertisements

About jrh794

I am a sixty-five year old math instructor at Southern Oregon University. I taught at the College of the Siskiyous in Weed California for twenty-six years. Prior to that I worked as a computer programmer, carpenter and in various other jobs. I graduated from Rice University in 1967 and have a MS in Operations Research from Stanford. In the past I have hand-built a stone house and taken long solo bicycle tours. Now I ride my mountain bike and play golf for recreation.
This entry was posted in Math and Me, Math Explorations. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s