Does GMPY2 (or GMP) have a pow() function?

Question

GMPY2 (or GMP) has a powmod function but I can't find anything for regular exponentiation aside from python's native pow. Does a function like this exist for mpz integers?

Guanine

gmpy2.readthedocs.org/en/latest/mpz.html powmod? – Gradate

Did you try x ** y? If anything works, it'd probably be that. – Ember

Answer 1

Just use Python's standard pow() function or the exponentiation ** operator. GMPY2's mpz type overloads all the standard special methods so you should just be able to use standard Python commands.

For example:

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

The same holds true for divmod(), etc.

Prison

Answer 2

Some performance information:

gmpy2 pow is twice as fast as python's pow, even when factoring in construction:

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

You can use the built-in pow(x,y,modulus) on an mpz, but using powmod instead is a about 10% faster.

>>> 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

The gmpy2 version is much faster than the native python with a modulus (sometimes as much as 10 times faster). Using powmod is only marginally faster than using pow/mpz, because of the construction time of the mpz.

If you already have an mpz, powmod and pow are aboslutely equivalent.

Quass

Seems that sometimes powmod could be even slower than just mpz(a) ** mpz(b). What the reason could it be for that behavior? – Bleary

gmpy2.powmod(a, b, c) is exactly what I was looking for. Thanks! – Eileen

Answer 3

Sure it does.

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)

Set rop to base raised to exp. The case 0^0 yields 1.

There is of course no mpz_pow(...) which would take two mpz_t input arguments. The reason for that is, if memory serves, because unsigned long is thought to be sufficient whereas an mpz_t e, b for b^e might very easily get out of proportion in terms of memory requirements. I can't seem to find the mailing list post that makes the claim but when I do I'll post the reference.

---

Edit: I can't seem to find a pure pow function without modular arithmetic for Python, but it may be a case of me not looking hard enough. I did however see an sqrt function which means you can implement your own pow (also this).

Boloney

Hm, does this exist in GMPY2? – Guanine