0

I wrote the following modulo exponentiation. But I am not sure if I will loose precision when converting from MPZ type to long. 

def mypowmod(base, power, modulus):
    base = gmpy.mpz(base)
    power = gmpy.mpz(power)
    modulus = gmpy.mpz(modulus)
    result = pow(base, power, modulus)
    return long(result)
jfs
  • 399,953
  • 195
  • 994
  • 1,670
drdot
  • 3,215
  • 9
  • 46
  • 81
  • Your function is better written as `mypowmod = pow`. – Dan D. Feb 15 '15 at 06:44
  • @DanD. what do you mean? – drdot Feb 15 '15 at 06:46
  • unrelated: if the result has many digits and you want to get a decimal representation (string) then don't convert to `long` and [leave `gmpy2.mpz` as is — `str(mpz)` is *much* faster than `str(long)`](http://stackoverflow.com/a/28480239/4279). – jfs Feb 15 '15 at 08:36

2 Answers2

3

Disclaimer: I am the maintainer of gmpy and gmpy2.

The Python long type is arbitrary precision. Conversion to/from long and mpz are always exact.

Since long is arbitrary precision, the built-in pow() function will calculate the correct result without requiring the use of gmpy or gmpy2. However, using the mpz type will be much faster. A quick test shows that it is faster even for number of only 10 digits.

$ python -m timeit -s "import gmpy;a=10;b=gmpy.mpz('1'*a);p=gmpy.mpz('2'*a)-7;m=gmpy.mpz('3'*a)+11" "pow(b,p,m)"
1000000 loops, best of 3: 1.41 usec per loop
$ python -m timeit -s "a=10;b=long('1'*a);p=long('2'*a)-7;m=long('3'*a)+11" "pow(b,p,m)"
100000 loops, best of 3: 8.89 usec per loop

gmpy does not have a powmod() function. That function was introduced in gmpy2. gmpy2.powmod will automatically convert the arguments to mpz and return an mpz result. Your function could be written as:

def mypowmod(base, power, modulus):
    return long(gmpy2.powmod(base, power modulus)

Even including the conversion between long and mpz, it is still much faster than using the built-in long type.

python -m timeit -s "import gmpy2;a=10;b=long('1'*a);p=long('2'*a)-7;m=long('3'*a)+11" "long(gmpy2.powmod(b,p,m))"
1000000 loops, best of 3: 1.72 usec per loop
casevh
  • 11,093
  • 1
  • 24
  • 35
0

No.

But using the gmpy.mpz type is mostly unneeded as the built in long type has all the needed operations for this function. The code uses the built in pow function rather than say the gmpy.powmod function so converting to gmpy.mpz is unneeded and as the pow function returns a long the code becomes:

def mypowmod(base, power, modulus):
  result = pow(base, power, modulus)
  return result

Which is better written as:

mypowmod = pow
Dan D.
  • 73,243
  • 15
  • 104
  • 123
  • If I dont convert the input to MPZ, how can I handle integer size greater than 2^63-1? Could you give a simple example on gmpy.powmod? – drdot Feb 15 '15 at 07:07
  • python integers don't have a fixed size. they can be arbitrarily large. – Eevee Feb 15 '15 at 07:50