New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions

ABSTR&CT. The parallel evaluation of rational expressions i considered. New algorithms which minimize the number of multiplication or divismn steps are given. T, hey are faster than the usual algorithms when multiplication or division takes more time than addition or subtraction. It is shown, for example, that x ~ can be evaluated in two steps of parallel division and flog2 nl steps of parallel addition, while the usual algorithm takes [log ~ nl steps of parallel multiphcation. Lower bounds on the time required are obtained in terms of the degree of the expressions to be evaluated. From these bounds, the algorithms presented in the paper are shown to be asymptotically optimal Moreover, it is shown that by using parallelism the evaluation of any first-order ational recurrence of degree greater than 1, e.g. y,+l = (y, • a/y,), and any nonlinear polynomial recur-rence can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is. KEY woRns ANn PHRASES: parallel algorithms, lower bounds, parallel evaluation, rational expres-sions, recurrence proble