An algorithm for coding efficient arithmetic operations

Robert W. Floyd · Communications of the ACM · 1961

Most existing formula transbttion schemes yield inefficient coding.A method is described which reduces the mmfl)er of store and fetch operai>ions, evaluates constant subexpressions during compilation, t~tl([ recognizes m~my equiwdent subexpressions.Most previously published algorithms for formula translation depend uport a left-to-right scan of the formula, during which each symbol encountered either causes generation of coding or is saved on a list until it can be correctly interpreted in context.An exception is the GAT translator, which scans from right to left.In coding arithmetic operators for machines with accumulators (i.e., oneor two-address machines), right-to-left scans potcntiMly generate more efficient eoding than left-to-right scans.The reason can be seen by considering the formula x := (u 0~ v)/(y 0~ z), where the O's a.re orbit,tory arithmetic operators, each innplemented by a single machine instruction.The symbolic coding for a typical one-~Mdress machine generated by both Iypes of scan is shown t)elow: Left4o-right Right-to-left CLA u CLA y 0~ v 02 z STR Tt STR T1 CLAy CLA u 0,., z 0, v

Cited by 29 works. doi:10.1145/366062.366082 Open-access PDF

Authors

References