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, they're all integers to Python.
Imagine you need to calculate something really big. For example, we want to calculate the number of ways to permute the cards in a 52-card deck. The factorial 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 has one universal type of integer, and this covers all of the bases, from individual bytes to numbers that fill all of the memory. Here are the steps to use integers properly:
- Write the numbers you need. Here are some smallish numbers: 355, 113. There's no practical upper limit.
- 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
- Creating a much, much bigger number with a calculation using the
**operator ("raise to power") 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 has two representations for numbers. The conversion between these two is seamless and automatic.
For smallish numbers, Python will generally use 4-byte or 8-byte integer values. Details are buried in CPython's internals; they depend on the facilities of the C compiler used to build Python.
For numbers over
sys.maxsize, Python switches to internally representing integer numbers as 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 × 1067. 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, this giant number works 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)
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 -263 ... 263 - 1. Outside this range, largish integers are used.
The values in
sys.int_info tell us that large integers are a sequence of 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 in order to be represented. Instead of the commonly used symbols, 0, 1, 2, 3, …, 9, for base-10 numbers, we'd need 230 distinct symbols for each digit of these large numbers.
A calculation involving 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?
Python offers us a broad set of arithmetic operators:
// operators are for division; we'll look at these in a separate recipe named Choosing between true division and floor division. The
** operator raises a number to a power.
For dealing with individual bits, we have some additional operations. We can use
>>. 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.
- We'll look at the two division operators in the Choosing between true division and floor division recipe, later in this chapter.
- We'll look at other kinds of numbers in the Choosing between float, decimal, and fraction recipe, which is the next recipe in this chapter.
- For details on integer processing, see https://www.python.org/dev/peps/pep-0237/.