20
$\begingroup$

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!

$\endgroup$
  • 1
    $\begingroup$ Are you interested in the theoretical question or in the practical question? $\endgroup$ – Yuval Filmus Oct 19 '13 at 20:03
  • $\begingroup$ Both, but more inclined towards practical one! $\endgroup$ – Andy Oct 20 '13 at 6:49
  • 1
    $\begingroup$ For the practical question, I recommend using GMP. If you're curious what they use, look at the documentation or the source code. $\endgroup$ – Yuval Filmus Oct 20 '13 at 8:04
  • $\begingroup$ Nobody knows. We haven't found it yet. $\endgroup$ – JeffE Oct 21 '13 at 2:55
22
$\begingroup$

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

  1. Fürer's algorithm
  2. FFT based multiplication of large numbers
  3. Fast Fourier transform
  4. Toom–Cook multiplication
  5. Schönhage–Strassen algorithm
  6. Karatsuba algorithm
$\endgroup$
9
$\begingroup$

Note that the FFT algorithms listed by avi add a large constant, making them impractical for numbers less than thousands+ bits.

In addition to that list, there are some other interesting algorithms, and open questions:

  • Linear time multiplication on a RAM model (with precomputation)
  • Multiplication by a Constant is Sublinear (PDF) - this means a sublinear number of additions which gets for a total of $\mathcal{O}\left(\frac {n^2} {\log n} \right)$ bit complexity. This is essentially equivalent to long multiplication (where you shift/add based on the number of $1$s in the lower number), which is $\mathcal{O}\left({n^2} \right)$, but with an $\mathcal{O}\left(\log n\right)$ speedup.
  • Residue number system and other representations of numbers; multiplication is almost linear time. The downside is, the multiplication is modular and {overflow detection, parity, magnitude comparison} are all as hard or almost as hard as converting the number back to binary or similar representation and doing the traditional comparison; this conversion is at least as bad as traditional multiplication (at the moment, AFAIK).
    • Other Representations:
      • [Logarithmic representation]: multiplication is addition of the logarithmic representation. Example: $$ 16 \times 32 = 2^{\log_2 16 + \log_2 32} = 2^{4+5} = 2^{9} $$
        • Downside is conversion to and from logarithmic representation can be as hard as multiplication or harder, the representation can also be fractional/irrational/approximate etc. Other operations (addition?) are likely more difficult.
      • Canonical representation: represent the numbers as the exponents of the prime factorization. Multiplication is addition of the exponents. Example: $$ 36 \times 48 = 3^2\cdot 5^1\times 2^{2}\cdot 3^1\cdot 4^1 = {2^2}\cdot {3^2} \cdot 4^1 \cdot 5^1 $$
      • Downside is, requires factors, or factorization, a much harder problem than multiplication. Other operations such as addition are likely very difficult.
$\endgroup$
  • 1
    $\begingroup$ I believe a residue/Chinese Remainder Theorem-based approach with the right moduli can lead to speedups over traditional multiplication even with the conversion back; at some point this was in chapter 4 of TAOCP, at least as a footnote. (It still doesn't get near the FFT-based methods, but it's an interesting historical note) $\endgroup$ – Steven Stadnicki Oct 20 '13 at 17:15
  • $\begingroup$ @StevenStadnicki oh cool, I need to look at that then; do you happen to know the complexity? $\endgroup$ – Realz Slaw Oct 20 '13 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.