Thumbnail
Access Restriction
Subscribed

Author Sethi, Ravi ♦ Ullman, J. D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1970
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The problem of evaluating arithmetic expressions on a machine with $\textit{N}$ ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An algorithm for evaluation of expressions under this assumption is proposed, and it is shown to take the shortest possible number of instructions. It is then assumed that certain operators are commutative or both commutative and associative. In this case a procedure is given for finding an expression equivalent to a given one and having the shortest possible evaluation sequence. It is then shown that the algorithms presented here also minimize the number of storage references in the evaluation.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1970-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 17
Issue Number 4
Page Count 14
Starting Page 715
Ending Page 728


Open content in new tab

   Open content in new tab
Source: ACM Digital Library