Working with large and small integers

Many programming languages make a distinction between integers, bytes, and long integers. Some languages include distinctions for signed versus unsigned integers. How do we map these concepts to Python?

The easy answer is that we don't. Python handles integers of all sizes in a uniform way. From bytes to immense numbers with hundreds of digits, it's all just integers to Python.

Getting ready

Imagine you need to calculate something really big. For example, calculate the number of ways to permute the cards in a 52-card deck. The number 52! = 52 × 51 × 50 × ... × 2 × 1, is a very, very large number. Can we do this in Python?

How to do it...

Don't worry. Really. Python behaves as if it has one universal type of integer, and this covers all of the bases from bytes to numbers that fill all of the memory. Here are the steps to using integers properly:

1. Write the numbers you need. Here are some smallish numbers: 355, 113. There’s no practical upper limit.

2. Creating a very small value—a single byte—looks like this:

      >>> 2
      2

Or perhaps this, if you want to use base 16:

      >>> 0xff
      255

In later recipes, we'll look at a sequence of bytes that has only a single value in it:

      >>> b'\xfe'
      b'\xfe'

This isn't—technically—an integer. It has a prefix of b' that shows us it's a 1-byte sequence.

3. Creating a much, much bigger number with a calculation might look like this:

      >>> 2**2048 
      323...656

This number has 617 digits. We didn't show all of them.

How it works...

Internally, Python uses two kinds of numbers. The conversion between these two is seamless and automatic.

For smallish numbers, Python will generally use 4 or 8 byte integer values. Details are buried in CPython's internals, and depend on the facilities of the C-compiler used to build Python.

For largish numbers, over sys.maxsize, Python switches to large integer numbers which are sequences of digits. Digit, in this case, often means a 30-bit value.

How many ways can we permute a standard deck of 52 cards? The answer is 52! ≈ 8 × 10⁶⁷. Here's how we can compute that large number. We'll use the factorial function in the math module, shown as follows:

>>> import math
>>> math.factorial(52)
80658175170943878571660636856403766975289505440883277824000000000000

Yes, these giant numbers work perfectly.

The first parts of our calculation of 52! (from 52 × 51 × 50 × ... down to about 42) could be performed entirely using the smallish integers. After that, the rest of the calculation had to switch to largish integers. We don't see the switch; we only see the results.

For some of the details on the internals of integers, we can look at this:

>>> import sys
>>> import math
>>> math.log(sys.maxsize, 2)
63.0
>>> sys.int_info
sys.int_info(bits_per_digit=30, sizeof_digit=4)

The sys.maxsize value is the largest of the small integer values. We computed the log to base 2 to find out how many bits are required for this number.

This tells us that our Python uses 63-bit values for small integers. The range of smallish integers is from -2⁶⁴ ... 2⁶³ - 1. Outside this range, largish integers are used.

The values in sys.int_info tells us that large integers are a sequence of numbers that use 30-bit digits, and each of these digits occupies 4 bytes.

A large value like 52! consists of 8 of these 30-bit-sized digits. It can be a little confusing to think of a digit as requiring 30 bits to represent. Instead of 10 symbols used to represent base 10 numbers, we'd need 2**30 distinct symbols for each digit of these large numbers.

A calculation involving a number of big integer values can consume a fair bit of memory. What about small numbers? How can Python manage to keep track of lots of little numbers like one and zero?

For the commonly used numbers (-5 to 256) Python actually creates a secret pool of objects to optimize memory management. You can see this when you check the id() value for integer objects:

>>> id(1)
4297537952
>>> id(2)
4297537984
>>> a=1+1
>>> id(a)
4297537984

We've shown the internal id for the integer 1 and the integer 2. When we calculate a value, the resulting object turns out to be the same integer 2 object that was found in the pool.

When you try this, your id() values may be different. However, every time the value of 2 is used, it will be the same object; on the author's laptop, it's id = 4297537984. This saves having many, many copies of the 2 object cluttering up memory.

Here's a little trick for seeing exactly how huge a number is:

>>> len(str(2**2048))
617

We created a string from a calculated number. Then we asked what the length of the string was. The response tells us that the number had 617 digits.

There's more...

Python offers us a broad set of arithmetic operators: +, -, *, /, //, %, and **. The / and // are for division; we'll look at these in a separate recipe named Choosing between true division and floor division. The ** raises a number to a power.

For dealing with individual bits, we have some additional operations. We can use &, ^, |, <<, and >>. These operators work bit-by-bit on the internal binary representations of integers. These compute a binary AND, a binary Exclusive OR, Inclusive OR, Left Shift, and Right Shift respectively.

While these will work on very big integers, they don't really make much sense outside the world of individual bytes. Some binary files and network protocols will involve looking at the bits within an individual byte of data.

We can play around with these operators by using the bin() function to see what's going on.

Here's a quick example of what we mean:

>>> xor = 0b0011 ^ 0b0101
>>> bin(xor)
'0b110'

We've used 0b0011 and 0b0101 as our two strings of bits. This helps to clarify precisely what the two numbers have as their binary representation. We applied the exclusive or (^) operator to these two sequences of bits. We used the bin() function to see the result as a string of bits. We can carefully line up the bits to see what the operator did.

We can decompose a byte into portions. Say we want to separate the left-most two bits from the other six bits. One way to do this is with bit-fiddling expressions like these:

>>> composite_byte = 0b01101100
>>> bottom_6_mask =  0b00111111
>>> bin(composite_byte >> 6)
'0b1'
>>> bin(composite_byte & bottom_6_mask)
'0b101100'

We've defined a composite byte which has 01 in the most significant two bits, and 101100 in the least significant six bits. We used the >> shift operator to shift the value by six positions, removing the least significant bits and preserving the two most significant bits. We used the & operator with a mask. Where the mask has 1 bit, a position's value is preserved in the result, where a mask has 0 bits, the result position is set to 0.

See also

• We'll look at the two division operators in the Choosing between true division and floor division recipe
• We'll look at other kinds of numbers in the Choosing between float, decimal, and fraction recipe
• For details on integer processing, see https://www.python.org/dev/peps/pep-0237/