Handling big numbers in code

by

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

More Related Contents:

  1. How do i implement these algorithms below
  2. Removing duplicates in lists
  3. How to generate all permutations of a list?
  4. How to efficiently compare two unordered lists (not sets) in Python?
  5. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  6. Weighted random selection with and without replacement
  7. What is the fastest way to flatten arbitrarily nested lists in Python? [duplicate]
  8. Understanding recursion in Python
  9. Efficient calculation of Fibonacci series
  10. How did Python implement the built-in function pow()?
  11. Find longest repetitive sequence in a string
  12. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  13. Algorithm to find which number in a list sum up to a certain number
  14. Checking if all elements in a list are unique
  15. Mapping a range of values to another
  16. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  17. Weighted random sample in python
  18. How to check whether two lists are circularly identical in Python
  19. How to test if one string is a subsequence of another? [duplicate]
  20. Fast prime factorization module
  21. What’s the algorithm of ‘set.intersection()’ in python?
  22. How to incrementally sample without replacement?
  23. Split a list of numbers into n chunks such that the chunks have (close to) equal sums and keep the original order
  24. Replace list of list with “condensed” list of list while maintaining order
  25. Python: Choose random line from file, then delete that line
  26. String similarity metrics in Python [duplicate]
  27. Python Weighted Random [duplicate]
  28. How can I interleave or create unique permutations of two strings (without recursion)
  29. Python: powerset of a given set with generators [duplicate]
  30. All possible paths from one node to another in a directed tree (igraph)

Leave a Comment