カハンの加算アルゴリズム

カハンの加算アルゴリズム（Kahan summation algorithm: 不正確でなく訳すとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合に、計算の途中の誤差を保持することで補正する。Compensated Summation（補正加算）とも呼ぶ。
単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち  に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる。
このアルゴリズムは考案したウィリアム・カハンの名を取り、こう呼ばれる。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である）。その他の類似例としてはΔΣ変調が挙げられる。ΔΣでは、誤差の蓄積の保持が積分となっている。

擬似コードと解説

このアルゴリズムの擬似コードは以下の通り:
function kahanSum(input)
    var sum = 0.0
    var c = 0.0             // 処理中に失われる下位ビット群の補償用変数    for i = 1 to input.length do
        y = input[i] - c          // 問題なければ、c はゼロ        t = sum + y               // sum が大きく y は小さいとすると、y の下位ビット群が失われる        c = (t - sum) - y         // (t - sum) は y の上位ビット群に相当するので y を引くと下位ビット群が得られる（符号は逆転）
        sum = t                   // 数学的には c は常にゼロのはず。積極的な最適化に注意    next i                  // 次の繰り返しで y の失われた下位ビット群が考慮される    return sum
6桁の十進浮動小数点演算を例として動作を見てみよう。コンピュータは普通二進演算だが、基本原理は同じである。sum の値が 10000.0 で、次の input(i) が 3.14159 と 2.71828とする。正確な加算結果は 10005.85987 であり、6桁に丸めると10005.9となる。単純に加算すると1回目の加算で 10003.1、2回目で 10005.8 となり、正しくない。
c の初期値はゼロとする。
  y = 3.14159 - 0                    y = input[i] - c
  t = 10000.0 + 3.14159
    = 10003.1                        大部分の桁が失われた  c = (10003.1 - 10000.0) - 3.14159  これは書かれた通りに評価される必要がある    = 3.10000 - 3.14159              y の失われた部分を得るため、本来の y との差分を得る    = -.0415900                      6桁なので、最後にゼロが付与されるsum = 10003.1                        このように input(i) の一部の桁しか加算されていない
合計が非常に大きいため、入力数値の一部の桁しか反映されない。しかし、ここで次の intput(i) の値が 2.71828 とすると、今回は c がゼロでなはないため次のようになる。
  y = 2.71828 - -.0415900            前回加算できなかった部分をここで反映する    = 2.75987                        大きな変化はなく、ほとんどの桁が有効に計算される  t = 10003.1 + 2.75987              しかし、総和へ加算しようとすると一部の桁しか考慮されない    = 10005.9                        丸めが発生している  c = (10005.9 - 10003.1) - 2.75987  反映されなかった分を計算する    = 2.80000 - 2.75987              今回は加算された値が大きすぎる    = .040130                        しかし、次の繰り返しで反映するので問題ないsum = 10005.9                       正確な値は 10005.85987 であり、正しく6桁に丸められている
ここで、総和は2つの部分に分けられて実行されると考えられる。すなわち、sum は総和を保持し、c は sum に反映されなかった部分を保持する。そして次の繰り返しの際に sum の下位桁への補正を試みる。これは、何もしないよりはよいが、精度（桁数）を倍にした方がずっと効果があるのも事実である。ただし、単純に桁数を増やすことが現実的とは限らない。input が倍精度だった場合、四倍精度をサポートしているシステムは少ないし、四倍精度を採用するなら input 内のデータも四倍精度にしなければならない。

代替手法

カハンのアルゴリズムでの誤差成長は入力数 n に対して  だが、pairwise summation では若干悪い  となる。これは入力を再帰的に半分に分けていって、再帰的に加算を行う方式である。この技法は単純な総和計算に比べて加算回数が増えないという利点があり（カハンのアルゴリズムでは演算回数が4倍に増える）、並列計算も可能という利点がある。通常、再帰の行き着いた基本ケースでは1回または0回の加算になるが、再帰のオーバーヘッドを低減させるため n がある程度小さくなったらそれ以上再帰させないという方式も考えられる。pairwise summation と同様の技法は高速フーリエ変換 (FFT) アルゴリズムでよく使われており、そのためFFTでは誤差が対数的に成長することが多い。実際には丸め誤差の符号は無作為に変化するので、pairwise summation の二乗平均平方根誤差の成長は  となる。
もう1つの代替手法として、何よりも丸め誤差を生じないことが優先されるなら、任意精度演算を使うことが考えられる。Shewchukは、特に高精度ではないが正確に丸められた総和を求める技法として、任意精度演算を使ってそれなりのコストで計算する方法を示した。Kirchnerとウルリヒ・クリッシュはビット幅の大きいアキュムレータを使い、整数演算だけで総和を求める技法を示した。ハードウェアの実装を示した例として Müller、Rüb、Rülling の論文がある。
10の20乗といったような絶対値が極端に大きい数を扱うことが無い、会計などには、浮動小数点方式ではなく、必要十分な桁数以上を確保した固定小数点方式（また、場合によっては十進演算）を、可能であれば使う方がよい。

最適化にまつわる注意

コンパイラが生成するコードは、最適化により、書かれたプログラムと正確に対応しないのが普通である。コンパイラはプログラムの内容を数式処理的に解析して最適化を施すことがあるが、コンパイラの設計によってはカハンの加算アルゴリズムについて間違った最適化を行なうことがある。例えば、以下のコードについて
  t:=sum + y;
  c:=(t - sum) - y;
コンパイラは、結合法則を適用して以下のように推論することがある。
  c = 0
すると補正がなされなくなる。ただし、一般にコンパイラは浮動小数点演算では近似的にしか結合法則が成り立たないとして、明示的に「安全でない」最適化を指示されないかぎり、このような最適化を行わない。なお、Intel C++ Compiler のようにデフォルトで結合法則を適用した最適化を行うコンパイラもある。K&R版の最初のC言語では、結合法則による浮動小数点演算の項の並べ替えを許していたが、ANSI C 規格ではそれが禁止され、C言語を数値解析分野で使いやすくした（FORTRANでも並べ替えが禁止されている）。それでもオプションを指定すれば並べ替えできるようにしてあるコンパイラが多い。
一方、一部の言語では総和機能を提供している（APLの +/input、FORTRANのSUMなど）。これらは最良の手法で総和を計算するような実装であると期待される。しかし、FORTRANのマニュアルを見ても単に入力と同じ精度で計算するとあるだけで詳細は不明である。線型代数学の標準的サブルーチン集であるBLASでは、高速化のための演算順序の並べ替えを明確に避けているが、BLASの実装ではカハンのアルゴリズムを採用していないことが多い。Pythonの標準ライブラリには fsum という総和関数があり、Shewchukのアルゴリズムを使い丸め誤差の蓄積を防いでいる。