## The area-time complexity of binary multiplication

55. 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.
Abstract:
dvi (5K),
pdf (108K),
ps (36K).

Paper:
pdf (698K).

Corrigendum:
pdf (33K).

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

*AT* > *c*_{1}*n*^{3/2}
and
*AT*^{2} > *c*_{2}*n*^{2},
where *c*_{1} and *c*_{2}
are positive constants
which depend on the technology but are independent of *n*.
The exponents 3/2 and 2 are best possible.
(In fact more a more general result is established: see the
dvi,
pdf or
ps
version of the abstract for details.)

A consequence of the
results is that binary multiplication is "harder" than binary addition,
in the sense that the area-time complexity of
*n*-bit binary multiplication is asymptotically greater than
that of *n*-bit binary addition.

## 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.
A preliminary version, which contains some additional material
on upper bounds, appeared as
Brent and Kung [53].
For an extension of the results to problems with only a 1-bit output,
see Brent and Goldschlager
[64,
85].

As pointed out in the corrigendum, the conjecture made on page 528 of
the paper is false. This follows from a result of
Erdős
[*Leningrad Universitet Vestnik (Matematika, Mekhanika, Astronomiia)*
15 (1960), 41-49].
For details see the
dvi,
pdf or
ps version of the abstract.
We thank P. Erdős, D. J. Newman, A. M. Odlyzko
and C. Pomerance for
bringing the result of Erdős to our attention.
Fortunately, none of the results of the paper depend on
the conjecture.

An improvement on the result of Erdős has been given by Ford,
*Annals of Mathematics* 168 (2008), 367-433,
or arXiv:math/0401223
(see in particular Corollary 3).

Note that in our paper *log* denotes the logarithm to base 2,
and *ln* is used for the natural logarithm. In the references
cited above, *log* generally denotes the natural logarithm.

For additional references, see
OEIS A027424.

For additional values of mu(2^{n}), see
OEIS A027417.

For a 2012 talk on the asymptotics of the function mu(n)
(using slightly different notation, mu(n) is called M(n)), click
here.

Go to next publication

Return to Richard Brent's index page