PaperlayerView exact revision on arXiv

Source-linked AI summary

Even faster integer multiplication

David Harvey, Joris van der Hoeven, Grégoire Lecerf

arXiv:1407.3360v1cs.CCcs.SCmath.NT

TL;DR

Fürer's approach lacked an explicit bound for K. This paper gives a new multiplication algorithm with an explicit K = 8 bound and a conjecture-dependent variant with K = 4.

  • Problem

    Fürer suggested minimizing K but gave no explicit bound for it.

    Source: §1 · p. 1

  • Method

    The paper introduces a new algorithm for integer multiplication and, for a conjectural variant, replaces coefficient ring C with finite field Fp[i] to use fast multiplication modulo Mersenne numbers.

    Source: §1 · pp. 1–2

  • Results

    The new algorithm gives I(n) = O(n log n 8^(log^* n)), while the conjecture-dependent variant gives I(n) = O(n log n 4^(log^* n)).

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The optimized Fürer variant achieves K = 16, suggesting the new algorithm is faster by a factor of 2^(log^* n).

    Source: §1 · p. 1

    The K = 4 variant depends on Conjecture 9.1, a slight weakening of the Lenstra–Pomerance–Wagstaff conjecture on Mersenne-prime distribution.

    Source: §1 · p. 2

Abstract

from arXiv · show

We give a new proof of F\"urer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike F\"urer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of F\"urer's algorithm achieves only K = 16, suggesting that the new algorithm is faster than F\"urer's by a factor of 2^(log^* n). Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.

1. Introduction

The paper develops an integer-multiplication algorithm with an explicit K = 8 bound, avoiding Fürer’s special coefficient rings, and gives a conditional K = 4 algorithm. It places these results in the history of FFT-based multiplication and explains the new algorithm’s speedup over an optimised Fürer variant.

1.2. Our contributions and outline of the paper

  • I(n)=O(n log n 8^(log* n)) for the new algorithm, while the optimised Fürer variant reaches K = 16, suggesting a speedup factor of 2^(log* n).The paper attributes the difference to avoiding the factor-of-two zero-padding associated with Fürer’s artificial fast roots of unity and shifting more work into short transforms.Source: §1 · p. 1, §1.2 · p. 4

1. Introduction

  • The new algorithm splits integers into small chunks, uses complex DFTs decomposed into short transforms, and converts those transforms to recursive integer multiplications using Bluestein’s method and Kronecker substitution.It works directly over C and does not require special coefficient rings with fast roots of unity.Source: §1 · pp. 1–2, §1.2 · p. 4

1.2. Our contributions and outline of the paper

  • Under Conjecture 9.1 on Mersenne-prime distribution, a further algorithm achieves I(n)=O(n log n 4^(log* n)) by replacing C with Fp[i].The method exploits fast multiplication modulo numbers of the form 2^q−1.Source: §1 · p. 2, §1.2 · p. 4
  • The same techniques also apply to polynomial multiplication over finite fields, for which no Fürer-type complexity bounds were previously known.The details are presented in the companion paper [24].Source: §1 · p. 2

1.1. Brief history and related work

  • Integer multiplication progressed from Karatsuba’s subquadratic method to FFT-based Schönhage–Strassen and then Fürer’s bound O(n log n 2^O(log* n)).The paper recounts how FFT-based methods use polynomial multiplication and suitable rings to improve asymptotic bounds.Source: §1.1 · pp. 2–3

1.2. Our contributions and outline of the paper

  • The paper develops tools for analyzing slowly growing recurrence inequalities used in the complexity proofs.These tools support the analyses of the new algorithm and Fürer’s algorithm.Source: §1.2 · p. 4
  • An unoptimised implementation of the modular-arithmetic variant ran an order of magnitude slower than GMP, and the authors doubt a highly optimised version will be competitive in the near future.They identify polynomial multiplication over finite fields as a potentially promising practical direction.Source: §1.2 · p. 4

2. Survey of classical tools

This section reviews the classical tools used later: Fourier transforms and polynomial multiplication, alongside data-rearrangement and integer-to-polynomial techniques. It explains how DFTs can be composed, used for cyclic convolution, and reduced to convolution.

2. Survey of classical tools

  • The section surveys classical tools—including array operations, DFTs, FFT multiplication, Bluestein's transform, and Kronecker substitution—that the later algorithms use.It directs readers to standard references for further details.Source: §2 · p. 5

