The Parallel Evaluation of Arithmetic Expressions Without Division

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<inf>2</inf>n + 0(1) steps if sufficiently many processors are available. We then improve this result and reduce 3 log<inf>2</inf>n to 2.465 log<inf>2</inf>n. Finally, we deduce some results that apply when a fixed number of processors are available. Copyright © 1973 by The Institute of Electrical and Electronics Engineers, Inc.