The Area-Time Complexity of Binary Multiplication,
Abstract
We consider the problem of performing multiplication of n-bit binary numbers on a chip. Let A denote the chip area, and T the time required to perform multiplication. Using a model of computation which is a realistic approximation to current and anticipated VLSI technology, we show that (A/A sub 0) (T/T sub 0) to the 2 alpha power > or = n to the (1 + alpha) power for all alpha is an element (0, 1), where A sub 0 and T sub 0 are positive constants which depend on the technology but are independent of n. The exponent 1 + alpha is the best possible. A consequence is that binary multiplication is 'harder' than binary addition if AT to the 2 alpha power is used as a complexity measure for any alpha > or = 0. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1979
- Accession Number
- ADA082388
Entities
People
- H. T. Kung
- R. P. Brent
Organizations
- Carnegie Mellon University