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.

Go to next publication

Return to Richard Brent's index page