The graph-theoretical models of this paper can be used to compare the rounding error behavior of numerical programs The models follow the approach, popularized by Wilkinson, of assuming independent rounding errors at each arithmetic operation Models constructed on th~s assumpuon are more tractable than would be the case under more realistic assumptions There are identified two easily tested condmons on programs which guarantee that" error analyses are relatively lnsensmve to the particular graph model employed The development has the addmonal benefit of sometimes providing an elementary proof that one program is comparable in stablhty to another Examples of such results are gwen KEY WORDS AND PHRASES rounding errors, numerical stability, arithmetic graphs CR CATEGORIES 5 11, 5 14In order to represent programs as "arithmetic graphs," we restrict attention to straight-

In one iteration, Chen's algorithm for evaluating exponentials and logarithms advances by 2 bits on the average, yet may not advance at all. Analysis reveals that the no-advance situation actually paves the way for sizable advance in the next iteration, and the guaranteed advance, after a one iteration overhead, is one bit per iteration. Two new schemes raise the guaranteed advance to 1.5 bits per iteration, after a two-iteration overhead, while maintaining the original requirement of one stored constant per operand bit. Adopting as a figure of merit the following quantity Q = advance per iteration/memory words per operand bit for the steady-state iterations, the new schemes appears to be better than other methods heretofore proposed.

A class of languages RUD derived from the class of rudimentary relations is studied. Two characterizations of RUD are established, one using linear-time relative computation and the other using language-theoretic operations. Also, some connections between RUD and classes of languages defined by resource-bounded Turing machines are given.