Big integers in Python

Why this matters

The largest 64-bit signed integer is 9223372036854775807, which has 19 digits. Many real calculations go past that. A factorial of 25 is a 26-digit number. A cryptography library works with numbers of 300 digits or more. A program that counts every way to arrange a deck of cards gets results past 60 digits. A fixed 64-bit type cannot store any of these, and in a language with fixed-size integers an overflow prints a wrong answer without any message.

Python does not have this problem for ordinary code. Its int type grows to hold any whole number that fits in memory. This lesson shows what that means in practice, how a 64-bit type fails for comparison, and the one limit you do meet: Python refuses to turn a very long int into text unless you allow it. The speed and the memory cost of very large numbers are covered at the end.

Python int grows as needed

A Python int stores as many digits as the number needs. It grows when the number grows, and Python frees its memory when no name refers to it. The next program does arithmetic on a 30-digit number and a 9-digit number. Each operation works the same way it would with small numbers.

a + b = 123456789012345678902222222211
a - b = 123456789012345678900246913569
a * b = 121932631124828532112482853211126352690
a // b = 124999998873437499901
a % b = 574845669
2 ** 100 = 1267650600228229401496703205376

The number a has 30 digits. The product a * b has 39 digits, and Python keeps all of them. The operator ** raises a number to a power, so 2 ** 100 is 2 to the power 100. The division operator // gives the whole-number part of the quotient, and % gives the remainder. The division rules for negative numbers come after the factorial example.

Worked example: a factorial that overflows a 64-bit type

A factorial of a number n, written n!, is the product of all the whole numbers from 1 up to n. So 5! is 1 times 2 times 3 times 4 times 5, which is 120. Factorials grow very fast, which makes them a good test of the size limit.

The program below computes 25! two ways. The first uses the ctypes module to store the running product in a 64-bit signed value, which wraps the way a Java long does. The second uses a plain Python int.

25! in 64 bits = 7034535277573963776
25! as int = 15511210043330985984000000
bit length = 84

The 64-bit version prints a number that is wrong. The true value of 25! has 26 digits, while the 64-bit answer has 19 and bears no relation to the real value. The program gave no warning. The plain int version prints the correct value.

The method bit_length shows how many bits the number needs. The value is 84 bits long, which is more than the 64 bits of a 64-bit type. That is the reason the fixed version fails. The math.factorial function computes the same product in one call, but the loop shows the work.

Worked example: long sequences

The next program has two loops of increasing difficulty. The first computes 30!, which is a 33-digit number. The second computes the 100th Fibonacci number. The Fibonacci sequence starts with 1 and 1, and each new number is the sum of the two before it. Its 100th term has 21 digits.

The program uses two names, prev and cur, to hold the last two numbers. Each step computes the next number and moves the names forward. Python allows both values to be set in one line, so prev, cur = cur, prev + cur computes the right side first and then moves both names.

30! = 265252859812191058636308480000000
fib(100) = 354224848179261915075
digits of 2 ** 200 = 61

The Fibonacci loop starts with prev equal to 0 and cur equal to 1. After the loop, cur holds the 100th term. The loop ends with cur as the answer, and prev as the value before it.

The last line counts the digits of 2 to the power 200. The function str turns the number into text, and len counts the characters. For a Python int, the length of its decimal text is the number of digits. This is a simple way to check the size of an answer.

Worked example: working with the digits

The digit count from the sequence example is one way to look inside a big number. A second way is to visit each digit and do something with it. The next program does this for 2 to the power 1000, which has 302 digits.

Each character of the text is a digit. The expression int(c) turns a digit character into its number, so sum(int(c) for c in text) adds the digits. The part inside the brackets is a generator expression, a short way to write a loop that produces one value at a time.

digits in 2 ** 1000 = 302
sum of digits = 1366
first 20 digits = 10715086071862673209

The slice text[:20] takes the first 20 characters, from position 0 up to position 20 without including it. The result is the leading digits of the number.

This approach works on the text of the number. Dividing by 10 in a loop would also work, but it needs one division for each digit. The text form is shorter and easier to read.

Division and remainder with negative numbers

Division needs more care with negative numbers. Python's // rounds down, toward negative infinity. Its % gives a remainder with the sign of the divisor. The built-in divmod returns both parts at once. The program below uses -7 and 3.

-3
2
(-3, 2)
-3
-2

The quotient of -7 divided by 3 is -2 with a fraction, and the rule rounds it down to -3. The remainder is then 2, because -7 equals 3 times -3 plus 2. The remainder always has the sign of the divisor, so it is never negative when the divisor is positive. Many programs use this to find a position in a circle or a repeating pattern. The same rule holds for big numbers, so the remainder of a 30-digit number works the same way.

The last two lines show the rule for a negative divisor. The remainder of 7 divided by -3 is -2, which has the sign of -3.

Comparing big integers

Python compares the values of two int objects with ==. Two numbers with the same value are equal, even when they were created at different times. The keyword is is different. It checks whether two names point to the same object, and it is used for None, not for numbers.

True
True
True

The first line is True, because the two values are equal. The comparison operators <, >, <= and >= work on any two ints, big or small. In Java, == compares object identity, so Python's rule is simpler.

Converting back to a smaller type

Sometimes a program needs to turn a big number into a fixed-size value. The ctypes module does this with a silent wrap, the same as a cast in Java. The program below converts 2 to the power 40 into a 32-bit value.

2 ** 40 & 0xFFFFFFFF = 0
as c_int32 = 0
bit length = 41

