Use GMP as default implementation of integers in Python3
Torbjorn Granlund
tg at swox.com
Wed Nov 5 01:39:53 CET 2008
Victor Stinner <victor.stinner at haypocalc.com> writes:
First, I have a questions about GMP: I'm unable to find the pow() function
with only mpz_t arguments. mpz_powm() only uses mpz_t variables but it
computes the modulo, not just base^exp. How can I compute base^exp with an
exponent bigger than a unsigned long? Eg. 2^(2^40) with a 32 bits CPU.
You cannot, since that wouldn't fit in the memory of your computer.
I wrote a patch for the Python language to use the GMP library for the
integers. My patch works correctly but Python is a little bit slower (3% to
14%) because most of the time, integers are (very) small. I guess that the
most common range is [-2^32-1; 2^32-1]. Should I use a better memory
allocator? I also changed it to use Python memory managment. How can I speed
it Python+GMP?
In Python2, an integer is 31 bits + sign and automatically switch to long
integer (unlimited) on overflow. In Python3, all integers are long integers.
About the long integers:
- base = 2^15 (32768)
- multiply: grade school multiplicatin or Karatsuba (cutfoff = 70 digits,
and 2x70 digits for square (a*a))
- divide: no idea (see x_divrem())
The base is very small but was choosed because it works on any platform or
CPU.
Do you know other successful integration of GMP in languages?
I cannot answer, but perhaps somebody else on this list can be of more
help!
--
Torbjörn
More information about the gmp-discuss
mailing list