Brief
Multiplying two integers is a convolution of their digits, so an FFT can do it fast. Multiply million-digit integers by splitting them into limbs (fixed-size chunks of digits) and convolving with your B11 FFT. Prove a floating-point error bound that dictates the limb size: bigger limbs are faster, but every result must stay close enough to an integer to round correctly. Add an exact 3-prime NTT in NumPy uint64 as the fallback. An NTT (number-theoretic transform) is an FFT done in modular integer arithmetic, so there is no rounding at all; three primes are combined to cover the full result size. Use Barrett reduction (a fast way to compute x mod p with multiplications instead of division) inside it. On top, compute pi to 10 million digits with Chudnovsky binary splitting (a fast-converging series for pi, summed by recursively combining halves).
Approach
Write each integer in base as limbs, . The product's limbs before carrying are the convolution , which an FFT computes in . The float result is only useful if every comes back within of the true integer. Brent and Zimmermann (Modern Computer Arithmetic, chapter 3, after Percival) bound the error of a length- floating-point convolution by
with in float64 and the error in your twiddle factors ( if they are correctly rounded). With limbs below , . So the bound grows with : more digits per limb means fewer limbs and a faster FFT, until the bound crosses . Signed limbs in cut in half, which quarters the bound and buys one more bit per limb.
The NTT removes rounding. Each prime here is with primitive root 3, so it has roots of unity of order , and ; the shared limit is length . The product of the three primes is about (), so any coefficient below that is recovered exactly. For Barrett with a -bit prime and , use and . Every intermediate stays under , so uint64 never overflows, and needs at most two subtractions of .
For pi, the Chudnovsky series is
and each term adds about 14.18 digits. Binary splitting turns the sum into a tree of big-integer products, so a faster multiply speeds up everything. Build in this order: exact float multiply, the bound, conversions, timing, then the NTT, then pi.
Where people get stuck
- Decimal limbs cost more than the multiply. Turning a 1M-digit int into a decimal string, and back, can take
longer than CPython's whole multiplication. Use power-of-two limbs through
int.to_bytesandint.from_bytes. - The 4,300-digit limit. Since Python 3.11, converting an int with more than 4,300 decimal digits to or from a
string raises
ValueErrorby default. Callsys.set_int_max_str_digits(0)before printing pi. - Twiddles by recurrence. Computing by repeated multiplication builds up error far beyond . Compute each twiddle directly from its angle, or the bound no longer describes your code.
- Random tests hide the worst case. Random digits give errors many times smaller than all-maximum limbs. Test the worst case on purpose.
- Carries in a vectorised world. Rounded coefficients can be around , far bigger than a limb. Carry with repeated split-and-shift passes in int64, or rebuild the Python int from bytes, rather than a Python loop over limbs.
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- At least 5× faster than CPython int at 1M digits and exact on 10^4 random products; pi to 10M digits matching a published digit file; the gap to gmpy2 reported honestly. Record with `python tools/mlarena.py record PM-A04 "<k>x vs CPython at 1M digits"`.
- The limb size you use at each length is justified by the proven bound, not only by tests passing.
- Timings include conversion to and from Python ints.
Side quests
Terms in plain words
- Karatsuba multiplication
- A divide-and-conquer method that multiplies two numbers with three half-size multiplications instead of four.
- Limb
- One fixed-size chunk of a big integer's digits, treated as a single coefficient in the convolution.
- NTT (number-theoretic transform)
- An FFT that works with integers modulo a prime instead of complex numbers, so it is exact.
- Barrett reduction
- Computing x mod p using a precomputed reciprocal and multiplications, which avoids slow division.
- Chudnovsky binary splitting
- Summing the Chudnovsky series for pi (about 14 digits per term) by splitting it into halves recursively so most work is on big-integer multiplications.
- Twiddle factor
- One of the complex roots of unity an FFT multiplies by. How accurately you compute them enters the error bound directly.
- Garner's algorithm
- A way to rebuild a number from its remainders modulo several primes, one prime at a time, without ever dividing big numbers.
Why it rates ★★★☆☆
Rigorous rounding-error analysis tied to a real speed win is uncommon. It reads as serious numerics.