カハンの加算アルゴリズム
補正加算における誤差を注意深く分析することで、その精度の特性がわかる。単純な総和の計算よりも正確だが、悪条件の総和では相対誤差が大きくなる。
i=1,...,n の n 個の数値 xi の合計を計算するとする。その計算は次の式で表される。
S n = ∑ i = 1 n x i {\displaystyle S_{n}=\sum _{i=1}^{n}x_{i}} (無限の精度で計算する場合)
補正加算では、 S n + E n {\displaystyle S_{n}+E_{n}} で総和が表され、誤差 E n {\displaystyle E_{n}} について次が成り立つ。
| E n | ≤ [ 2 ε + O ( n ε 2 ) ] ∑ i = 1 n | x i | {\displaystyle |E_{n}|\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]\sum _{i=1}^{n}|x_{i}|}
ここで ε は使用する算術体系の計算機イプシロンである(例えば、IEEEの倍精度浮動小数点数の場合は ε≈10)。通常、関心のある量は相対誤差 | E n | / | S n | {\displaystyle |E_{n}|/|S_{n}|} であり、相対誤差は上の式から次のような条件となる。
| E n | | S n | ≤ [ 2 ε + O ( n ε 2 ) ] ∑ i = 1 n | x i | | ∑ i = 1 n x i | .