2
$\begingroup$

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?

  • 3
    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.2012-02-02

1 Answers 1

16

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