How to Avoid Rounding Errors

(Probably, this is a standard algorithm, so if someone knows the name, drop me a note.)

If something like

\[y_i = {x_i a \over b}\]

is to be calculated, and all numbers are integers, a naive implementation would result in something, for which

\[\sum y_i \ne {(\sum x_i) a \over b}\]

because of rounding errors, due to the integer division. This can be avoided by transforming the formula into

\[y_i = {(\sum_{j=0}^{j=i} x_j) a \over b} - \sum_{j=0}^{j=i} y_j\]

Of corse, when all $y_i$ are calculated in a sequence, $\sum_{j=0}^{j=i} x_j$ and $\sum_{j=0}^{j=i} y_j$ can be accumulated in the same loop.


Generated on Wed Sep 7 02:00:36 2011 for Dillo by  doxygen 1.5.9