The chip complexity of binary arithmetic

53. R. P. Brent and H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the Twelfth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1980, 190-200.

Abstract: dvi (3K), pdf (80K).

Paper: pdf (675K).


The chip complexity of a computation is concerned with the chip area A, and the time T, required to perform the computation when implemented on a chip. An area-time product ATalpha, for non-negative alpha, is used as a complexity measure. A particular value of alpha can be chosen to reflect the relative importance of A and T. We give both upper and lower bounds on the area-time complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate current and anticipated LSI or VLSI technology.


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.

Bounds for binary multiplication are also considered in Brent and Kung [55]. The upper bound for binary addition is considered in more detail in Brent and Kung [60].

For an extension of the results to problems with only a 1-bit output, see Brent and Goldschlager [64].

Go to next publication

Return to Richard Brent's index page