奇怪的计算平方根方法

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;
}

看起来它能够正常工作，但我不明白它是如何工作的？

- Howard Grey

---

我投票将此问题关闭，因为这是一个数学问题，而不是程序设计问题。请到math.stackexchange.com提问。 - Barmar

注意：当 n 接近 INT_MAX 时，代码会失败。无论如何，对于大数值，它需要很长时间才能运行。存在更快的方法。 - chux - Reinstate Monica

如果你觉得这很奇怪，那么你应该看看科学计算器内部高度奇异的算法。即使研究了几个小时，也没有一丝头绪它们是如何完成它们的工作的！ - wallyk

Answer 1

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

- interjay