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 , Newton’s method uses this iterative formula , where is the initial “guess” at the root. My idea was to come up with a formula, a ratio of two polynomials, for say, given a fixed , fixed in the sense that the same would be chosen for any . I created a function, and its seven fold iterate 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 ( and 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 would work okay. and that seven iterates is overkill.
and then I used Mathematica functions to simplify it to this 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.
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.