## The Parallel Evaluation of Arithmetic Expressions Without Division

15. R. P. Brent,
D. J. Kuck
and K. Maruyama,
The parallel evaluation of arithmetic expressions without division,
* IEEE Transactions on Computers* C-22 (1973), 532-534.
MR 50#11843.
Abstract:
dvi (2K),
pdf (77K).

Paper:
pdf (536K).

## Abstract

As computers become capable of executing more arithmetic
operations simultaneously, the question of compiling for such
machines becomes more important.
In this correspondence we consider arbitrary arithmetic expressions
of *n* distinct variables with operations restricted to addition,
subtraction, and multiplication. We first construct a scheme whereby
any such expression can be evaluated in at most
3 log_{2}*n* + O(1)
steps if sufficiently many processors are available. We then improve
this result and reduce
3 log_{2}*n*
to 2.465 log_{2}*n*. Finally, we
deduce some results that apply when a fixed number of processors
is available.
## Comment

The result was improved (if the number of processors is limited)
and generalised in
[18], [22].
Go to next publication

Return to Richard Brent's index page