A strange way to calculate the square root

Question

I was told that this piece of code is equivalent to (int)sqrt(n)

 int s(int n) { for (int i = 1, k = 0; n > 0; i += 2) { if (k + i > n) return i / 2; k += i; } return 0; } 

And it seems to work, but I don’t understand how it works?

Answer 1

He uses the fact that x^2 = 1 + 3 + 5 + ... + (2*x-1) . Here i passes odd numbers, and k is their sum. It stops when the sum is greater than n . At this moment i == (2*x-1) + 2 where x is the square root, so x == floor(i/2) .