カハンの加算アルゴリズム
カハンの加算アルゴリズム（Kahan summation algorithm）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。基本的にコンピュータ上で使用される。Compensated Summation（補正加算）とも呼ぶ。
単純に "n" 個の数値の総和を計算すると、"n" に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち formula_1 に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）。補正加算では最悪の場合の誤り限界 (error bound) は "n" とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる。
このアルゴリズムは考案したウィリアム・カハンの名を取り、こう呼ばれる。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である）。また、ΔΣ変調では誤差（雑音）を加算するのみでなく積分する。
このアルゴリズムの擬似コードは以下の通り:
6桁の十進浮動小数点演算を例として動作を見てみよう。コンピュータは普通二進演算だが、基本原理は同じである。"sum" の値が 10000.0 で、次の "input(i)" が 3.14159 と 2.71828とする。正確な加算結果は 10005.85987 であり、6桁に丸めると10005.9となる。単純に加算すると1回目の加算で 10003.1、2回目で 10005.8 となり、正しくない。
"c" の初期値はゼロとする。
合計が非常に大きいため、入力数値の一部の桁しか反映されない。しかし、ここで次の "intput(i)" の値が 2.71828 とすると、今回は c がゼロでなはないため次のようになる。
ここで、総和は2つの部分に分けられて実行されると考えられる。すなわち、"sum" は総和を保持し、"c" は "sum" に反映されなかった部分を保持する。そして次の繰り返しの際に "sum" の下位桁への補正を試みる。これは、何もしないよりはよいが、精度（桁数）を倍にした方がずっと効果があるのも事実である。ただし、単純に桁数を増やすことが現実的とは限らない。"input" が倍精度だった場合、四倍精度をサポートしているシステムは少ないし、四倍精度を採用するなら "input" 内のデータも四倍精度にしなければならない。
補正加算における誤差を注意深く分析することで、その精度の特性がわかる。単純な総和の計算よりも正確だが、悪条件の総和では相対誤差が大きくなる。
"i"=1...,"n" の "n" 個の数値 "x" の合計を計算するとする。その計算は次の式で表される。
補正加算では、formula_3 で総和が表され、誤差 formula_4 について次が成り立つ。
ここで ε は使用する算術体系の計算機イプシロンである（例えば、IEEEの倍精度浮動小数点数の場合は ε≈10）。通常、関心のある量は formula_6 であり、相対誤差は上の式から次のような条件となる。
この相対誤差の境界条件式において、分数 Σ|"x"|/|Σ"x"| が総和問題の条件数である。計算方法がどうであれ、この条件数が総和問題の本質的な誤差への敏感さを表している。固定精度を使った固定の（すなわち、任意精度演算のようにデータによって時間および領域の計算量が変化するアルゴリズムではない）アルゴリズムによる全ての（後方安定な）総和計算技法の相対誤差条件は、その条件数に比例する。「悪条件」の総和問題では、その比率が大きくなり、補正加算であっても相対誤差が大きくなる。例えば被加数 "x" が平均値がゼロの無相関の乱数列の場合、その総和はランダムウォークとなり、条件数は formula_1 に比例して成長する。一方、入力が無作為であっても平均がゼロでなければ、formula_9 に伴って条件数は有限の定数に漸近することになる。入力が全て負でない場合、条件数は1となる。
固定の条件数が与えられると、補正加算の相対誤差は事実上 "n" とは独立となる。原理的に "n" よって線型に成長する O("n"ε) があるが、この項は実質的にゼロと見なせる。というのも最終結果が精度 ε に丸められるので、"n" がおよそ 1/ε かそれ以上でない限り "n"ε という項はゼロに丸められる。倍精度の場合、その項が無視できなくなる "n" の値は 10 ぐらいであり、多くの場合それほどの数値の総和を求めるのは現実的でない。したがって、条件数が固定なら補正加算の誤差は事実上 "O"(ε) となって、"n" とは独立である。
それに比べ、加算のたびに丸めが発生する単純な総和計算では、相対誤差は formula_10 と条件数をかけた値として成長していく。ただし、この最悪ケースは丸め方向が毎回同じ場合のみ発生するので、実際にはめったに観察されない。実際には丸め方向は毎回無作為に変化し、その平均はゼロに近づくことが多い。その場合の単純な総和の相対誤差は二乗平均平方根となり、formula_11 と条件数をかけた値として成長していく。その場合でも補正加算より誤差が大きくなる。ただし、精度を2倍にすれば ε が ε となるので、単純総和の誤差は O("n"ε) となって、元の精度での補正加算に匹敵するようになる。
カハンのアルゴリズムでの誤差成長は入力数 "n" に対して formula_12 だが、 では若干悪い formula_13 となる。これは入力を再帰的に半分に分けていって、再帰的に加算を行う方式である。この技法は単純な総和計算に比べて加算回数が増えないという利点があり（カハンのアルゴリズムでは演算回数が4倍に増える）、並列計算も可能という利点がある。通常、再帰の行き着いた基本ケースでは1回または0回の加算になるが、再帰のオーバーヘッドを低減させるため "n" がある程度小さくなったらそれ以上再帰させないという方式も考えられる。pairwise summation と同様の技法は高速フーリエ変換 (FFT) アルゴリズムでよく使われており、そのためFFTでは誤差が対数的に成長することが多い。実際には丸め誤差の符号は無作為に変化するので、pairwise summation の二乗平均平方根誤差の成長は formula_14 となる。
もう1つの代替手法として、何よりも丸め誤差を生じないことが優先されるなら、任意精度演算を使うことが考えられる。Shewchukは、特に高精度ではないが正確に丸められた総和を求める技法として、任意精度演算を使ってそれなりのコストで計算する方法を示した。KirchnerとKulischはビット幅の大きいアキュムレータを使い、整数演算だけで総和を求める技法を示した。ハードウェアの実装を示した例として Müller、Rüb、Rülling の論文がある。
10の20乗といったような絶対値が極端に大きい数を扱うことが無い、会計などには、浮動小数点方式ではなく、必要十分な桁数以上を確保した固定小数点方式（また、場合によっては十進演算）を、可能であれば使う方がよい。
コンパイラが生成するコードは書かれたプログラムと正確に対応しているのが普通である。コンパイラはプログラムの内容を数式処理的に解析して最適化を施すことがあるが、コンパイラの設計によってはカハンの加算アルゴリズムについて間違った最適化を行なうことがある。例えば、以下のコードについて
コンパイラは、結合法則を適用して以下のように推論することがある。
すると補正がなされなくなる。ただし、一般にコンパイラは浮動小数点演算では近似的にしか結合法則が成り立たないとして、明示的に「安全でない」最適化を指示されないかぎり、このような最適化を行わない。なお、Intel C++ Compiler のようにデフォルトで結合法則を適用した最適化を行うコンパイラもある。K&R版の最初のC言語では、結合法則による浮動小数点演算の項の並べ替えを許していたが、ANSI C 規格ではそれが禁止され、C言語を数値解析分野で使いやすくした（FORTRANでも並べ替えが禁止されている）。それでもオプションを指定すれば並べ替えできるようにしてあるコンパイラが多い。
一方、一部の言語では総和機能を提供している（APLの +/input、FORTRANのSUMなど）。これらは最良の手法で総和を計算するような実装であると期待される。しかし、FORTRANのマニュアルを見ても単に入力と同じ精度で計算するとあるだけで詳細は不明である。線型代数学の標準的サブルーチン集であるBLASでは、高速化のための演算順序の並べ替えを明確に避けているが、BLASの実装ではカハンのアルゴリズムを採用していないことが多い。Pythonの標準ライブラリには fsum という総和関数があり、Shewchukのアルゴリズムを使い丸め誤差の蓄積を防いでいる。