在不使用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是平方根的较低和较高的近似.在你的情况下,你需要较小的一个.