c - 用C递归计算整数sqrt

Question

我改编了一些我找到的Python代码here使用按位运算计算数字的 sqrt(如果该数字以整数形式存在)。这是我的代码。

int ft_sqrt(int nb){
    int smallcandidate;
    int largecandidate;

    if (nb < 0){
        return (0);
    }else if (nb < 2){
        return (nb);
    }else{
        smallcandidate = ft_sqrt(nb >> 2) << 1;
        largecandidate = smallcandidate + 1;

        if (largecandidate * largecandidate > nb){

            return (smallcandidate);
        }
        else{
            return (largecandidate);
        }
    }
}

这适用于我测试过的每个数字(在整数可以容纳的范围内)，除了 3。这是为什么？我该如何修复它？

Answer 1

抱歉，但是您最好使用迭代函数，因为您看到您的递归是最终递归，可以折叠为 while 循环。你的算法是:

#include <stdio.h>

unsigned isqrt(unsigned x)
{
    unsigned quot = 1, mean = x; /* isqrt must be between these two */
    /* we begin with extreme numbers and for each pair of (quot,mean),
     * the first, below the square root, and the other above, we get 
     * mean value of the two (lesser than previous) and the
     * quotient (above the prev. value, but still less than the 
     * square root, so closer to it) to get a better approach */
    while (quot < mean) {
        mean = (mean + quot) >> 1;
        quot = x / mean;
    }
    /* quot is always <= mean so finally it should be the same,
     * we can return quot or mean, indistinctly. */
    return mean;
}

int main() /* main test function, eliminate to use the above. */
{
    unsigned n;
    while (scanf("%u", &n) == 1) {
        printf("isqrt(%u) ==> %u\n", n, isqrt(n));
    }
}

编辑

该算法基于这样一个事实:几何平均值总是比算术平均值更接近 1。因此，我们取两个近似值(源数和 1，因为它们的几何平均值是平方根)，然后计算它们的算术平均值(因此获得的值介于两者之间，因此更接近几何平均值)，然后除以原始数数字乘以算术平均值，因此两个近似值都乘以原始数据(它们的几何平均值又是平方根)。由于在每个循环中算术平均值更接近几何平均值，因此商也必须如此(以及几何平均值的商)，从而导致两个数字更接近平方根。我们继续该算法，直到两个数字相等(a/sqrt(a) = sqrt(a)，并且 (sqrt(a) + sqrt(a))/2 = sqrt(a )) 或者，由于舍入误差，它们会交叉。 ---这发生在整数上 ---