THE AREA-TIME COMPLEXITY OF BINARY MULTIPLICATION

R. P. BRENT AND H. T. KUNG

Abstract

The problem of performing multiplication of n-bit numbers on a chip is considered. Let A denote the chip area and T the time required to perform multiplication. By using a model of computation which is a realistic approximation to current and anticipated LSI or VLSI technology, it is shown that

(\frac{A}{A_{0}} ) (\frac{T}{T_{0}} )^{2α} ≥ n^{1+α}

for all α ∈ [0, 1], where A_{0} and T_{0} are positive constants which depend on the technology but are independent of n. The exponent 1 + α is the best possible. A consequence of this result is that binary multiplication is “harder” than binary addition. More precisely, if (AT^{2α})_{M}(n) and (AT^{2α})_{A}(n) denote the minimum area-time complexity for n-bit binary multiplication and addition, respectively, then

\frac{(AT^{2α})_{M}(n)}{(AT^{2α})_{A}(n)} = \begin{cases}Ω(n^{1−α}) & for 0 ≤ α ≤ 1/2 \\ Ω(n^{α}/ log^{2α} n) & for 1/2 < α ≤ 1 \\ Ω(n/ log^{2α} n) & for α > 1 \end{cases}

= Ω(n^{1/2}) for all α ≥ 0.

1991 Mathematics Subject Classification. Primary 68Q35; Secondary 65Y05, 68M07, 68Q25. Key words and phrases. Area-time complexity, binary multiplication, chip design, chip layout, circuit design,

combinational logic, chip complexity, lower bounds, VLSI.

CR Categories. 5.25, 6.1, 6.32. Received August 1979; revised March 1980; accepted April 1980. This research was supported in part by the National Science Foundation under Grant MCS 78-236-76 and

the Office of Naval Research under Contracts N00014-76-C-0370 and N00014-80-C-0236. Most of this work was carried out at the Australian National University while H. T. Kung was there as a Visiting Fellow during May 1979.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1981, ACM. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb055a typeset using AMS-L^{A}TEX.

Comments

Only the Abstract is given here. The full paper appeared as [3]. Similar results for the case α = 1 were obtained independently by Abelson and Andreae [1] (using a more restrictive model than ours). A preliminary version, which contains some additional material on upper bounds, appeared as [2]. For an extension of the results to problems with only a 1-bit output, see [4].

Let

μ(N) = |{ij | 0 ≤ i < N, 0 ≤ j < N}|

be the number of distinct products of nonnegative integers each less than N. As pointed out in the Corrigendum to [3], our conjecture [3, page 528] that

lim_{N→∞} \frac{μ(N) log_{2} log N}{N^{2}} = 1

is false. In fact, it follows from a result of Pál Erdős [5] that

μ(N) = \frac{N^{2}}{(log N)^{c+o(1)}} ,

where

c = 1 − (1 + ln ln 2)/ ln 2 ≃ 0.086.

Fortunately, none of the results of [3] depend on the conjecture.

Acknowledgement. We thank P. Erdős, D. J. Newman, A. M. Odlyzko and C. Pomerance for bringing the result [5] to our attention.

References

[1] H. Abelson and P. Andreae, “Information transfer and area-time trade-offs for VLSI multiplication”, Communications of the ACM 23 (1980), 20–23.

[2] R. P. Brent and H. T. Kung, “The chip complexity of binary arithmetic” Proc. Twelfth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1980, 190–200. rpb053.

[3] R. P. Brent and H. T. Kung, “The area-time complexity of binary multiplication”, Journal of the ACM 28 (1981), 521–534. CR 22#38242, MR 82i:68027. Corrigendum: ibid 29 (1982), 904. MR 83j:68046. Also appeared as Report TR-CS-79-05, Department of Computer Science, ANU; and as Report TR CMU-CS-79-136, Department of Computer Science, CMU (July 1979), 25 pp. rpb055.

[4] R. P. Brent and L. M. Goldschlager, “Some area-time tradeoffs for VLSI”, SIAM J. on Computing 11 (1982), 737–747. MR 83k:68024. rpb064.

[5] P. Erdős, Leningrad Universitet Vestnik (Matematika, Mekhanika, Astronomiia) 15 (1960), 41–49.

(Brent) Department of Computer Science, Australian National University, Canberra

(Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh