25
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Are you interested in the theoretical question or in the practical question? $\endgroup$ Oct 19, 2013 at 20:03
  • $\begingroup$ Both, but more inclined towards practical one! $\endgroup$
    – Andy
    Oct 20, 2013 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$ Oct 20, 2013 at 8:04
  • 1
    $\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, 2020 at 12:53
  • 1
    $\begingroup$ To focus, how large is n? 100 digits and 10 million digits are different. $\endgroup$
    – gnasher729
    Aug 17 at 18:01

3 Answers 3

24
$\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$
5
  • 4
    $\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, 2019 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, 2020 at 10:53
  • $\begingroup$ @hardmath do you want to move that to an answer to get upvotes :-) $\endgroup$ Jul 22, 2020 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, 2020 at 19:26
  • 2
    $\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$ Jul 22, 2020 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.
$\endgroup$
2
  • 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$ Oct 20, 2013 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, 2013 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 full 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 realistically be done today for n = 256, but there isn’t that much demand.

Otherwise, for small n (let's say you have a computer with 64 bit arithmetic, and your numbers are less than 5 x 64 bits) the speed will change dramatically at certain sizes. For small sizes, you could perform Karatsuba by hand. And look how the number of operations changes very carefully. For example from 16x16 to 17x17 words there could be a massive change.

One source claims Karatsuba is fasted up to 10^96 (320 bits, 5 64-bit words). But I could see Toom-Cook being faster, calculating products of 3 128-bit quantities, and calculating the 128 bit products using Karatsuba. So for the fastest for small n, I'd expect many individual cases. Plus this would be very implementation dependent.

$\endgroup$
1
  • $\begingroup$ (FWIW, the tag is mathematical-programming, not digital-circuits.)(And I think 319+1 bit may have been 10*32 bits.) $\endgroup$
    – greybeard
    Aug 19 at 4:37

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.