2.1. Arrays and sorting

  • On a Turing machine, transposing an n1 × n2 matrix of b-bit elements takes O(b n1 n2 log min(n1,n2)) time, and merge sort supports more complex rearrangements.The transpose method recursively splits along the shorter dimension.Source: §2.1 · p. 5

2.2. Discrete Fourier transforms

  • A DFT evaluates a polynomial at powers of a principal root of unity, and applying the inverse DFT recovers the input up to a factor of n.The section notes that the new algorithms work over fields whose characteristic does not divide n.Source: §2.2 · p. 5

2.3. The Cooley–Tukey FFT

  • Cooley–Tukey factors a DFT into inner and outer transforms with twiddle-factor multiplications; in the Turing model, data rearrangement and table extraction also contribute cost.The recurrence for ring operations is F_R(n1 n2) ≤ n1 F_R(n2) + n2 F_R(n1) + n.Source: §2.3 · p. 6

2.4. Fast Fourier multiplication

  • FFT multiplication computes a polynomial product modulo X^n − 1 using forward and inverse DFTs and pointwise multiplication; if the product degree is below n, the ordinary product is recovered.This modular product is also called cyclic convolution.Source: §2.4 · p. 7

2.5. Bluestein's chirp transform

  • Bluestein's chirp transform reduces an even-length DFT to a cyclic convolution of the same length, followed by O(n) additional operations.The convolution uses a fixed polynomial independent of the input.Source: §2.5 · p. 7

2.6. Kronecker substitution and segmentation

  • Kronecker substitution encodes polynomial products as integer products, while segmentation reverses the reduction by splitting integers into chunks and recovering the result by overlap-add.For the applications described, the overlap-add recovery costs O(n).Source: §2.6 · p. 8

3. Fixed point computations and error bounds

This section develops fixed-point complex arithmetic for approximate DFTs in the Turing model, with complexity bounds and error analysis. It defines the representation and error measures, then establishes error control for arithmetic, roots of unity, and composed transforms.

3.1. Fixed point numbers

  • Fixed-point values use a signed integer mantissa scaled by a fixed exponent, with an implicit absolute error bound and relative error measured against the exponent's scale.The machine accuracy is ϵ = 2^(1−p).Source: §3.1 · p. 8

3.2. Basic arithmetic

  • Fixed-point addition and subtraction take O(p) time, multiplication takes O(I(p)) time, and their relative errors are bounded in terms of input errors and machine accuracy.The same framework extends to cyclic convolution of vectors.Source: §3.2 · p. 9

3.3. Precomputing roots of unity

  • The paper constructs approximations to powers of a 2^k-th root of unity with relative error at most ϵ, using fixed-point square roots and increased temporary precision.The root table construction takes O(2^k p log p log log p) time.Source: §3.3 · p. 10

3.4. Error analysis for fast Fourier transforms

  • The butterfly transform is tight, and composing tight transforms preserves tightness; consequently, radix-2 DFTs have complexity O(2^k k I(p)).The error analysis accounts for the transform stages and twiddle-factor multiplications.Source: §3.4 · p. 10

4. A simple and fast multiplication algorithm

The section presents a DFT-based integer multiplication algorithm that computes short transforms through Bluestein's chirp transform and Kronecker substitution. Its recurrence yields an O(n log n K^(log^* n)) multiplication bound, and its DFT routine can outperform conventional Cooley–Tukey under a stated multiplication-cost assumption.

4. A simple and fast multiplication algorithm

  • The algorithm's key innovation combines Bluestein's chirp transform with Kronecker substitution to convert short DFTs into cyclic integer products modulo numbers of the form 2^n0 − 1.The resulting products are over (Z/(2^n0 − 1)Z)[i].Source: §4 · p. 10
  • When I(m) = m(log m)^(1+o(1)) and transform length n ∼ p, Proposition 4.1 improves transform complexity over Cooley–Tukey by roughly a factor of log n.The compared costs are n^2(log n)^(2+o(1)) for Cooley–Tukey and n^2(log n)^(1+o(1)) for Proposition 4.1.Source: §4 · p. 11
  • It first segments the n-bit inputs into log n-bit chunks, forming polynomial inputs of degree O(n/log n), then computes their product through DFTs of length O(n/log n).The coefficient precision and working precision are both O(log n).Source: §4 · p. 11
  • The DFT computation groups radix-2 layers into blocks of about log log n layers, using the Bluestein–Kronecker routine for the blocks and Cooley–Tukey for the remaining layers.The transforms are inverted after pointwise multiplication, and the coefficients are rounded to recover the exact polynomial product.Source: §4 · p. 11
  • I(n) = O(n log n K^(log^* n)) for some constant K > 1.The theorem follows by applying a recurrence bound to the normalized cost T(n) = I(n)/(n log n).Source: §4 · p. 12

