Multiplication is the easiest nontrivial arithmetic function
type: Item
instance of: scholarly article
title: Multiplication is the easiest nontrivial arithmetic function
zbMATH Open document ID: 0578.68034
DOI: 10.1016/0304-3975(85)90051-9
author: Helmut Alt
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 3926240
zbMATH Keywords: integer multiplication
zbMATH Keywords: fixed point multiplication
zbMATH Keywords: Boolean circuit
zbMATH Keywords: Boolean operations
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90051-9
OpenAlex ID: W2003165068
cites work: On the computational power of pushdown automata
cites work: Q3891763
cites work: Fast Multiple-Precision Evaluation of Elementary Functions
cites work: Q4302459
cites work: Q4190138
cites work: On Relating Time and Space to Size and Depth
cites work: Q5638290
cites work: Q5585021
cites work: Numerics of analytic functions and complexity
cites work: Fast multiplication of large numbers
description: scientific article; zbMATH DE number 3926240