How Python Represents Integers using Bignum
Learn how Python represents integer numbers of any magnitude using Bignum.
Programmers coding in lower-level languages like C/C++ need to consider the amount of memory used for an integer representation. They have to consider the minimum and maximum values of a variable to avoid problems of overflow. These programmers have to consider if an int is sufficient or if a long is necessary.
Compared to C/C++, Python has an advantage when working with integers. In Python, there is no integer overflow problem; therefore, Python programmers do not need to worry about what variable type to use for each integer. Python allows programmers to manipulate huge numbers without having to worry about precision loss. The only representation limitation for integers in Python is when the machine runs out of free memory, but that is a hardware limitation.
In practice, this is useful for calculating large values like factorials. Without using external libraries, Python can calculate factorials independently from the result’s magnitude. Below is an example of a function that calculates factorials:
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n-1)Executing the factorial function with the input 231 demonstrates the magnitude of the integer value that Python can represent.
>>> factorial(231)
1792233667382633521618843263044232513197622942259968207385215805123682159320161029848328112148883186161436034535802659466205111867109614573242316954383604389464524535467759401326264883566523043560811873179996072188155290081861628010250468430411854935707396605833540921031884571521279145124581094374547412403086564118143957940727734634769439112260383017302489106932716079961487372942529947238400000000000000000000000000000000000000000000000000000000Note that there are more efficient algorithms to calculate factorials; this example serves to illustrates the magnitude of the output.
Integer Representation
Before proceeding further in the discussion, note that this article considers only the CPython implementation. This implementation is the default version and the most commonly distributed version of Python. Different implementations could represent integers differently, but this discussion will only cover integer representation in CPython. One advantage of using CPython is that the whole codebase is publicly available on the CPython repository on Github.
Since Python 3, all integer values are represented with the struct below:
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};It is possible to expand the macros and represent the struct this way:
struct {
sssize_t ob_refcnt;
struct _typeobject *ob_type;
ssize_t ob_size;
uint32_t ob_digit[1];
};The first two elements of the struct above are not important for this discussion. The element ob_refcnt is used in Python’s garbage collector, and the ob_type is used for type identification, which, in this case, the object is an integer.
The integer value is represented by the two other variables: ob_digit and ob_size. Python uses the ob_digit array to store each digit of the number separately in different index locations. Additionally, the ob_size variable is used to store two values. It stores the length of the ob_digit array and the sign of the integer (positive or negative).
In the majority of the systems, ob_digit is a uint32_t array, but in some older computers, ob_digit can be a uint16_t array. This article will only consider the first case of uint32_t arrays.
This method of representing integer values with a sequence of digits with strings or arrays is known as Bignum Arithmetic. Usually, Bignum implementations represent values in binary; however, that would not be space-efficient with uint32_t arrays.
Base 2³⁰
Considering systems that use uint32_t arrays for integer representation, Python cannot use all 32 bits to store the digit. A brief explanation of this limitation is that many built-in functions in Python require a specific number of bits for the representation of integers for practicality and efficiency reasons. For a more curious reader, there are comments about this limitation in the official CPython repository.
Since Python can only use 30 of the 32 bits of each element, all integers are converted to base 2³⁰. Consequently, all digits in the array have values between 0 and 1073741823 (2³⁰-1). Note that the variable ob_size stores the length of the array with the number in base 2³⁰, not base 10.
In addition, the array representation is in little-endian order. In other words, the order is in the least-significant value first (lower index value). For instance, suppose the numbers were stored in base 10 instead of base 2³⁰, the number 234 represented using the array would be: <4,3,2>.
For example, the number 234254646549834273498 in Python would be first converted to base 2³⁰. Since we do not have enough characters to represent all digits of a number in base 2³⁰, for illustrational purposes, the digits of the number in base 2³⁰ will be represented in base 10. Hence, the number 234254646549834273498 in base 2³⁰ is 462328538,197050268,203, where 462328538 represents the first digit and so forth with the other two values. That is because 462328538 × (2³⁰)⁰ + 197050268 ×(2³⁰)¹ + 203 × (2³⁰)² = 234254646549834273498.
Therefore, the number 234254646549834273498 in Python with base 2³⁰ has 3 digits: 462328538,197050268,203 and it would be represented in Python in the following way:
If this number was negative, the Python representation would have the same array but
ob_sizewould be-3.
Common Integers Optimization
Get Alberto Oshiro’s stories in your inbox
Join Medium for free to get updates from this writer.
This process of converting and representing integers using Bignum Arithmetic is time-consuming for run-time operations. For this reason, since the int type is immutable in Python, Python creates representations for all values between -5 and 256 before the execution of the program. During the execution, Python reuses these objects whenever they are requested.
One clear disadvantage of using Bignum Arithmetic is in terms of memory usage. Any integer value in Python uses at least 28 bytes of memory, 7 to 14 times more than the language C would require creating a variable of type int.
Bignum Addition
One benefit of using Bignum Arithmetic is the simplicity of performing arithmetic operations. This article will cover only addition, but the other operations follow the same concept.
The idea behind Bignum’s addition is to perform addition the same way people add numbers in base 10 using paper and pencil. The process begins with the least significant digit first and continues towards the higher significance digits. Each digit from each number is added together separately, and the result moves over a carry value towards the following higher significance digit.
Bignum Arithmetic follows this approach using arrays. The process is to add each value from the same index from each array separately and carry over the value that exceeds the decimal place to the following index. The algorithm starts at index 0 and iterates until the length of the smallest array, adding up the digits using the carry method throughout.
The algorithm starts by creating a new empty array for storing the result. Note that the result of the sum between two values has at most one more digit than the largest number in summation. For example, the sum between 9 and 93 is 102. The largest value in this example is 93, and it has 2 digits. The result of the addition has 3 digits, one more than 93. In some cases, the number of digits of the result is equal to the number of digits of the largest number. In that case, the algorithm decreases the size of the array to fit the result without leading 0's. The only case where the last array cell (highest index) has value 0is for the representation of the number 0.
For illustrational purposes, here is an example of addition between two numbers represented with Bignum Arithmetic. The values being added together are 234254646549834273498 and 23425464654983.
The number 234254646549834273498 would be represented this way:
and the number 23425464654983 would be represented this way:
The algorithm starts by creating a new array of size 4 (one cell longer than the array representing the largest value in the addition).
Next, the algorithm starts the carry process index by index.
After iterating through all the indices up to the smallest array length, the algorithm computes the following values:
Finally, the program decreases the array size by 1 to remove the last empty cell. Then, the complete structure created from the addition is represented this way:
The original algorithm is written in C, but here is a Python function that simulates this process.
The function
addtakes in two Python lists. Each list represents one of the integers being added in this function. The numbers are already converted to base 2³⁰, and each list element stores one digit of the value.
In conclusion, Python uses Bignum Arithmetic to represent integers. Compared to other languages like Java and C/C++, Python makes working with integers very simple. While other languages require the programmer to determine the size variable to store a number, Python abstracts this need. However, this method also has a downside in terms of memory usage. While languages like C use either 2 or 4 bytes to represent a variable of type int, Python requires at least 28 bytes. For simple scripts, this extra memory usage does not cause a difference; however, for data-heavy programs, it might be interesting using other languages like C.
Thank you very much for reading this article! Soon I will be publishing more about Python and other programming topics.
