← All Cracked Math projects
PM-A04NOT STARTEDADVANCEDMATHPYTHONIMPACT ★★★☆☆

Beat CPython's big-int multiply with an FFT you can trust

CPython multiplies huge ints with Karatsuba (a divide-and-conquer method). Your FFT, with a proven rounding bound, should crush it. Then compute 10M digits of pi.

EST.25 h
REWARD+400 XP
AFTERCPython Lib/_pylong.py + 2

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Time to multiply two 1M-digit and two 10M-digit integers; time to 10M digits of pi
GOAL · >= 5x faster than CPython int at 1M digits, and exact on 10^4 random products; pi to 10M digits matching a published digit file; an honest report of the gap to gmpy2
CPython int (Karatsuba, KARATSUBA_CUTOFF = 70 in longobject.c) and gmpy2 (GMP) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

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 BB as limbs, x=∑ixiBix = \sum_i x_i B^i. The product's limbs before carrying are the convolution zk=∑i+j=kxiyjz_k = \sum_{i+j=k} x_i y_j, which an FFT computes in O(Nlog⁡N)O(N \log N). The float result is only useful if every zkz_k comes back within 12\tfrac12 of the true integer. Brent and Zimmermann (Modern Computer Arithmetic, chapter 3, after Percival) bound the error of a length-N=2nN = 2^n floating-point convolution by

∥z′−z∥∞<∥x∥2 ∥y∥2((1+ε)3n(1+ε5)3n+1(1+β)3n−1),\|z' - z\|_\infty < \|x\|_2\,\|y\|_2 \Big( (1+\varepsilon)^{3n} (1+\varepsilon\sqrt5)^{3n+1} (1+\beta)^{3n} - 1 \Big),

with ε=2−53\varepsilon = 2^{-53} in float64 and β\beta the error in your twiddle factors (ε/2\varepsilon/\sqrt2 if they are correctly rounded). With LL limbs below BB, ∥x∥2≤L (B−1)\|x\|_2 \le \sqrt{L}\,(B-1). So the bound grows with LB2L B^2: more digits per limb means fewer limbs and a faster FFT, until the bound crosses 12\tfrac12. Signed limbs in [−B/2,B/2)[-B/2, B/2) cut ∥x∥2\|x\|_2 in half, which quarters the bound and buys one more bit per limb.

The NTT removes rounding. Each prime here is c⋅2m+1c \cdot 2^m + 1 with primitive root 3, so it has roots of unity of order 2232^{23}, 2252^{25} and 2262^{26}; the shared limit is length 2232^{23}. The product of the three primes is about 7.9×10257.9 \times 10^{25} (2862^{86}), so any coefficient below that is recovered exactly. For Barrett with a kk-bit prime and x<p2x < p^2, use m=⌊22k/p⌋m = \lfloor 2^{2k}/p \rfloor and q=((x≫(k−1)) m)≫(k+1)q = \big((x \gg (k-1))\, m\big) \gg (k+1). Every intermediate stays under 2622^{62}, so uint64 never overflows, and x−qpx - qp needs at most two subtractions of pp.

For pi, the Chudnovsky series is

1π=12∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k+3/2,\frac{1}{\pi} = 12 \sum_{k=0}^{\infty} \frac{(-1)^k (6k)!\,(13591409 + 545140134k)}{(3k)!\,(k!)^3\,640320^{3k+3/2}},

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.

EXPECTEDFig. 1
1e-6 1e-4 1e-2 1e0 1e2 1e4 under 0.5: rounds correctly 2 3 4 5 6 decimal digits per limb worst |computed − exact| in any product coefficient (log) proven bound, 1M digits proven bound, 10M digits measured, all nines, 1M measured, random digits, 1M
The bound above against measured worst errors, using numpy.fft in float64 with unsigned decimal limbs. The bound allows 4 digits per limb at 1M digits but only 3 at 10M. All-nines inputs, the worst case for this bound, are 20 to 30 times below it, and at 5 digits per limb they already round wrongly. Why it's here: Your own FFT should give a picture like this. It shows why tests alone are not enough: random digits look safe at sizes where the worst case fails.

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_bytes and int.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 ValueError by default. Call sys.set_int_max_str_digits(0) before printing pi.
  • Twiddles by recurrence. Computing wkw^k by repeated multiplication builds up error far beyond β\beta. 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 101310^{13}, 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.
HINT · OBJECTIVE 2
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.

Objectives

0 / 7 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. 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"`.
  2. The limb size you use at each length is justified by the proven bound, not only by tests passing.
  3. Timings include conversion to and from Python ints.

Side quests

Python's decimal module (libmpdec) multiplies huge numbers with its own number-theoretic transform. Race it at 1M and 10M digits and explain the gap.
Add Newton-iteration division and square root on top of your multiply and use them for the last steps of the pi computation.

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.