integer square root of an integer, why does this work?

Question

Good morning everyone, today I have been shown a clever way to evaluate the integer square root of an integer. Although it is indeed working I fail to understand why it works. Here' s the code:

mov output, 0
mov eax, input
mov ebx, 1
loop:
sub eax, ebx 
cmp eax, 0   
jl end      
inc output
add ebx, 2
jmp loop
end:

Now please pay attention to my question, I know how this works: it decreases the input by uneven numbers (1,3,5,7...), if the input is still >=0 it increases the output by 1 and repeats the process, else output is the integer square root of input. What I don' t know is the reason this algorithm works, I' m asking if anyone knows it.

Answer 1

To generate the sum of for i = 1 to n of (2 i - 1), reverse the numbers and add:

      1 +    3 +    5 +    7 + ... + 2n-3 + 2n-1
+  2n-1 + 2n-3 + 2n-5 + 2n-7 + ... +    3 +    1
   ----------------------------------------------
     2n +   2n +   2n +   2n + ... +   2n +   2n

= 2n^2 but since the sum was added twice divide by 2 so

The sum of for i = 1 to n of (2 i - 1) = n^2.