1. Number of Operations and Total Rounding Error #
$$ \begin{align} X’ &= X \pm d \\ d &= \varepsilon \sqrt{N} \end{align} $$
- Machine precision $\varepsilon$
- Number of operations $N$
- True value $X$
- Computed result $X'$
- Uncertainty in calculation $d$
2. Explanation #
Consider performing repeated operations on a computer. Here, “operations” refer to basic arithmetic calculations such as addition, subtraction, multiplication, and division in decimal.
Since all variables in a computer are represented in bits of 0 and 1, any value used by the computer is rounded to a finite representation. For example, even constants like $\pi$ are not stored with infinite precision but are rounded to a finite number of digits (e.g., about 16 digits in decimal).
Thus, when numbers that cannot be exactly represented in binary are expressed in binary, they must be rounded. This rounding affects the least significant bit, and the rounding follows certain predefined rules.
If we assume that the least significant bit is determined independently of the rest, the error causes a deviation from the true value by an amount equal to the machine precision $\varepsilon$.
In other words, using a machine with precision $\varepsilon$, performing $N$ operations introduces a discrepancy $d$ between the computed result $X’$ and the true value $X$. This discrepancy $d$, representing the total rounding error, can be modeled as a random walk1, leading to:
$$ \begin{align} X’ &= X \pm d \\ d &= \varepsilon \sqrt{N} \end{align} $$
This indicates that the computed result $X’$ can only be obtained with uncertainty $d$ (within a 1$\sigma$ range).
For instance, if the machine precision is $\varepsilon = 1 \times 10^{-16}$ and $N = 10000$ operations are performed to obtain a result $X’$, the precision of the result will be $X \pm 1 \times 10^{-14}$. This only accounts for the effect of rounding errors; additional effects such as truncation errors must also be considered.