Working with large and small integers_Modern Python Cookbook-QQ阅读中文短篇网

上QQ阅读APP看书，第一时间看更新

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.

Getting ready

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 inpidual 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 × 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, 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)

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 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 2³⁰ 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?

For some commonly used numbers (-5 to 256), Python can create a secret pool of objects to optimize memory management. This leads to a small performance improvement.

There's more...

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

For dealing with inpidual 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.