## 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).

## Abstract

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 *AT*^{alpha},
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.
## Comments

Similar results for the *AT*^{2} 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