The number 2 to the power 40 is a 1 followed by 40 zeros in binary, so its lowest 32 bits are all 0. The mask keeps those 32 bits, which are 0, and no error appears. The ctypes line gives the same answer. Python does not check for a fixed size, so the conversion is silent. Compare the value with the original, or check the bit length, when a wrong number would cause a bigger problem.

The digit limit when converting to text

Python has one limit on large integers that other languages do not have. Converting an int with more than 4300 digits to text, or reading text with more than 4300 digits into an int, raises an error. The limit protects programs from very slow conversions and from attacks that send huge numbers as text. The limit is a setting, and it can be changed for a program that needs it.

print(len(str(2 ** 20000)))

Traceback (most recent call last):
  File ".../limit.py", line 1, in <module>
    print(len(str(2 ** 20000)))
              ~~~^^^^^^^^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

The message gives the limit and the way to raise it. The function sys.set_int_max_str_digits changes the limit for the program. A number with 6021 digits is far beyond what an interview question asks for, so the default is enough for almost every task. The power 2 ** 20000 itself is computed without any error. The limit applies only when the number is turned into text.

The same limit applies to reading. Text with more than 4300 digits, such as int("1" * 5000), raises the same kind of error. A program that reads very large input must allow the larger size before it converts the text.

How big is big

The table below shows how fast a factorial grows. The digit counts are the length of the text, and the bit counts come from bit_length.

The value 20! is the largest factorial that a 64-bit type can hold. It has 62 bits, which is inside the 64 bits of that type. The value 21! needs 66 bits, so it is the first factorial that a 64-bit type cannot store. A Python program that needs 21! or more uses a plain int and gets the right answer with no extra code.

The number 52! is the count of ways to put a 52-card deck in order, which is why that example appears in the introduction. Its 226 bits are far beyond any fixed-size type. A plain int stores it with no extra work from the program.

Speed and memory

A big int takes more memory than a small one, and each operation on it takes more time. The cost grows with the number of digits. A small number such as 500 takes about 28 bytes, while a number with thousands of digits takes thousands of bytes. For most programs in this course the numbers are small, and the cost does not matter. For a loop that multiplies big numbers millions of times, the cost can matter, and the fix is a better algorithm, not a different type.

When the answer is a size you can predict, a fixed-size type is faster, because the processor handles it in one step. Python does not offer that choice for its int, so the ctypes and array modules are the tools when speed on fixed sizes matters.

Common mistakes

Forgetting that a result is returned. In Python, an operation on an int returns a new value and never changes the original. A line such as x + 1 on its own computes a value and throws it away. The next program shows this.

after the sum without assignment: 10
after the assignment: 11

The first sum computes 11 and throws the result away. The habit to build is to write x = x + 1, or x += 1, every time you want the value to change.

Expecting a 64-bit wrap. A Python int does not wrap at 64 bits. Code that was written for a fixed-size language may expect the wrap, and the output then differs. Check the type of the value before you assume a limit.

Using is to compare numbers. The keyword is compares objects. Python can share small integer objects, so is may give a result that looks right by accident. Use == for numbers. Python warns about this with a SyntaxWarning when a literal number appears next to is.

Passing text that is not a number. int("12a") raises ValueError: invalid literal for int() with base 10: '12a'. The message shows the text that failed. This matters when the text comes from a user or a file. Wrap the conversion in a try block, or check the text before creating the number.

Looking for a separate type for big numbers. Python has no separate type for big numbers, so use a plain int for every value. Small values are faster, but the code is the same.

Practice

Work each exercise yourself before you open the answer. Predict the output on paper first.

1. Write a program that computes 30! with a plain int and prints it. Then print the number of digits.
2. The program below prints 100 for a sum. Explain why it prints 100 and not 101.

total = 100
total + 1
print(total)

3. Write a program that prints 2 to the power 200 and checks whether it equals 2 ** 200 computed a second way, with pow(2, 200). Explain which operator you used for the check.
4. Find the output of -7 % 3, and explain why it is not -1.
5. Write a function digit_count(value) that returns the number of decimal digits in a positive int. Test it with 2 ** 200.

Each exercise has an answer below a "Show the answer" line. Try each one first, then read the answer.

1. The loop multiplies the numbers from 1 to 30, and the answer has 33 digits.

Show the answer

f = 1
for i in range(2, 31):
    f = f * i
print(f)
print(len(str(f)))

The output is 265252859812191058636308480000000 and then 33.

2. The sum total + 1 returns 101, but the result is not stored. The name total still points to 100.

Show the answer

The fix is total = total + 1.

3. The check uses ==, and both sides have the same value.

Show the answer

p = 2 ** 200
print(p)
print(p == pow(2, 200))

The output is the 61-digit number and then True. The == operator compares the values.

4. The output is 2. The remainder takes the sign of the divisor, which is 3, so it is never negative.

Show the answer

print(-7 % 3)

The output is 2. The value -1 is what the remainder of a language with the sign of the dividend would give.

5. The function returns the length of the text form of the number.

Show the answer

def digit_count(value):
    return len(str(value))
 
print(digit_count(2 ** 200))

The output is 61, the digit count shown in the sequence example.

What you now know

• A Python int holds whole numbers of any size, limited only by memory. Sums, products and powers stay exact.
• A factorial of 21 or more does not fit in a 64-bit type. A Python int holds it with no extra code.
• The operators // and % round down and give a remainder with the sign of the divisor. divmod returns both parts.
• == compares values. is compares objects, and it is for None.
• Converting an int with more than 4300 digits to text raises an error. sys.set_int_max_str_digits changes that limit.
• An operation returns a new value, so store it with x = x + 1 when you want the change.