The Area-Time Complexity of Binary Multiplication
Richard P. Brent, H. T. Kung · Journal of the ACM · 1981
The problem of performing multtphcaUon of n-bit binary numbers on a chip is considered Let A denote the ch~p area and T the time reqmred to perform mult~phcation.By using a model of computation which is a realistic approx~mauon to current and anucipated LSI or VLSI technology, ~t is shown thatfor all a ~ [0, 1], where A0 and To are posmve constants which depend on the technology but are mdependent of n.The exponent 1 + a is the best possible A consequence of this result is that binary multiphcatlon is "harder" than binary addmon More precisely, ff(AT2~)M(n) and (AT2~)A(n) denote the mmimum area-time complexity for n-b~t binary multiphcauon and addmon, respectively, then (AT2~)M(n) _ 1 f~(nl-a) for 0 _ 0).