No New Messages
author avatar
Syed Reza
1454393197513 NOTE

Square Root Estimation

Let's take a look at the intuitive first-instinct approach to computing the square root of a number $x$. Later we'll compare this against the general Newton-Raphson method.

Heron's Method

  1. Guess a solution $g$
  2. If $\frac{x}{g} = g$ then STOP, $g$ is your answer
  3. If $g$ is too high or too low, LET $g' = \frac{1}{2}(\frac{x}{g} + g)$
  4. $g'$ is your new $g$ -- GOTO Step 2

So starting with a guess, we get a better guess, and then an even better guess. With each guess better than the last, we converge onto the The Answer (plus or minus some acceptable error).

Step 2 is neat because it exploits this really nice property of the square root function. It says, if the square root of $x$ is $g$ then $\frac{x}{g}$ must be equal to $g$ -- or in other words -- $g*g$ must equal $x$ --after all that's the definition of the square root.

Step 3 is also neat; let's take a look at a property of numbers under division.

Think of a number $n$, and imagine it as a tick on a number line, now imagine another tick at $\sqrt{n}$. If it is too hard to imagine in the abstract in terms of $n$ -- that's okay, just use a real number… like 16.

Ok, imagine 16 as a tick on the number line, and imagine 4 a quarter of the distance to 16 on the same number line. Since we know that 16 divided by 4 is 4, surely 16 divided by any number greater than 4 is less than 4. And likewise, surely any number dividing 16 which is less than 4 must be greater than 4.

And so, whenever you divide a number $n$ by a number smaller than $n$, let's call this number $d$ for divisor, the result, let's call it $q$ for quotient, falls on whichever side of $\sqrt{n}$ that the dividend $d$ is not in. And if $d = \sqrt{n}$ then it must be the case that $q = \sqrt{n}$ and so $d = q = \sqrt{n}$.

The steps above work very well for this problem, but what if the problem were to be slightly altered?

General Approach With Newton-Raphson

The approach described above, known as Heron's Method or the Babylonian Method, is very neat. Unfortunately, neatness requires all of these insights that are specific to the problem, and insights require thinking and thinking is hard. If you're presented with a problem with a gun to your head and a countdown timer in the room, it's better to know the answer than to have to think about it. A general solution is like having the answer to a lot of problems, like a master key. If you're the super of a building, it's easier to carry a few master keys than to carry individual keys for each door in your building. General solutions or approaches, like master keys, are lighter and easier to carry in the pockets of your brain.

Newton's Method, or the Newton-Raphson method, is a way to generally approximate the "zeroes of a function" - the value of the inputs for which the output of the function is zero. So let's take another look at the square root problem and get it to fit this general solution.

The new original problem can be stated as follows:

Given $N$

find a number $x$ such that $N/x = x$

This may seem confusing because before we were using $x$ as our input, and $g$ as our "guess". Now we are using $x$ as our answer and $N$ as our input to the problem.

We can rephrase this as follows:

Given $N = f(x) = x^2$

Find the corresponding value of $x$

This can be further rephrased as follows:

Given some $N$ and the function below $$ f(x) = x^2 - N $$

Find a value of $x$ such that $f(x) = 0$

This is precisely what Newton's Method allows us to do, so we've managed to correctly rephrase the problem. Great, so what is Newton's method?

Newton's Method describes how to go from an initial guess of $x_0$ to a better guess, say $x_1$, and then from $x_1$ to an even better guess $x_2$, such that you are closer to $f(x_n) = 0$, where $n$ is however many times you've improved on your guess until you decide it's close enough.

$$ x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$$

The assumption and the requirement here is, of course, that $f(x)$ must be differentiable.

In our case, $f(x) = x^2 - N$ most certainly is differentiable. Simply, $f'(x) = 2x$. And so, $$x_{n+1} = x_n - \dfrac{(x_n^2 - N)}{2x_n} $$

Let us simplify.

$$ x_{n+1} = x_n - \dfrac{1}{2}x_n + \dfrac{1}{2}\dfrac{N}{x_n}$$

$$ x_{n+1} = \dfrac{1}{2}x_n + \dfrac{1}{2}\dfrac{N}{x_n}$$

Which last simplifies to:

$$x_{n+1} = \dfrac{1}{2} (x_n + \dfrac{N}{x_n})$$

Ah, so $x_{n+1}$ (the better guess) is the average of $x_n$ and $N/x_n$ -- this is exactly what is happening in Heron's method.

As you can see, Heron's Method can be derived through Newton's Method. And that I think is a nice reminder of the power of an elegant general solution.