3 ms·
The abstract of this paper is refreshingly succinct: We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations. The
by throwawaymath 8y ago
The abstract of this paper is refreshingly succinct:
We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations.
The result is excellent, and it closes (in the affirmative) the Schonhage-Strassen conjecture first postulated in 1971.
- hackcasual 8y agoIt establishes the upper bound, but I don't believe this paper establishes a lower bound, so the conjecture is still open (a super linear lower bound would violate the conjecture).
- deleted 8y ago[deleted]
- rincebrain 8y agoJust to be sure I understand, doesn't the conjecture postulate that O(n log n) is the lower bound, so _anything_ beneath n log n would violate it?
- lovecg 8y agoYes (technically the lower bound would be the small-o(n log n)). The conjecture is that it’s possible to do in O(n log n) time, which this paper proves, and that it’s not possible to do any faster (which is still an open problem).
- throwawaymath 8y agoYou make a good point, nice catch. Technically we don't know what the fastest possible algorithm is yet.