Integer multiplication below n log n
Source: github.com/openai/math/tree/main/preprints/Integer-multipli…
We give a deterministic algorithm that multiplies two n -bit integers in $O(n(\lg n)^{1-\kappa})$ worst-case time, with $\kappa=2^{-182}$, on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the $n\log n$ optimality conjecture of Schönhage and Strassen in this model.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Integer-multiplication-below-n-log-n
curl -X POST /api/v1/records/openai-math/Integer-multiplication-below-n-log-n/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Integer-multiplication-below-n-log-n/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
When is it plausible that a result is optimal?blog.computationalcomplexity.orgBill Gasarch
INT MULT Improved Algorithms for Integer Multiplication of two \(n\)-bit numbers. In 1971 Schonhage and Strassen conjectured that there is an algorithm for integer multiplication that takes \(O(n\log n)\) bit operations. In 2019, Harvey and van der Hoeven proved this conjecture. Is there an…