23
$\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
  • 2
    $\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
  • $\begingroup$ It depends. If you are satisfied with an algorithm that can multiply only a very specific class of numbers, look at this algorithm that can multiply two $n$-bit numbers in $O(kn)$, where $k$ related to the Collatz problem. $\endgroup$ – DaBler May 20 at 12:53
23
$\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
| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Note the recent paper by D. Harvey and J. van der Hoeven (March 2019) describing an algorithm with $O(n\ln n)$ complexity. $\endgroup$ – hardmath Apr 28 '19 at 19:32
  • $\begingroup$ Karatsuba is really easy mathematically, just one simple formula. Also nice to distribute to multiple processors and to vectorise. $\endgroup$ – gnasher729 Feb 19 at 10:53
  • $\begingroup$ @hardmath do you want to move that to an answer to get upvotes :-) $\endgroup$ – Ciro Santilli 郝海东冠状病六四事件法轮功 Jul 22 at 19:05
  • 1
    $\begingroup$ @Ciro: There's a Question about the practical effects of this at MatterModeling.SE (a beta site I was unaware of) and one of the Answers is quite a good explanation of how large the numbers have to be to get an improvement. $\endgroup$ – hardmath Jul 22 at 19:26
  • 1
    $\begingroup$ @hardmath OMG, that site is so obscure, should at most be a tag on chemistry or physics. In any case, I still recommend dumping the link to the paper and quick summary. Doesn't matter if useless in practice, paper itself says authors didn't care about being useful in practice. This is Computer Science SE, doesn't have to be useful :-) $\endgroup$ – Ciro Santilli 郝海东冠状病六四事件法轮功 Jul 22 at 19:32
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.
| cite | improve this answer | |
$\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
0
$\begingroup$

If space and amount of hardware is no concern, then you can do what most CPUs do: For two n-bit numbers, use n^2 AND gates to produce n^2 zeroes and ones, then use n^2 half adders to reduce the number of values by 1/3, do that again until you can get the final result with one set of full adders.

Time = O(log n), hardware cost = O(n^2). Could realistybe done today for n= 256, but there isn’t that much demand.

| cite | improve this answer | |
$\endgroup$

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.