9

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?

qwr
  • 9,525
  • 5
  • 58
  • 102

3 Answers3

10

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.

casevh
  • 11,093
  • 1
  • 24
  • 35
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.

Erik Aronesty
  • 11,620
  • 5
  • 64
  • 44
  • Seems that sometimes `powmod` could be even slower than just `mpz(a) ** mpz(b)`. What the reason could it be for that behavior? – A.Ametov Jan 04 '21 at 19:57
  • `gmpy2.powmod(a, b, c)` is exactly what I was looking for. Thanks! – Arty Aug 30 '21 at 14:15
1

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

Community
  • 1
  • 1
rath
  • 3,655
  • 1
  • 40
  • 53