algorithm - 编写自己的平方根函数

Question

如何编写自己的函数来找到整数的最准确平方根？

谷歌搜索后，我找到了this (从其 original link 存档)，但首先，我没有完全理解它，其次，它也是近似的。

假设平方根是最接近的整数(到实际根)或 float 。

Answer 1

以下计算 N > 0 的 floor(sqrt(N)):

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

这是 Crandall & Pomerance 中给出的牛顿方法的一个版本，“素数:计算视角”。你应该使用这个版本的原因是知道他们在做什么的人已经证明它精确地收敛到平方根的底部，而且它很简单所以实现错误的可能性很小。它也很快(尽管可以构建一个更快的算法——但正确地做到这一点要复杂得多)。对于非常小的 N，正确实现的二分搜索会更快，但您也可以使用查找表。

要舍入到最近的整数，只需使用上面的算法计算 t = floor(sqrt(4N)) 。如果设置了t的最低有效位，则选择x = (t+1)/2；否则选择 t/2。请注意，这四舍五入是平局；您还可以通过查看余数是否非零(即是否 t^2 == 4N)来向下舍入(或舍入为偶数)。

请注意，您不需要使用浮点运算。事实上，你不应该。该算法应完全使用整数来实现(特别是，floor() 函数仅指示应使用常规整数除法)。