Сделать из рекурсивной функции итеративную

Question

Есть функция для нахождения символа Якоби на c++. (Не очень важная часть, но функция используют длинную арифметику написанную мной).

signed char jacobi(BigInt a, BigInt b){
    BigInt g;
    if (a >= b) a %= b;
    if (a == 0) return 0;
    if (a == 1) return 1;
    if (a < 0)
        if ((b - 1) / 2 % 2 == 0)
            return jacobi(-a, b);
        else
            return -jacobi(-a, b);
    if (a % 2 == 0)
        if (((b * b - 1) / 8) % 2 == 0)
            return +jacobi(a / 2, b);
        else
            return -jacobi(a / 2, b);
    g = gcd(a, b);

    if (g == a) 
        return 0;
    else if (g != 1)
        return jacobi(g, b) * jacobi(a / g, b);
    else if (((a - 1) * (b - 1) / 4) % 2 == 0)
        return +jacobi(b, a);
    else
        return -jacobi(b, a);
}

Тк функция рекурсивная и используются длинные числа, я думаю что нужно из рекурсивной функции сделать итеративную. Но к сожалению появились некоторые ошибки. И если можно помогите провести рефакторинг этой функции.

Answer 1

В википедии нашел псевдокод алгоритма как раз челе циклы.

Вот его реализация:

signed char jacobi(BigInt a, BigInt b){
    if (b == BigInt::BIG_ONE) return 0;
    try {
        if (b.isEven() == 1)
            throw invalid_argument("The bottom number must be odd");
    }
    catch(const invalid_argument e){
        cout << e.what() << endl;
        exit(1);
    }
    if (gcd(a, b) != 1) return 0;
    signed char res = 1;
    while (a != 0) {
        BigInt t = 0;
        while (a.isEven() == 1) {
            ++t;
            a /= 2;
        }

        uint b8 = (b % 8).getFirstBit();
        if (t.isEven() == 0)
            if (b8 == 3 || b8 == 5)
                res = -res;

        if (a % 4 == 3 && b % 4 == 3)
            res = -res;

        BigInt c = a;
        a = b % c;
        b = c;
    }
    return res;
}

БЛОГ НА HUSL

Сделать из рекурсивной функции итеративную

Ответы (1 шт):