Integer multiplication below n log n
There is one deterministic Turing machine , with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, that computes the exact -bit product of any two -bit integers for every in worst-case time with , refuting an eventual lower bound in this model.
The proof is complete and rigorous: all parameter inequalities in Section 9.1-9.2 hold, the error analysis in Section 9.7 bounds the final error strictly below , and every term in Table 1 has exponent at most , yielding .
“Theorem 1. There is one deterministic Turing machine A, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, that computes this exact product for every n ≥ 1 and every pair of n-bit inputs. Its worst-case running time satisfies TA(n) = O(n(lg n)^{1-κ}), κ = 2^{-182}.” · Show in paper