Fürer's Algorithm

Purpose: Multiply two $n$-bit integers in $O\left(n\log n\cdot 2^{O({\log }^{\ast }n)}\right)$ — the first improvement on Schönhage-Strassen after 36 years (Martin Fürer, 2007).

The Idea

Schönhage-Strassen works in $\mathbb{Z}/(2^k+1)\mathbb{Z}$, where roots of unity are powers of 2 and twiddle multiplications are free shifts — but only $2k$ of them exist, which forces the recursion to shrink block sizes by a square root each level, costing the $\log \log n$ factor.

Fürer works instead in a ring
$R=\mathbb{C}[x]/(x^P+1)$
that contains both:

• a small set of “fast” roots of unity (powers of $x$, so multiplying by them is a cyclic shift — free), and
• a large set of ordinary roots of unity (which cost real multiplications).

The FFT is then arranged so that most levels use the fast roots and only $O({\log }^{\ast }n)$ levels need the expensive ones. That is where the iterated logarithm comes from.

Complexity

$O\left(n\log n\cdot 2^{O({\log }^{\ast }n)}\right)$

Since ${\log }^{\ast }n\le 5$ for every $n$ below $2^{65536}$, the $2^{O({\log }^{\ast }n)}$ factor is a constant for all practical purposes — but a constant nobody has ever measured, because the algorithm has never been implemented competitively.

A galactic algorithm

Fürer’s is the textbook example of a galactic algorithm: asymptotically superior, but only for inputs larger than anything that will ever exist. Estimates put the crossover with Schönhage-Strassen far beyond the number of atoms in the observable universe.

The others in this category worth recognising:

Algorithm	Beats the practical option above	Practical?
Fürer multiplication	astronomically large $n$	no
Harvey-van der Hoeven $O(n\log n)$	$n>2^{1729^{12}}$	no
Coppersmith-Winograd matrix multiply	enormous matrices	no
Pettie-Ramachandran MST	—	no (unanalysable)
Chen et al. $m^{1+o(1)}$ max flow	—	not yet
AKS primality	never	no

Why it matters anyway

The 2019 Harvey-van der Hoeven $O(n\log n)$ algorithm — which matches the conjectured lower bound — built directly on Fürer’s technique of mixing cheap and expensive roots of unity. Fürer’s paper broke a 36-year barrier and showed the $\log \log n$ was not intrinsic; that opened the door.

For a competitive programmer the lesson is a healthy one: asymptotic complexity is not running time. The $O(n\log n\log \log n)$ Schönhage-Strassen and the $O(n^{1.465})$ Toom-3 both beat “faster” algorithms across every input size you will meet.

Variants / Use Cases

• Schönhage-Strassen — what production libraries use
• Big Integer Multiplication — the topic page
• Complexity Theory — asymptotics versus practice