Handling big numbers in code


Question

I'm working on a programming problem where I need to handle a number involving 100000 digits. Can python handle numbers like this?

1
9
8/11/2012 3:47:56 PM

As other answers indicated, Python does support integer numbers bounded only by the amount of memory available. If you want even faster support for them, try gmpy (as gmpy's author and current co-maintainer I'm of course a little biased here;-):

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x+1'
10000 loops, best of 3: 114 usec per loop
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y+1'
10000 loops, best of 3: 65.4 usec per loop

Typically, arithmetic is not the bottleneck for working with such numbers (although gmpy's direct support for some combinatorial and number-theoretical functions can help if that's what you're doing with such numbers). Turning the numbers into decimal strings is probably the common operation that will feel slowest...:

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(x)'
10 loops, best of 3: 3.11 sec per loop
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(y)'
10 loops, best of 3: 27.3 msec per loop

As you see, even in gmpy stringification of huge numbers can be hundreds of times slower than a simple addition (alas, it's an intrinsically complicated operation!); but in native Python code the ratio of times can go to stringification being tens of thousands times slower than a simple addition, so you really want to watch out for that, especially if you decide not to download and install gmpy (for example because you can't: e.g., gmpy is not currently supported on Google App Engine).

Finally, an intermediate case:

$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x*x'
10 loops, best of 3: 90 msec per loop
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*y'
100 loops, best of 3: 5.63 msec per loop
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*x'
100 loops, best of 3: 8.4 msec per loop

As you see, multiplying two huge numbers in native Python code can be almost 1000 times slower than the simple addition, while with gmpy the slowdown is less than 100 times (and it's not too bad even if only one if the numbers is already in gmpy's own format so that there's the overhead of converting the other).

23
9/6/2009 9:12:35 PM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon