On the time required to parse an arithmetic
statement for parallel processing
38. R. Towle and R. P. Brent,
On the time required to parse an arithmetic
statement for parallel processing,
Proceedings of the 1976
International Conference on Parallel Processing
(edited by P.H. Enslow),
IEEE, New York, 1976, 254.
Paper: pdf (74K).
Abstract
This paper announces a result on the time required to parse an
arithmetic expression (containing N tokens)
using the associative, commutative and distributive
laws valid over a ring. Upper bounds on the time required for
Beatty's algorithm
[J. ACM 21 (1974), 613-640] and for
Brent's algorithm [22] are given.
The use of the associative and commutative laws adds O(N) time to
the parsing process, and the use of all three laws
adds O(N log N) time.
Comment
Further details are given in Ross Towle's thesis,
Control and data dependence for program transformations,
Dept. of Computer Science, University of Illinois at Urbana-Champaign,
UIUCDCS-R-76-788, March 1976, 113 pp.
Go to next publication
Return to Richard Brent's index page