How does this square root approximation work?

Question

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 $\sqrt{16} = 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?

Answer 1

The differences between the successive perfect squares are 1, 3, 5, 7, 9, 11 ...

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$.