Integer multiplication below n log n
One deterministic fixed-finite-tape Turing machine outputs the exact product of every pair of n-bit inputs in worst-case O(n(lg n)^(1−κ)), κ=2^-182.
Proof overview availableThe catalogue guide leads to the article, its external inputs, and the bilingual PDF editions.
Open the catalogue guide