Even Faster Integer Multiplication

(2014)

Abstract:

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

Authors:

David Harvey, Joris van der Hoevena, and Grgoire Lecerfb

Tags:

computer science, theory, Integer multiplication, algorithm, complexity bound, FFT

Length:

28

Submitted By:

alixander

Date Submitted:

Jul 15, 2014

Favorited:

0

Times Read:

0

Discussion and Questions