Abstract: dvi (5K), pdf (108K), ps (36K).
Paper: pdf (698K).
Corrigendum: pdf (33K).
where c1 and c2 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.
A preliminary version, which contains some additional material on upper bounds, appeared as Brent and Kung . 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(2n), 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