Motivation
Every fast integer-multiplication algorithm in the literature is stated for the multitape Turing machine. The algorithms are built from a small set of standard subroutines whose costs are usually quoted as "well known":
- linear-time addition;
- sorting by merging on tapes;
- fast matrix transposition;
- a crude O(n1+δ) multiplier, used for the small multiplications inside fixed-point arithmetic.
Harvey–van der Hoeven (2021) use all of these in §2.1, §2.3 and §4–§5 of their O(nlogn) paper. They cite Brent–Zimmermann for the arithmetic, Knuth vol. 3 for merge sort, and Bostan–Gaudry–Schost for transposition.
This mission formalizes that toolkit in the shared machine model IntMul_MultitapeModel. Its goal is the classical Schönhage–Strassen bound M(n)=O(nlognloglogn). The toolkit is exactly what is missing before the recursive step of the companion mission, Harvey–van der Hoeven Proposition 5.4, can be decomposed. Proposition 5.4 is the last open link on that mission's main line.
Timeline (multitape Turing model).
- Folklore: schoolbook multiplication in O(n2); addition in O(n).
- 1962: Karatsuba–Ofman, O(nlog23).
- 1963–1966: Toom and Cook, O(n1+ϵ) for every ϵ>0.
- 1971: Schönhage–Strassen, O(nlognloglogn).
- 1973 (2nd ed. 1998): Knuth, TAOCP vol. 3 §5.4, merge sorting on tapes.
- 2007: Bostan–Gaudry–Schost, Appendix: transposing an m×k matrix with N bits in total in O(Nlogmin(m,k)) on a multitape machine.
- 2019/2021: Harvey–van der Hoeven, O(nlogn), using all of the above.
Setting
The machine model, input and output conventions, and the time-bound predicate MulTimeBound are those of IntMul_MultitapeModel. That model follows Montanaro's lecture notes:
- k≥2 one-way tapes, with a read-only input tape and a separate output tape;
- ▹ appears only in cell 0 of each tape;
- START=HALT, and the halting state freezes the configuration.
For subroutines whose input is not of the form x#y, the new definitions file IntMul_MultitapeWords starts the machine on an arbitrary word over {0,1,#}. It also provides the encodings
- bits(x), a bit string written as a word;
- u1#u2#⋯#um, a list of words joined by separators.
Formalization targets
Goal: Schönhage–Strassen
MulTimeBound(n↦nlnnlnlnn): a single multitape machine multiplies n-bit integers for every n≥1 in worst-case time O(nlognloglogn).
Milestones
- Schoolbook multiplication: MulTimeBound(n2).
- Karatsuba–Ofman: MulTimeBound(nlog23).
- Linear-time addition: on input x#y with ∣x∣=∣y∣=n, output binn+1(valx+valy) within c(n+1) steps.
- Merge sort on tapes:
- Input: m records, each a key of ℓ bits and a payload of q bits, written as k1#p1#k2#p2#⋯.
- Output: the records stably sorted by key value, in the same format.
- Time: c(N+1)(⌈log2m⌉+1), where N is the input length.
- Matrix transposition:
- Input: an m×k matrix (m,k≥1) with entries of ℓ≥1 bits, in row-major order. Entries are separated by # and rows by ##.
- Output: the transpose, in the same format.
- Time: c(N+1)(⌈log2min(m,k)⌉+1).
Formalization scope
Constants may depend only on the machine. All time bounds count exact steps of one fixed machine in the shared model. Building machines by composing smaller ones (subroutine calls, scratch tapes, recursion) is the solvers' business; any reusable infrastructure for it is welcome as published lemmas.
Selected references
- A. Schönhage, V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281–292.
- A. Karatsuba, Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady 7 (1963), 595–596.
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §5.4.
- A. Bostan, P. Gaudry, É. Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier–Manin operator, SIAM J. Comput. 36 (2007), 1777–1806, Appendix.
- R. P. Brent, P. Zimmermann, Modern Computer Arithmetic, Cambridge University Press, 2011, Ch. 1.
- D. Harvey, J. van der Hoeven, Integer multiplication in time O(nlogn), Ann. of Math. 193 (2021), §2.1.
- A. Montanaro, Computational Complexity, lecture notes, §3–§4.