2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "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}$. $\endgroup$ Mar 12, 2013 at 10:51
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 12, 2013 at 11:56
  • $\begingroup$ Federico Poloni : am I allowed to use log1p() ? :-) $\endgroup$
    – J.J. Green
    Mar 12, 2013 at 12:15
  • $\begingroup$ to Emil: ... otherwise A has a bounded error. $\endgroup$ Apr 19, 2013 at 8:06

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, AlainD. Very informative, but I also want to know if symbolic or functional computation, can be used to get provably better bounds on the error of numerical algorithms, in the way that is described in the question. $\endgroup$ Apr 19, 2013 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.