5. Logarithmically slow recurrence inequalities

This section develops recurrence bounds for algorithms that reduce problem size through logarithmically slow functions. It relates their iteration counts to log^*, then bounds recurrences with weighted sums of smaller subproblem costs.

5. Logarithmically slow recurrence inequalities

  • Every logarithmically slow function admits an iterator once the input is sufficiently large that the function decreases the input by at least one.Examples given include log x, 2 log x, and (log x)^2.Source: §5 · pp. 12–13
  • Logarithmically slow functions reduce problem sizes, and their iterators measure how many repeated reductions are needed; these iteration counts equal log^* x + O(1).The section introduces this framework to handle recurrence inequalities used in later sections.Source: §5 · pp. 12–13
  • If T is bounded by L up to σ and larger inputs reduce to weighted subproblems of size at most φ(y), Proposition 5.3 gives T(y) ≤ C L K^(log^* y − log^* σ).The recurrence's weighted sum is bounded by 1 + B log^ℓ y, under the proposition's stated conditions.Source: §5 · p. 13

6. Even faster multiplication

The optimized algorithm uses complex cyclic integer convolution as its recursive problem and tunes the transforms and chunk sizes to obtain an explicit multiplication bound.

6. Even faster multiplication

  • Complex cyclic integer convolution, rather than ordinary integer multiplication, is the basic recursive problem because Bluestein's chirp transform reduces DFTs to such convolutions.Source: §6 · p. 14
  • Increasing coefficient size from about lg n to (lg n)^2 reduces convolution-output inflation to 2 + O(1/lg n), while longer short transforms make Bluestein–Kronecker multiplications dominate.Source: §6 · p. 14
  • The main recurrence bounds normalized cost C(n) using a smaller admissible n0 and an additive O(1) term.Source: §6 · p. 15
  • The DFT construction groups layers into short transforms, using Bluestein–Kronecker for most groups and ordinary Cooley–Tukey for the remaining layers; fixed-operand transforms are reused.Source: §6 · pp. 14, 16
  • O(n log n 8^(log^* n)) bounds integer multiplication, with the recursion extended from admissible inputs to general inputs.The proof first bounds C(n) on admissible integers, then uses I(k) ≤ 3 C(O(k)) + O(k).Source: §6 · p. 17

7. An optimised variant of Fürer's algorithm

The optimized variant makes Fürer's bound explicit at K=16. It encodes inputs in a ring with a fast root of unity and organizes DFT work to control the recursive cost.

7. An optimised variant of Fürer's algorithm

  • Fürer's ring R=C[X]/(X^(2^r+1)) contains a principal 2^r-th root X whose powers can be multiplied by in linear time.Source: §7 · p. 17
  • The encoding splits inputs into chunks and zero-pads polynomial coefficients, a cost of introducing artificial roots of unity.Source: §7 · p. 18
  • The transform algorithm applies Cooley–Tukey in groups, while twiddle-factor multiplications dominate and are reduced through Kronecker substitution.Source: §7 · p. 18
  • The cost analysis reduces to a recurrence involving n0 and C(n0), with an O(n log n) additive term.Source: §7 · p. 19
  • I(n)=O(n log n 16^(log^* n)) is achieved by the optimized variant of Fürer's algorithm.The authors report that they do not know how to obtain K<16 using Fürer's approach.Source: §7 · p. 19

8. Fast multiplication using modular arithmetic

This section adapts fast integer multiplication to modular arithmetic, yielding O(n log n 8^(log^* n)). Its implementation depends on finding suitable primes and roots of unity; under GRH, the paper gives a deterministic option for prime selection.

8. Fast multiplication using modular arithmetic

  • O(n log n 8^(log^* n)) is achieved by a modular-arithmetic variant of the fast multiplication algorithm.The section aims to replace complex-number arithmetic with modular arithmetic while retaining the bound.Source: §8 · p. 19, §8.2 · p. 20

