### Comparing the combinational complexities of arithmetic functionsComparing the combinational complexities of arithmetic functions

Access Restriction
Subscribed

 Author Alt, Helmut Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1988 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Methods are presented for finding reductions between the computations of certain arithmetic functions that preserve asymptotic Boolean complexities (circuit depth or size). They can be used to show, for example, that all nonlinear algebraic functions are as difficult as integer multiplication with respect to circuit size. As a consequence, any lower or upper bound (e.g., $\textit{O}(\textit{n}$ log $\textit{n}$ log log $\textit{n}))$ for one of them applies to the whole class. It is also shown that, with respect to depth and size simultaneously, multiplication is reducible to any nonlinear and division to any nonpolynomial algebraic function. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1988-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 35 Issue Number 2 Page Count 14 Starting Page 447 Ending Page 460

#### Open content in new tab

Source: ACM Digital Library