Рекурсивно вычислить целое число sqrts с C - PullRequest
Новая
       65

Рекурсивно вычислить целое число sqrts с C

0 голосов
/ 20 мая 2018

Я адаптировал некоторый код Python, который нашел здесь , чтобы вычислить 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. Почему это?и как я могу это исправить?

1 Ответ

0 голосов
/ 23 мая 2018

Извините, но вам лучше использовать итеративную функцию, так как вы видите, что ваша рекурсия является окончательной рекурсией, которую можно свернуть в цикл 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)) или из-за ошибок округления пересекаются.--- это происходит с целыми числами ---

...