Multiplication is the easiest nontrivial arithmetic function (Q1066671): Difference between revisions

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), multplication can be done with O(S(n)) Boolean operations, as well.