c++ - 不使用 sqrt 函数求平方根的底

Question

假设我有一个整数n，我想找到该数m的平方小于的最大数n。

这个问题的最佳解决方案是什么？

Answer 1

“最优解”很少存在，但一个相当快的算法如下（有人知道它的名字吗？），它被称为巴比伦方法：

int num = 4567;

int r1 = num / 2;
int r2 = 2;

while (std::abs(r2 - r1) > 1) {
     r2 = (r1 + r2) / 2;
     r1 = num / r2;
}

这里r1和r2是平方根的较低和较高的近似值。在您的情况下，您将需要较小的那个。

Answer 2

由于您只是在寻找整数部分，您可以这样做：

1. 以尽可能低的 m 开始循环，即 m=1 （除非您允许 n < 1 ）
2. 检查 m*m 是否大于 n
3. 如果不是，则需要检查下一个 m，因此将 m 加 1 并继续循环的下一个迭代
4. 如果它更大，则停止循环并从 m 中减去 1，因为 m-1 是小于 n 的平方根的最终值。

int n = 123; //or whatever you want
int m = 1;
while (m * m <= n) {
    m = m + 1;
}
return (m - 1);