# How does this square root approximation work?

I've come across an odd way of estimating the square root of a number, going like this:

1. Given a number n,
2. Subtract the odd numbers from n in a rising order (1, 3, 5...), until $n \leq 0$
3. Count how many numbers you subtracted from n. This is the approximation of the square root.

Example:

1. $n = 16$
2. $n = (16 - 1) = 15$
3. $n = (15 - 3) = 12$
4. $n = (12 - 5) = 7$
5. $n = (7 - 7) = 0$
6. We have subtracted 4 odd numbers. Since $\sqrt16 = 4$, the approximation works.

(This script is an implementation in Python.)

However, try as I might, I can't understand why this works. Is there a good explanation available?

-
You can extend this slightly: If you were looking for $\sqrt{19}$ you could subtract the first four odd numbers leaving a remainder of $3$. The next odd number is $9$, which is too big, so your approximation would be $4\frac{3}{9}$ or about $4.33$. In fact $\sqrt{19} \approx 4.36$ so it is not a bad method. – Henry Feb 2 '12 at 13:35

Your algorithm is equivalent to summing odd numbers until the sum exceeds the input -- and it works because the sum of the first $n$ odd numbers is exactly $n^2$.