NUM Numbers and algebra Algorithm
Big integers
Also known as: Arbitrary-precision arithmetic · bignum · big integers · long arithmetic · int in Python · math/big · BigInt · Knuth's algorithm D · converting to decimal
Numbers longer than a machine word are kept as an array of “digits” in a large base and computed by school column methods. Which base to choose, why a digit in Python is 30 bits rather than 32, where a square hides, and why converting a number to a decimal string was declared a vulnerability in 2022.
The factorial of a thousand is a number of 2568 digits. A 64-bit machine word holds nineteen, yet Python prints 1000! in full and instantly. Inside, it keeps it as 285 “digits” of 30 bits and multiplies them the way we multiply in a column, only each “digit” runs from zero to 1,073,741,823. Below, n! grows in such memory multiplication by multiplication: each cell is one digit, its colour the value. Switch the base, then press “Print”: it turns out that putting a number on the screen can cost more than computing it.
The black cells at the start are the zeros at the end of the number: 1000! has 33 of them in base 2³⁰, 27 in base 10⁹, and 249 zeros in decimal notation. Look at the printing. In base 10⁹ each cell is a ready set of nine decimal digits, and printing is one pass over the memory. In base 2³⁰ there are no decimal digits in memory at all: to get the last nine you have to divide the whole number by 10⁹, then the quotient again, and so on 286 times. Each division goes over all the cells, and for 285 cells that comes to more than forty thousand cell divisions, a square of the length.
The idea
A big number is an array of “digits” in base B, least significant first: x = d₀ + d₁B + d₂B² + … Addition, subtraction, multiplication and division are the school column algorithms, only a digit is now a machine number. The base is taken as large as possible, but so that the intermediate results, the sum of two digits with a carry and the product of two digits with a carry, fit in a machine word of double width.
Addition is a pass from the lowest digit to the highest: s = ai + bi + carry, the digit of the result is s mod B, the new carry s div B, that is, 0 or 1. Multiplying by a short number is also one pass, with a carry smaller than the multiplier. Multiplying two big numbers in a column is every digit by every digit, O(n·m) digit multiplications. How large the base can be is decided by one inequality.
If in column multiplication the carry is propagated at once, then every intermediate sum “digit of the result + product of two digits + carry” is at most B² − 1, and the carry is at most B − 1.
Induction on the steps. A digit of the result is at most B − 1, the product of two digits at most (B − 1)², the carry by assumption at most B − 1. The sum is at most (B − 1) + (B − 1)² + (B − 1) = B² − 1. The new carry is the quotient of this sum by B, at most (B² − 1) div B = B − 1. At the start of a row the carry is zero, so the assumption holds from the very first step.
Hence the choice of bases. The competitive programmer's B = 10⁹: B² = 10¹⁸ fits in signed 64 bits, while 10¹⁰ no longer does, as 10²⁰ is more than 2⁶⁴. And such a number is easy to print: each digit is nine decimal places. Binary bases are more economical: with 2³² every bit of the word is used, the product of two digits fits in 64 bits, and shifts and bitwise operations are almost free. Go, GMP and BigInt in JavaScript go further and give a digit the whole 64-bit word: the product of two such digits takes 128 bits, but the processor produces them in one instruction anyway, the high and low halves; in Go this is bits.Mul64.
Python chose 30 bits. A comment in the CPython source lists the conditions: the digit type must hold 2B − 1, the sum of two digits without overflow, the double-digit type B² − 1, and the marshal storage format requires the digit length to be a multiple of 15. 15 and 30 bits fit; on 64-bit machines a digit is 30 bits in a 32-bit cell, and a product goes in a 64-bit one.
Code
Big numbers in base 10⁹, the way they are written at programming contests: parsing a string, printing, addition counting carries, multiplication by a short number, the column, and division by a short number. The program computes 1000! and 2¹⁰⁰⁰ and checks everything against the language's built-in arithmetic.
1000! has 2568 digits in 286 base-10^9 digits, 249 zeros at the end it starts with 40238726007709377354 and its last nonzero digits are 0027753472 2^1000 has 302 digits; 8063 carries in 17212 digit additions (10^1000 - 1) * 3^2000: 112 x 107 digits -> 218, mod 1000000007 = 817895449
With doublings a carry happens in 47 % of digit additions, whenever the digit is at least half the base. Long chains of carries, as in 999…9 + 1, happen, but rarely, and adding big numbers costs O(n). Division by a short number goes the other way, from the highest digit: the remainder is multiplied by B and added to the next digit, as in long division.
In Go the product of two base-10⁹ digits together with the carry fits in a uint64 only because the carry is propagated at once. If you accumulate a sum of products in one cell and carry later, the cell overflows by the nineteenth addition of numbers around 10¹⁸.
How it is built in Python and Go
An integer in Python is always a big one. The object header takes 24 bytes, its last field holds the number of digits and the sign, and then come the digits themselves, 4 bytes each. So sys.getsizeof for a number of k digits is 24 + 4k: for 1000! that is 285 digits and 1164 bytes, exactly what the first scene shows. The parameters can be seen right from the language: sys.int_info reports bits_per_digit=30 and sizeof_digit=4. Small numbers are big too, just with one digit, and Python checks the addition of two such with a separate fast branch.
In Go a big number is a big.Int: a sign and a slice of machine words nat, least significant word first. The inner loops, “add two vectors of words”, “multiply a vector by a word and add to another”, are written in assembly for each processor, and bits.Mul64 and bits.Add64 compile to one or two instructions. So there is no point rewriting math/big by hand, and on long numbers it switches by itself from the column to Karatsuba multiplication.
Division: guessing a digit of the quotient
Dividing a big number by a big number is the same long division, but a digit of the quotient cannot be found by trial: there are B of them, about a billion. It is guessed from the top digits: the two top digits of the remainder are divided by the top digit of the divisor. The guess may be larger than the real digit, and then it is decreased, checking against the next digit. Donald Knuth showed in algorithm D that if both numbers are first multiplied so that the top digit of the divisor is at least B/2, the guess exceeds the real digit of the quotient by at most 2. The proof and all the details are in “The Art of Computer Programming”, volume 2, § 4.3.1; what matters here is the outcome: column division, like multiplication, costs O(n·m) digit operations.
For very long numbers division is reduced to multiplication. The reciprocal 1/b is found by Newton's method, each iteration doubling the number of correct digits, and the quotient is obtained by a multiplication. The time of division is then of the same order as multiplication. Another way is recursive division by halves, on the same divide-and-conquer scheme as Karatsuba; this is how GMP and math/big divide long numbers.
Printing: where the square hides
A binary base is convenient for arithmetic and inconvenient for people. To print a number it is converted to decimal, and the naive way is the one in the first scene: nibble nine digits off the bottom by dividing by 10⁹. Each division goes over the whole number, and there is one division per nine digits, O(n²) in total. On a number of a hundred thousand digits this is already a quarter of a second in Python, on a million half a minute.
Divide and conquer is faster. Divide the number by 109·2k, a power close to the square root of the number, and get two halves by number of digits: the high one and the low one. Convert each the same way, padding the low one with leading zeros. The powers 10⁹, 10¹⁸, 10³⁶, … are computed by squaring and kept in a table. Dividing the halves costs as much as a multiplication of that length, M(n), there are log n levels of recursion, and altogether it is O(M(n) log n) by the master theorem.
A measurement: a number of d digits is converted to a string in three ways, our naive one, our “by halves” and the built-in one, and the string is parsed back into a number.
The naive way grows with slope 2: ten times longer means a hundred times slower, 0.35 seconds in Python and 0.29 in Go at a hundred thousand digits. “By halves” at the same hundred thousand is 4 times faster in Python and 15 times in Go, and the gap grows. The built-in ways behave differently. In Go String() is built like “by halves”; the math/big source says that the recursion speeds up conversion fourfold at medium lengths and about 30 times at twenty thousand digits; but parsing a string with SetString is almost quadratic: at three hundred thousand digits it is already three times slower than printing. In Python both printing and parsing grow slower than a square: since version 3.12 CPython converts very long numbers with divide-and-conquer algorithms from the _pylong module.
Before that, conversion in CPython was quadratic, and in 2022 this was declared a vulnerability, CVE-2020-10735: a long string of digits in a request to a server tied up the processor inside int() for a long time. Since then Python by default refuses to convert between a string and a number of more than 4300 digits, sys.int_info.default_max_str_digits, until the program lifts the limit itself with sys.set_int_max_str_digits. More on this story in the article on complexity from measurements. The limit does not touch binary bases: hex() and int(s, 16) work in linear time, because a hexadecimal digit is exactly four bits.
What operations cost
| operation | column methods | fast methods |
|---|---|---|
| addition, subtraction, comparison | O(n) | — |
| multiplication by a short number, division by a short number | O(n) | — |
| multiplication | O(n²) | Karatsuba O(n1.585), Toom–Cook, FFT and NTT almost O(n log n) |
| division | O(n²), algorithm D | Newton or recursion: O(M(n)) or O(M(n) log n) |
| converting to decimal and back | O(n²) | “by halves”: O(M(n) log n) |
Memory is O(n) per number, and it is easy to estimate in advance: n! has about log₁₀ n! ≈ n(log₁₀ n − 0.434) decimal digits by Stirling's formula, and log₁₀ 2³⁰ ≈ 9.03 times fewer 30-bit Python digits. And here is what your browser's engine can do: BigInt is built its own way there. Press “Measure”: five operations on numbers from a thousand to three hundred thousand digits.
Addition grows linearly, the other operations slower than a square: in Chrome we got multiplication with a slope of about 1.2, division and printing about 1.4–1.5. Different JavaScript engines differ noticeably here, so the conclusion is one: if a program works with numbers of hundreds of thousands of digits, measure on the platform it will run on.
Where it is used
- Python, Go, JavaScript, Java. In Python every integer is big; in Go there is
math/big; in JavaScript the BigInt type, which appeared in the 2020 standard; in JavaBigInteger. At contests in C++ people still write base-10⁹ big integers themselves. - Cryptography. A 2048-bit RSA key is 69 Python digits or 32 Go words, and all of the encryption is exponentiation modulo such numbers. For it libraries like OpenSSL and GMP keep separate fast loops of modular multiplication.
- Record numbers. In October 2024 the GIMPS project found the prime 2136,279,841 − 1 with 41,024,320 digits. Checking such a number is 136 million squarings modulo a number of 136 million bits. In a column each would cost trillions of word multiplications, and the check would stretch over thousands of years; with multiplication via the fast Fourier transform it becomes feasible. This time thousands of graphics processors did the computing.
History
School algorithms with long numbers are older than computers, and for machines they were systematically described by Donald Knuth in the second volume of “The Art of Computer Programming” in 1969: algorithms A, S, M and D, addition, subtraction, multiplication and division, with proofs and analysis. Torbjörn Granlund started the GMP library in January 1991 and released it in September; today computer algebra systems and many record computations rest on it. Python had big integers from its first versions, and with Python 3.0 (2008) only one type, int, remained. In Go the math/big package was part of the first stable version of the language in 2012.
Problems
In the first problem you count the carries when adding two numbers of a million digits each; among the tests are the first million digits of π and e. In the second, how many zero low cells n! has in base 2³⁰, 10⁹ or any other, when the factorial itself would not fit in any memory.