2007-03-12 More About Square Roots

Another easy way to compute the square root of any number a has been introduced by Heron of Alexandria long before our time. It is an iterative method which is based on the idea that one may very well guess the result, as long as there is a way to make sure the guessing error gets smaller with every new guess.

Let x₀ be an initial guess for the square root of a, and let d₀ be the guessing error. Hence
   ( x₀ + d₀ )² = a,
and therefore
   x₀² + 2x₀d₀ + d₀² = a.
We assume that d₀ is small, and so d₀² will be much smaller than 2d₀. In fact, we assume that it is so small that we can safely ignore it.
   x₀² + 2x₀d₀ ≈ a
   ⇒ d₀ ≈ ( a - x₀² ) / 2x₀.
Now we have an approximation of the error we made in the first place. We can use this approximation to correct our first guess and start over again:
   x₁ = x₀ + d₀ = ( x₀ + a/x₀ ) / 2
The complete iteration formula reads
   x_i+1 = ( x_i + a/x_i ) / 2.
We can start off with any value x₀ ≠ 0. It's easy, isn't it?

***

Addendum:
Oh my god. Starbuck just died. Or at least her Viper exploded and she had no way to get out. There won't even be a search and rescue mission. Rumor has is she might be one of the Final Five, but Katie Sackhoff has signed an NDA, so we can only speculate. That spoiled the day for me.