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.

  • 1
    $\begingroup$ are you looking for an arithmetic circuit or a boolean circuit ? $\endgroup$ – Suresh Venkat Jun 1 '14 at 7:22
  • 1
    $\begingroup$ I am looking for a Boolean circuit. $\endgroup$ – Amir Jun 1 '14 at 19:34
  • $\begingroup$ for the record what is the $O(n \log n)$ algorithm? wouldnt it use that many gates? $\endgroup$ – vzn Jun 1 '14 at 23:16
  • 3
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Jun 2 '14 at 5:09
  • 4
    $\begingroup$ 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. $\endgroup$ – Kaveh Jun 2 '14 at 19:52

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)

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

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.