I sometimes have quite nerdy readings. As of late, I’ve been reading Le fabuleux destin de (The Fabulous Destiny of , one might translate) by Benoît Rittaud. This book is a treasure trove of facts, and one caught my eye more than the others so far: an iterative method to compute square roots of any (positive) number.
When the method is first presented, he leaves to the reader to find a demonstration (though he gives one much later on, several chapters later), but let’s see what we can find.
The iterative method has two components. At first:
if we’re interested in finding . We then have the recurrence:
Rittaud (handwavingly) remarks that since and are always between and , they eventually converge to the same value, which turns out to be the square root of .
Let us make something that looks like a digression but really isn’t. Newton’s method for finding roots (or more exactly zeroes; the vocabulary seems to vary from author to author) of functions can be applied to the computation of , and is in fact the usual textbook example for this computation.
Newton’s method is fundamentally simple: from an initial guess for the position of the zero of the function, , we use the slope of the function at to guess where the zero might actually be. If is the function, its slope at point is denoted , and is fact its derivative at . Using a little algebra, we find that the next guess for the zero is given by:
For the square root of , we put:
which has its zero(es) at , and since it is also concave, it should behave well with Newton’s method. Replacing in Newton’s iteration, we get:
since . It can be rewritten as:
just by simplifying the original expression somewhat.
Let us compare the two methods, Newton’s and Rittaud’s (I don’t think it’s his, the text seems to indicate it was known since ancient times; but let’s call it Rittaud’s for now to distinguish it from Newton’s). Let us have a look at the following table, comparing the two methods, by iteration.
So what do we notice? That Newton’s method converges exceedingly fast? Sure. The other method converges pretty fast too. In fact… they converge at the same rate. In fact, they are the same algorithm: is the same as !
If you’re tenacious, you can unravel the expression for and see that, algebraically, it is identical to Newton’s method. So, using either Newton’s or Hero‘s method (we eventually find out that a variant of the method is due to Hero of Alexandria), we find:
and it continues to get much worse after that. We can show that the limit of the series indeed . Therefore, the recurrence presented by Rittaud, that simplifies to Hero’s method is in fact the same as Newton’s method.
As far as the number of operations is concerned (it is always important when implementing an algorithm), Newton’s (fully simpified) method is more efficient. In its simplified version, it does one addition and two divisions, one of which is the trivial division by 2. The initial recurrence with and need a lot more: three divisions plus one addition in the term, and one more division and addition in the term.
So at first, reading of this method in Rittaud’s book, it got me to think whether or not the recurrence using and would be faster or more interesting than Newton’s method. Turns out, it’s an interesting but overly complicated way of computing the same thing. Newton wins again.