8.1. Sketch of the algorithm

  • The algorithm reduces integer multiplication to polynomial multiplication modulo X^(2^k) − 1, using chunks of b bits.The coefficients of the product have at most 2b + k bits.Source: §8.1 · p. 19
  • Choosing precision λ so that log(p^λ) > 2b + k makes the modular product determine the integer polynomial product unambiguously.The computation uses DFTs over Q_p but represents elements with finite precision in Z/p^λZ.Source: §8.1 · p. 19
  • Cooley–Tukey decomposes each DFT into short transforms, which Bluestein converts to cyclic convolutions handled recursively.Kronecker substitution converts those convolutions to multiplication modulo 2^n0 − 1.Source: §8.1 · p. 19

8.2. Computing suitable p and !

  • Finding a suitable prime by the unconditional bound can take longer than the multiplication bound itself.The stated bound p0(k) < 2^(6k) comes with a search time of O(2^(5k) k^O(1)).Source: §8.2 · p. 20
  • Multivariate splitting introduces enough zero-padding to raise K, while a top-level Fürer step can retain K = 8 with deeper levels modular.The prime-search problem occurs only at the top recursion level, so the remaining levels can use the modular algorithm.Source: §8.2 · p. 20
  • Under GRH, p0(k) can be computed deterministically in O(2^k k^O(1)) time.The algorithm adjusts coefficient size so prime computation costs O(n log n), while retaining the O(n log n 8^(log^* n)) bound.Source: §8.2 · p. 20
  • Finding the required root of unity costs O(p^(1/4+ε)) in this setting, less than finding p itself.The root is computed modulo p^λ by lifting a primitive root modulo p.Source: §8.2 · p. 21

9. Conjecturally faster multiplication

The section presents a conjecturally faster multiplication method using finite fields based on Mersenne primes, converting short products into cyclic products to reduce the bound from K = 8 to K = 4. It establishes the preceding bound through Theorem 9.6 and Proposition 5.3, bounding an auxiliary parameter and using bivariate DFTs.

9. Conjecturally faster multiplication

  • Replacing short products with cyclic products over a Mersenne-prime field saves a factor of two at each recursion level, reducing K from 8 to 4.The algorithm relies on unproved conjectures about the distribution of Mersenne primes.Source: §9 · p. 21

9.2. Crandall and Fagin's algorithm revisited

  • Adapting Crandall and Fagin’s algorithm [12] with varying-size chunks reduces multiplication modulo a Mersenne number to cyclic multiplication over a smaller Mersenne-prime field.That field supplies suitable roots of 2 and high-order roots of unity for efficient FFTs.Source: §9 · p. 21, §9.2 · p. 22

9.3. Bivariate Crandall–Fagin reduction

  • The bivariate Crandall–Fagin reduction maps cyclic-polynomial multiplication over (Z/p Z)[i] to multiplication over Fp0[i][X; Y]/(X^M − 1; Y^N − 1).It uses varying-size chunks and requires N ≤ q, gcd(N, q0) = 1, and q0 > 2⌈q/N⌉ + lg(MN) + 3.Source: §9 · p. 22, §9.3 · pp. 23–24

9.1. Mersenne primes

  • Under Conjecture 9.1, a Mersenne prime p exists between 2n and 2nc, and the proposition gives a way to compute it and a primitive 2q+1-th root of unity in Fp[i].Here c is the ratio of the conjecture’s upper and lower constants.Source: §9.1 · p. 22

9.4. Conjecturally faster multiplication

  • Assuming Conjecture 9.1, the recursive algorithm decomposes long DFTs into short transforms using Bluestein’s method and Cooley–Tukey over Fp0[i].The short-transform length is M0, with log M0 = O(log log n log log log n).Source: §9.4 · pp. 25–26
  • The argument performs 2t + 1 bivariate DFTs, and the bound (9.5) follows as in the proof of Theorem 6.4.Source: §9.4 · p. 27
  • For large n, log n0 = O(log log n log log log n), which yields a suitable iterated-exponential function for the bound.Source: §9.4 · p. 27
  • The proof of Theorem 1.2 follows from Theorem 9.6 and Proposition 5.3, analogously to the proof of Theorem 1.1.Source: §9.4 · p. 27
Loading 1407.3360v1…