HackerPapers

arXiv:1407.3360cs.CC

Even faster integer multiplication

David Harvey, Joris van der Hoeven, Grégoire Lecerf

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that the new algorithm is faster than Fürer's by a factor of 2^(log^* n). Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.SCSymbolic Computation math.NTNumber Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Sep 2015 to Sep 2015. Found in 1 HN submission from Jul 2014 to Jul 2014. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. How to multiply polynomials in Θ(n log n) time 1 comment

    • The best complexity these days [1] is essentially n log n. More precisely, O( n log n 8^(log* n) ), where log* is the extremely slow-growing iterated logarithm. The original Schönhage-Strassen algorithm is O(n log n log log n). [1] http://arxiv.org/abs/1407.3360

      pbsdView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.