<p>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).</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.9226" rel="nofollow">Fast Multiplication And Its Applications</a>, Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)</p>

CC BY-SA 3.0
2014-06-02T18:19:52.403Z
The linked paper does not have pages 335 or 336. Perhaps you meant to link to a different file?
argentpepper
CC BY-SA 3.0
2014-06-02T18:43:13.490Z
oops! thx for tip. above version marked as draft. [this version](http://cr.yp.to/lineartime/multapps-20080515.pdf) with cited pg #s is maybe final?
vzn
CC BY-SA 3.0
2014-06-02T15:26:31.723Z
2014-06-02T18:48:42.627Z
2014-06-02T18:48:42.627Z
vzn
<p>What is the best result for the number of gates in a circuit multiplying two n-bit integers?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-01T07:22:37.793Z
are you looking for an arithmetic circuit or a boolean circuit ?
Suresh Venkat
CC BY-SA 3.0
2014-06-01T19:34:51.407Z
I am looking for a Boolean circuit.
Amir
CC BY-SA 3.0
2014-06-01T23:16:38.390Z
for the record what is the $O(n \log n)$ algorithm? wouldnt it use that many gates?
vzn
CC BY-SA 3.0
2014-06-02T04:01:58.587Z
I am pretty sure that no $O(n\log n)$ time algorithm is known, if you measure time as the number of bit operations.
Sasho Nikolov
CC BY-SA 3.0
2014-06-02T04:07:48.733Z
it looks like I made a mistake! There is no algorithm with $O(n\log n)$ for multiplication.
Amir
CC BY-SA 3.0
2014-06-02T04:23:10.007Z
yeah seemed like a mistake. anyway the best known algorithm seems to be [Schonage-Straussen](http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) which is impractical with a large constant and has one of the times you mention. another option is using the chinese remainder theorem with prime decompositions and adding exponents but then that makes addition logic slow.
vzn
CC BY-SA 3.0
2014-06-02T05:09:41.637Z
@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
CC BY-SA 3.0
2014-06-02T09:11:02.087Z
@SashoNikolov so your comment might be the answer to the question.
Suresh Venkat
CC BY-SA 3.0
2014-06-02T15:34:59.043Z
re Schönhage–Strassen impracticality, that is asserted by Savage in [Models of computation](http://cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf) p67: "Although the coefficients on the size and depth
bounds are so large that their circuit is not practical..."
vzn
CC BY-SA 3.0
2014-06-02T19:52:21.087Z
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
CC BY-SA 3.0
2014-07-03T04:59:36.657Z
@RickyDemer You are right, there should be a constant in the exponent.
Sasho Nikolov
<cc.complexity-theory><circuit-complexity>
Fewest number of gates for Multiplication
Amir
# Fewest number of gates for Multiplication

(Asked by: username_0 on 2014-06-01)

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.

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: are you looking for an arithmetic circuit or a boolean circuit ?  
> **username_0**: I am looking for a Boolean circuit.  
> **username_2**: for the record what is the $O(n \log n)$ algorithm? wouldnt it use that many gates?  
> **username_3**: I am pretty sure that no $O(n\log n)$ time algorithm is known, if you measure time as the number of bit operations.  
> **username_0**: it looks like I made a mistake! There is no algorithm with $O(n\log n)$ for multiplication.  
> **username_2**: yeah seemed like a mistake. anyway the best known algorithm seems to be [Schonage-Straussen](http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) which is impractical with a large constant and has one of the times you mention. another option is using the chinese remainder theorem with prime decompositions and adding exponents but then that makes addition logic slow.  
> **username_3**: @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.  
> **username_1**: @SashoNikolov so your comment might be the answer to the question.  
> **username_2**: re Schönhage–Strassen impracticality, that is asserted by Savage in [Models of computation](http://cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf) p67: "Although the coefficients on the size and depth bounds are so large that their circuit is not practical..."  
> **username_4**: 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.  
> **username_3**: @RickyDemer You are right, there should be a constant in the exponent.  

---

## 1 answers

### Answer by username_2 on 2014-06-02. Score: 2

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.9226), Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)

> **Comments:**
> **username_5**: The linked paper does not have pages 335 or 336. Perhaps you meant to link to a different file?  
> **username_2**: oops! thx for tip. above version marked as draft. [this version](http://cr.yp.to/lineartime/multapps-20080515.pdf) with cited pg #s is maybe final?  

---

