Multiplication is the easiest nontrivial arithmetic function

It is shown that fixed point multiplication can be reduced to the evaluation of any member 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 a Boolean circuit of size S(n), multiplication can be done with O(S(n)) Boolean operations, as well.

Authors

• Helmut Alt

Keywords

No keywords are indexed for this paper.