DocumentCode
2181996
Title
Multiplication is the easiest nontrivial arithmetic function
Author
Alt, Helmut
fYear
1983
fDate
7-9 Nov. 1983
Firstpage
320
Lastpage
322
Abstract
It is shown that floating point (or integer) multiplication can be reduced to the evalution of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by boolean circuits of size S(n), then multiplication can be done with circuits of size O(S(n)). as well.
Keywords
Circuits; Computer science; Convergence; Digital arithmetic; Polynomials; Size measurement;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location
Tucson, AZ, USA
ISSN
0272-5428
Print_ISBN
0-8186-0508-1
Type
conf
DOI
10.1109/SFCS.1983.36
Filename
4568094
Link To Document