The chip complexity of binary arithmetic
Richard P. Brent, H. T. Kung · 1980
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α,for α ≥ 0, is used as a complexity measure. A particular value of α, which is chosen by the user, reflects the relative importance between A and T. This paper derives lower and upper 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.