Multiplication is the easiest nontrivial arithmetic function

DOI10.1016/0304-3975(85)90051-9MaRDI QIDQ1066671zbMATH OpenOpenAlexFDO

Authors Helmut Alt

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90051-9

zbMATH Keywords

Boolean circuitBoolean operationsfixed point multiplicationinteger multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Comparing the combinational complexities of arithmetic functions
• On the multiplicative complexity of Boolean functions
• Shallow circuits and concise formulae for multiple addition and multiplication
• Faster integer multiplication
• Some notes on threshold circuits, and multiplication in depth 4

Cites work

• Fast Multiple-Precision Evaluation of Elementary Functions
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 3698378 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 619538 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 3365225 (Why is no real title available?)
• Multiplication is the easiest nontrivial arithmetic function
• Numerics of analytic functions and complexity
• On Relating Time and Space to Size and Depth
• On the computational power of pushdown automata

Cited in

(5)

• Multiplication is the easiest nontrivial arithmetic function
• Easy multiplications. I: The realm of Kleene's theorem
• A refined model of computation for continuous problems
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Comparing the combinational complexities of arithmetic functions

This page was built for publication: Multiplication is the easiest nontrivial arithmetic function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066671)