Multiplication Is the Easiest Nontrivial Arithmetic Function

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.

Authors

• Helmut Alt

Keywords

• Circuits
• Size measurement
• Digital arithmetic
• Computer science
• Convergence
• Polynomials
• Exponential Function
• Real Numbers
• Functional Class
• Complexity Measures
• Boolean Operators
• Newton Method
• Iteration Step
• Rational Function
• Circuit Size
• Iterative Formula
• Algebraic Function