Weird way of calculating square root [closed]

Question

I've been told this code snippet 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 seem to work, yet I don't understand how it works ?

Philomel

I'm voting to close this question as off-topic because this is a math question, not a programming question. Try math.stackexchange.com. – Pleasance

Note: code fails large n near INT_MAX. IAC, for large numbers it takes a long time to run. Faster methods exist. – Talithatalk

If you think that is weird, you should see the highly bizarre algorithms inside scientific calculators. Even after studying them for hours, there is no glimmer of how they are doing what they do! – Absher

Answer 1

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

Malaspina