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

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.

• "Less operations" does not always mean "lower error": for instance, compute in a double-precision environment $\frac{\log(1+x)}{x}$ and $\frac{\log(1+x)}{(1+x)-1}$ for $x=10^{-15}$. – Federico Poloni Mar 12 '13 at 10:51
• Since the algorithm can use conditionals, even a slightest error in one variable may lead to choosing the wrong branch of a conditional, and therefore to a completely different result, regardless of whether you use A or B. – Emil Jeřábek supports Monica Mar 12 '13 at 11:56
• Federico Poloni : am I allowed to use log1p() ? :-) – J.J. Green Mar 12 '13 at 12:15
• to Emil: ... otherwise A has a bounded error. – Ruhollah Majdoddin Apr 19 '13 at 8:06

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.