计算平方根的奇怪方法

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