The parallel evaluation of general arithmetic expressions
RP Brent - Journal of the ACM (JACM), 1974 - dl.acm.org
Journal of the ACM (JACM), 1974•dl.acm.org
It is shown that arithmetic expressions with n≥ 1 variables and constants; operations of
addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated
in time 4 log2 n+ 10 (n-1)/p using p≥ 1 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.
addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated
in time 4 log2 n+ 10 (n-1)/p using p≥ 1 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.
It is shown that arithmetic expressions with n ≥ 1 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 ≥ 1 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.
ACM Digital Library