计算平方根的奇怪方法

Question

有人告诉我这个代码片段等同于 (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;
}

它似乎有效，但我不明白它是如何工作的？

Answer 1

它利用了x^2 = 1 + 3 + 5 + ... + (2*x-1)这个事实。这里 i 遍历奇数， k 是它们的总和。当总和超过 n 时停止。此时i == (2*x-1) + 2其中x是平方根，所以x == floor(i/2).

Weird way of calculating square root