Имеет ли GMPY2 (или GMP) функцию pow()?

Question

GMPY2 (или GMP) имеет powmod функция, но я не могу найти ничего для регулярного возведения в степень кроме родного Python pow, Существует ли такая функция для mpz целые числа?

Answer 1

Просто используйте стандарт Python pow() функция или возведение в степень ** оператор. GMPY2-х mpz type перегружает все стандартные специальные методы, поэтому вы должны просто иметь возможность использовать стандартные команды Python.

Например:

>>> from gmpy2 import mpz
>>> pow(mpz(3),7)
mpz(2187)
>>> pow(mpz(3),7,13)
mpz(3)
>>> mpz(3)**7
mpz(2187)
>>> 

То же самое относится и к divmod() и т. Д.

Answer 2

Некоторая информация о производительности:

gmpy2 pow в два раза быстрее, чем в python, даже если учесть конструкцию:

>>> timeit.timeit('pow(98765, 10)', number=100000)
0.048412954514788
>>> timeit.timeit('pow(gmpy2.mpz(98765), 10)', number=100000, setup='import gmpy2')
0.024286470230094892

Вы можете использовать встроенный pow(x,y,modulus) на MPZ, но использование PowMod на 10% быстрее.

>>> timeit.timeit('pow(gmpy2.mpz(987654321),1000,100003)', 
number=100000, setup='import gmpy2')
0.057212181510976734
>>> timeit.timeit('gmpy2.powmod(987654321,1000,100003)', 
number=100000, setup='import gmpy2')
0.04513445007546579
>>> timeit.timeit('pow(987654321,1000,100003)', 
number=100000, setup='import gmpy2')
0.15511784474188062

Версия gmpy2 намного быстрее, чем собственный питон с модулем (иногда в 10 раз быстрее). Использование powmod только незначительно быстрее, чем использование pow/mpz, из-за времени создания mpz.

Если у вас уже есть mpz, powmod и pow абсолютно эквивалентны.

Answer 3

Конечно, это так.

void mpz_pow_ui (mpz_t rop, const mpz_t base, unsigned long int exp)
void mpz_ui_pow_ui (mpz_t rop, unsigned long int base, unsigned long int exp)

Установите rop на основание, поднятое до опыта. Случай 0^0 дает 1.

Там конечно нет mpz_pow(...) что заняло бы два mpz_t входные аргументы. Причина в том, что, если память не изменяет, потому что unsigned long считается достаточным, тогда как mpz_t e, b за b^e может очень легко выйти из пропорции с точки зрения требований к памяти. Кажется, я не могу найти сообщение в списке рассылки, которое предъявляет претензию, но когда я это сделаю, я опубликую ссылку.

---

Редактировать: я не могу найти чистый pow функция без модульной арифметики для Python, но это может быть случай, когда я не смотрю достаточно сложно. Однако я видел sqrt функция, которая означает, что вы можете реализовать свой собственныйpow (также это).