Reducing the error of Algorithms by assigning variables formulas instead of values

Question

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:

1- Mark the $i+1$th point 1 cm next to the $i$th point.

2- Mark the $i+1$th point $i$ cm next to the $1$st point.

If there is error $\epsilon$ in each measurement, clearly the first method will have error $i \epsilon$ for its $i+1$th point, while the second method has error only $\epsilon$ for each point.

Now suppose we are given an algorithm $A$, that has a fixed number of inputs $a_1, a_2, ..., a_k$ and intermediate variables $v_1, ..., v_t$, that can be assigned elements from, say, an algebraic field. Suppose for simplicity that the algorithm can be implemented using a single loop, consisting of conditional statements and field operations over $a_i$ and $v_i$, and that $A$ outputs $v_1$. Suppose that when the field operations are performed accurately, the output value is "right and exact", otherwise $A$ has a bounded error.

Let Algorithm $B$ be this: $B$ does exactly as $A$, unless that it assigns to each $v_i$ an algebraic formula in terms of $a_i$s (instead of field elements), and with each iteration of the loop, these formulas are updated accordingly, and are simplified according to field rules whenever possible (for example $2a + 3a = 5a$). To evaluate the conditional statements in the loop, $B$ evaluates the formula of each $v_i$ to field elements (with some error), but then discards these values.

Algorithm $A$ is like the first way: The values assigned to $v_i$s in the $i + 1$th iteration depend on values assigned to $v_i$s in the $i$th iteration. But Algorithm $B$ is like the second way: It tries to evaluate $v_i$s (and the output) in terms of the inputs $a_i$s. And if there is an error in each application of the field operations, then we hope that the output error of $B$ is less than $A$, because $B$ evaluating the final formula of $v_1$, performs fewer filed operations than what $A$ does during its running, as $B$ simplifies the formulas.

At this stage, I am not concerned with the computational complexity of B, like its running time or space, just with its error.

My question is whether this is already studied and there is a theory for it.

Answer 1

You mean replace double and int by expressions as in Symbolic computation?

It's feasible as long as your expressions can be put in a standard (canonical) form, like polynomials with coefficients ordered by decreasing degree or linearised trigonometric sums. It also suppose you coefficients are error frees (integers or rationals). Mathematica is an example of such a PL.

Of course you will not be able any more to stop on conditions like $|err|< 10^{-6}$, because it presuppose $err$ was evaluated previously. So, without loops, you are better of the leaving the procedural programming paradigm and switch to functional programming.

With that in that in mind, double, int and even expressions are replaced by functions (in the computer science meaning, that is algorithms). It is the programmer responsibility to ensure that each function [algorithm] is as rounding error free as it is possible. Then the program can be "lazy", meaning the values are only computed when needed, at the last moment when needed. Haskel is such a PL.

If you'd like a free, 10mn getting started, no-frill symbolic programming language for experimenting the limits of your ideas, have a look at Eigenmath.