◄ WORLD V · SONNY 5DART 110 · a helldive at the net

SCHONHAGE-STRASSEN multiply giants with a Fourier transform

To multiply two enormous integers, treat their digits as a signal: the product’s digits are the convolution of the two digit lists, and a Fast Fourier Transform computes a convolution in O(n log n) instead of O(n²). Their trick was to run the FFT over integers mod a Fermat number (an exact-arithmetic transform, no round-off), giving O(n log n log log n) — the champion from 1971 to 2007.

THE TECHNIQUE digits convolve; carry; done

Write each number as digit-coefficients of powers of the base. The product’s coefficients are the convolution cₖ = Σ aᵢbⱼ over i+j=k; then propagate carries. Schoolbook does that convolution in O(n²); an FFT/NTT does it in O(n log n). Multiply two numbers and watch the convolution and carry. live demo

HISTORY & CREDIT not the first fast multiply, and not alone

“Schönhage-Strassen invented fast multiplication” — no; that is theirs Karatsuba’s (1962). They made it near-linear. cited

~1805 / 1965 · the FFT itself is Gauss’s (unpublished, c.1805), rediscovered by Cooley & Tukey (1965) — so crediting them as inventors understates its prehistory.
1962 · Karatsuba (with Ofman) breaks O(n²) first — dart 041, the true start of fast multiplication; Toom-Cook generalises it.
1971 · Schönhage & Strassen reach O(n log n log log n) via a number-theoretic transform over rings Z/(22^m+1) (exact, no round-off). The same year, Pollard independently gives the NTT — usually omitted.
2007 / 2019 · Fürer beats it asymptotically; Harvey & van der Hoeven reach O(n log n) — exactly the bound Schönhage & Strassen conjectured in 1971, 50 years earlier.

Superseded in theory (galactic algorithms), still the practical method for enormous integers (GMP uses it). Schönhage & Strassen, 1971

RECOMMEND FOR I-13 the multiply runs; the FFT is the frontier

The digit convolution and carry run on the bignum today — the worked example lands exactly:

$ i13 run ss.i13 # 1234 x 5678 convolution [5,16,34,60,61,52,32] -> carry -> 7,006,652 # matches schoolbook
Recommend: the LIT part runs — schoolbook and Karatsuba (dart 041) already multiply on the corpus’s bignum, and the convolution above (verified 1234×5678 = 7,006,652) is exactly what an FFT/NTT computes, only slower. The frontier is the FFT acceleration: a number-theoretic transform needs a modular FFT with roots of unity — expressible over bignum, but a real build, and it only overtakes Karatsuba at thousands of digits (the crossover).
Note: it closes a lineage the corpus already runs — Karatsuba (041), the FFT (059), bignum — the three ingredients of near-linear multiplication.