EVALUATING RATIONAL FUNCTIONS - INFINITE PRECISION IS FINITE COST AND TRACTABLE ON AVERAGE

If one is interested in the computational complexity of problems whose natural domain of discourse is the reals, then one is led to ask: what is the 'cost' of obtaining solutions to within a prescribed absolute accuracy epsilon equals 1/2**s (or precision s equals minus log//2 epsilon )? The loss of precision intrinsic to solving a problem, independent of method of solution, gives a lower bound on the cost. It also indicates how realistic it is to assume that basic (arithmetic) operations are exact and/or take one step for complexity analyses. For the relative case, the analogous notion is the loss of significance. Some of these questions are addressed with regard to the problem of evaluating rational functions.