Существует ли функция библиотеки c ++ gmp, которая выполняет те же функции, что и функция python gmpy2 библиотеки divm (...)? - PullRequest
Новая
       122

Существует ли функция библиотеки c ++ gmp, которая выполняет те же функции, что и функция python gmpy2 библиотеки divm (...)?

0 голосов
/ 12 февраля 2020

Как и в заголовке, я пытаюсь найти функцию в библиотеке gmp C ++, которая выполняет ту же функцию, что и функция divm (...) библиотеки gmpy2 python.

Не могу представьте себе, что в gmpy2 есть этот метод, а в библиотеке gmp C ++ нет ничего, что могло бы сделать то же самое вычисление.

Если этого не существует, я был бы признателен за любой совет по созданию функции divm с нуля (все еще необходимо использовать gmp, поскольку я работаю со значениями, превышающими стандартные целые числа через mpz_class).

Спасибо!

1 Ответ

0 голосов
/ 12 февраля 2020

Исходный код C для этой функции можно найти здесь , в GMPy_MPZ_Function_Divm. Как видите, на самом деле это не взаимно-однозначное сопоставление с базовым кодом C, но когда вы убираете все элементы подсчета ссылок Python, это выглядит довольно просто c: 

// numz, denz, and modz are copies of the arguments.
// resz, gcdz ar temporaries.

if (mpz_invert(resz, denz, modz)) {    // inverse exists?
    ok = 1;
} else {                               // num, den AND mod have a gcd > 1?
    mpz_init(gcdz);
    mpz_gcd(gcdz, numz, denz);
    mpz_gcd(gcdz, gcdz, modz);
    mpz_divexact(numz, numz, gcdz);
    mpz_divexact(denz, denz, gcdz);
    mpz_divexact(modz, modz, gcdz);
    mpz_clear(gcdz);
    ok = mpz_invert(resz, denz, modz);
}
if (ok) {
    mpz_mul(resz, resz, numz);
    mpz_mod(resz, resz, modz);
    mpz_clear(numz);
    mpz_clear(denz);
    mpz_clear(modz);
    return resz;
} else {
    mpz_clear(numz);
    mpz_clear(denz);
    mpz_clear(modz);
    return NULL;
}

Математически он просто вычисляет выражение b<sup>-1</sup> * a % m для divm(a, b, m), конечно, предполагая, что это выражение допустимо (например, b не равно нулю).

...