The area-time complexity of binary multiplication

55. R. P. Brent and H. T. Kung, The area-time complexity of binary multiplication, Journal of the ACM 28 (1981), 521-534. CR 22#38242, MR 82i:68027. Corrigendum: ibid 29 (1982), 904. MR 83j:68046.

Abstract: dvi (5K), pdf (108K), ps (36K).

Paper: pdf (698K).

Corrigendum: pdf (33K).

Abstract

The problem of performing multiplication of n-bit numbers on a chip is considered. Let A denote the chip area and T the time required to perform multiplication. By using a model of computation which is a realistic approximation to current and anticipated LSI or VLSI technology, it is shown that

AT > c1n3/2     and     AT2 > c2n2,

where c1 and c2 are positive constants which depend on the technology but are independent of n. The exponents 3/2 and 2 are best possible. (In fact more a more general result is established: see the dvi, pdf or ps version of the abstract for details.)

A consequence of the results is that binary multiplication is "harder" than binary addition, in the sense that the area-time complexity of n-bit binary multiplication is asymptotically greater than that of n-bit binary addition.

Comments

Similar results for the AT2 measure were obtained independently by Abelson and Andreae [Communications of the ACM 23 (1980), 20-23], using a more restrictive model than ours.

A preliminary version, which contains some additional material on upper bounds, appeared as Brent and Kung [53]. For an extension of the results to problems with only a 1-bit output, see Brent and Goldschlager  [64, 85].

As pointed out in the corrigendum, the conjecture made on page 528 of the paper is false. This follows from a result of Erdős [Leningrad Universitet Vestnik (Matematika, Mekhanika, Astronomiia) 15 (1960), 41-49]. For details see the dvi, pdf or ps version of the abstract. We thank P. Erdős, D. J. Newman, A. M. Odlyzko and C. Pomerance for bringing the result of Erdős to our attention. Fortunately, none of the results of the paper depend on the conjecture.

An improvement on the result of Erdős has been given by Ford, Annals of Mathematics 168 (2008), 367-433, or arXiv:math/0401223 (see in particular Corollary 3).

Note that in our paper log denotes the logarithm to base 2, and ln is used for the natural logarithm. In the references cited above, log generally denotes the natural logarithm.

For additional references, see OEIS A027424.

For additional values of mu(2n), see OEIS A027417.

For a 2012 talk on the asymptotics of the function mu(n) (using slightly different notation, mu(n) is called M(n)), click here.

Go to next publication

Return to Richard Brent's index page