Handling very large numbers in Python

Question

I've been considering fast poker hand evaluation in Python. It occurred to me that one way to speed the process up would be to represent all the card faces and suits as prime numbers and multiply them together to represent the hands. To whit:

class PokerCard:
    faces = '23456789TJQKA'
    suits = 'cdhs'
    facePrimes = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 59, 61]
    suitPrimes = [2, 3, 5, 7]

AND

    def HashVal(self):
      return PokerCard.facePrimes[self.cardFace] * PokerCard.suitPrimes[self.cardSuit]

This would give each hand a numeric value that, through modulo could tell me how many kings are in the hand or how many hearts. For example, any hand with five or more clubs in it would divide evenly by 2^5; any hand with four kings would divide evenly by 59^4, etc.

The problem is that a seven-card hand like AcAdAhAsKdKhKs has a hash value of approximately 62.7 quadrillion, which would take considerably more than 32 bits to represent internally. Is there a way to store such large numbers in Python that will allow me to perform arithmetic operations on it?

Historiographer

Are you sure that, once you start representing your data in this way you will still see any significant speed improvement? I realize this doesn't answer your questions, but still.. – Offshore

I have a suggestion: instead of using separate variables for the card values and the representations, I suggest using dictionaries. (So faces = {'2': 11, '3': 13, '4': 17, '5': 19, '6': 23, '7': 29, '8': 31, '9': 37, 'T': 41, 'J': 43, 'Q': 53, 'K': 59, 'A': 61} and suits = {'c': 2, 'd': 3, 'h': 5, 's': 7}.) – Underbrush

Relying on integer multiplication and factorization sounds like it would be a huge loss in speed, not a gain. It would probably be a loss in memory too. If you really want to optimize hand storage, you could consider using a bitfield with 3 bits per rank (because you can have between 0 and 4 cards of each rank) and 4 bits per suit. But I'm not sure python is the best language for these kind of optimizations. Perhaps using a collections.Counter instead would be simpler. – Ontiveros

Answer 1

Python supports a "bignum" integer type which can work with arbitrarily large numbers. In Python 2.5+, this type is called long and is separate from the int type, but the interpreter will automatically use whichever is more appropriate. In Python 3.0+, the int type has been dropped completely.

That's just an implementation detail, though — as long as you have version 2.5 or better, just perform standard math operations and any number which exceeds the boundaries of 32-bit math will be automatically (and transparently) converted to a bignum.

You can find all the gory details in PEP 0237.

Kokoruda

The question is, does the performance hit from using bignum instead of 32 bit integers exceed the performance benefit from the clever method of hand evaluation he's using. – Kamseen

Actually, the barrier between int and long was broken in 2.5. 3.0 removes int altogether, making long the only integer type. – Pappose

@Ignacio — You're right, I'd conflated the 2.5 and 3.0 changes. Fixed my answer. – Kokoruda

How big is a big num? Can it be PHI ^ 4000000? – Bipinnate

@Mike Caron — If the struct listed in PEP 0237 is accurate, longs' lengths (in digits) are stored as unsigned 32-bit integers, up to 4,294,967,295 digits, meaning they can easily hold φ**(4*10**6), which is "only" 832,951 digits. However, φ is not an integer, so you will need to use a Decimal (Python's floating-point bignum) to calculate the number. You can store the result in a long afterward, however. – Kokoruda

@IgnacioVazquez-Abrams Just a point of clarification, long is the only integer type in 3.0, but it's named int. (And the old int is gone.) – Gagliardi

Answer 2

Python supports arbitrarily large integers naturally:

Example:

>>> 10**1000
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

You could even get, for example, a huge integer value, fib(4000000).

But still it does not (for now) supports an arbitrarily large float!!

If you need one big, large, float then check up on the decimal Module. There are examples of use on this site: OverflowError: (34, 'Result too large')

Another reference: 9.4. decimal — Decimal fixed point and floating point arithmetic

You can even using the gmpy module if you need a speed-up (which is likely to be of your interest): Handling big numbers in code

Another reference: gmpy (Google Code. Read-only)

History

Answer 3

You could do this for the fun of it, but other than that it's not a good idea. It would not speed up anything I can think of.

• Getting the cards in a hand will be an integer factoring operation which is much more expensive than just accessing an array.

• Adding cards would be multiplication, and removing cards division, both of large multi-word numbers, which are more expensive operations than adding or removing elements from lists.

• The actual numeric value of a hand will tell you nothing. You will need to factor the primes and follow the Poker rules to compare two hands. h1 < h2 for such hands means nothing.

Oxidation

Answer 4

Python supports arbitrarily large integers naturally:

In [1]: 59**3*61**4*2*3*5*7*3*5*7
Out[1]: 62702371781194950

In [2]: _ % 61**4
Out[2]: 0

Fourdrinier

These are not big numbers. – Lianaliane

His example isn't large, do this instead and they are large: >>> 593*614*2*3*5*7*3*5*7**230 2112200455965545784463763534981730015003287507654092906559062824748896024215265933823546366174073338762879285480688931763493239406757976048436785624579024287324291438651910344789488047853106653055212183616484650 Apologies, I can't get that to format nicely. – Tableau

Answer 5

The Python interpreter will handle it for you. You just have to do your operations (+, -, *, /), and it will work as normal.

The int value is unlimited.

Be careful when doing division. By default, the quotient is turned into float, but float does not support such large numbers. If you get an error message saying float does not support such large numbers, then it means the quotient is too large to be stored in float you’ll have to use floor division (//).

It ignores any decimal that comes after the decimal point, this way, the result will be int, so you can have a large number result.

>>>10//3
3

>>>10//4
2

Shearwater

How does your answer address large numbers issue in the question? – Brae

It means you can just do the normal operations with large numbers but be careful with division – Shearwater

@Hedy What can/should I do in case of division? I am trying to divide (10^18 - 1) by 2, and it's incorrect. Gives me a round 5 * 10^17 instead of 49999...99.5. Can I do anything about this? I am using the '/' division – Sheets

The big number could be the biggest amount of decimals in Pi. – Lianaliane

or Graham's number – Lianaliane

Answer 6

Why would you ever want to do this? If you insist on storing the hand as a single encoded value instead of a dict or list use a bit-string instead of the product of primes. Multiplication and prime number factorization is slow.

Encode each card as a power of 2 (1, 2, 4, 8, 16, etc.). You can add a card with hand |= card. You can check for a card with if hand & card > 0.

Snaffle