The parallel evaluation of general arithmetic expressions

22. R. P. Brent, The parallel evaluation of general arithmetic expressions, J. ACM 21 (1974), 201-206. CR 15#27055, MR 58#31996.

Abstract: dvi (2K), pdf (80K).

Paper: pdf (387K).


It is shown that arithmetic expressions with n variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log2n + 10(n-1)/p using p processors which can independently perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without the division operation, and the question of numerical stability is discussed.


The main result is the best possible, up to small constant factors. For related results see [15, 18, 38].

Lemma 2 of the paper is a simple but useful simulation result, sometimes called ``Brent's lemma'', which allows us to deduce time bounds for parallel computations with a limited number of processors by counting the operations performed on a parallel machine with an unlimited number of processors.

Lemma 2 (Brent's Lemma)

If a computation can be performed in t steps with q operations on a parallel computer (formally, a PRAM) with an unbounded number of processors, then the computation can be performed in t + (q-t)/p steps with p processors.

Go to next publication

Return to Richard Brent's index page