# Fewest number of gates for Multiplication

What is the best result for the number of gates in a circuit multiplying two n-bit integers?

The obvious method generates $\theta(n^2)$ gates. There are better approaches with $\theta(n\log n \log\log n)$ and $\theta(n\log n2^{\log^*(n)})$ gates.

I could not find any Boolean circuit family which can handle multiplication with $n\log n$ gates. I wonder if such a family of circuits exists.

• are you looking for an arithmetic circuit or a boolean circuit ? – Suresh Venkat Jun 1 '14 at 7:22
• I am looking for a Boolean circuit. – Amir Jun 1 '14 at 19:34
• for the record what is the $O(n \log n)$ algorithm? wouldnt it use that many gates? – vzn Jun 1 '14 at 23:16
• @vzn No, Martin Fuerer's algorithm is the best known, and it does give a circuit with $O(n\log n 2^{\log^* n})$ gates. Schonhage-Strassen is actually used in some computer algebra systems for very large numbers. – Sasho Nikolov Jun 2 '14 at 5:09
• There is some overhead to turn a TM to a circuit. A time $t(n)$ algorithm doors not give a circuit with $t(n)$ gates. The general translation cannot be better than the circuit complexity of the circuit value problem. On the other hand, the best uniform complexity does not imply a lower bound on circuit complexity as there is overhead also in the reverse direction, i.e. there can be circuits of size $O(n\lg n)$ even if there is no TM with that running time for multiplication. – Kaveh Jun 2 '14 at 19:52

## 1 Answer

Below is a detailed 2008 survey that covers top theoretical algorithms for multiplication, including the ones discussed in the comments to your question (including the Schönhage–Strassen algorithm and the $O(n\log n \, 2^{\log^* n})$ Fuerer algorithm, see page 335 of survey). However, implementation is a different matter and some of these algorithms may not be considered practical; the survey does not cover practical implementations. Although the survey includes algorithms for polynomials, power series, real numbers, and 2-adic numbers, integers are a special case of these (see Figure 1 on page 336).

Fast Multiplication And Its Applications, Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)

• The linked paper does not have pages 335 or 336. Perhaps you meant to link to a different file? – argentpepper Jun 2 '14 at 18:19
• oops! thx for tip. above version marked as draft. this version with cited pg #s is maybe final? – vzn Jun 2 '14 at 18:43
• @vzn : $\:$ Even that paper has a big-O around the $\log^*(n)$. $\;\;\;\;$ – user6973 Jul 3 '14 at 6:59