カハンの加算アルゴリズム（英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合[1]に、計算の途中の誤差を保持することで補正する。Compensated summation（補正加算）とも呼ぶ[2]。

単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち n {\displaystyle {\sqrt {n}}} に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）[3]。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる[3]。

このアルゴリズムの名は考案したウィリアム・カハンに因む[4]。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である[5]）。その他の類似例としてはΔΣ変調が挙げられる。ΔΣでは、誤差の蓄積の保持が積分となっている[6]。
擬似コードと解説

このアルゴリズムの擬似コードは以下の通り: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) の一部の桁しか加算されていない

合計が非常に大きいため、入力数値の一部の桁しか反映されない。しかし、ここで次の input(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 内のデータも四倍精度にしなければならない。
精度

補正加算における誤差を注意深く分析することで、その精度の特性がわかる。単純な総和の計算よりも正確だが、悪条件の総和では相対誤差が大きくなる。

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}} について次が成り立つ[3]。 。 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−16）。通常、関心のある量は相対誤差 。 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 。 . {\displaystyle {\frac {|E_{n}|}{|S_{n}|}}\leq \left[2\varepsilon +O(n\varepsilon ^{2})\right]{\frac {\sum _{i=1}^{n}|x_{i}|}{\left|\sum _{i=1}^{n}x_{i}\right|}}.}

この相対誤差の境界条件式において、分数 Σ|xi|/|Σxi。が総和問題の条件数である。計算方法がどうであれ、この条件数が総和問題の本質的な誤差への敏感さを表している[7]。固定精度を使った固定の（すなわち、任意精度演算のようにデータによって時間および領域の計算量が変化するアルゴリズムではない）アルゴリズムによる全ての（後方安定な）総和計算技法の相対誤差条件は、その条件数に比例する[3]。「悪条件」の総和問題では、その比率が大きくなり、補正加算であっても相対誤差が大きくなる。例えば被加数 xi が平均値がゼロの無相関の乱数列の場合、その総和はランダムウォークとなり、条件数は n {\displaystyle {\sqrt {n}}} に比例して成長する。一方、入力が無作為であっても平均がゼロでなければ、 n → ∞ {\displaystyle n\to \infty } に伴って条件数は有限の定数に漸近することになる。入力が全て負でない場合、条件数は1となる。

固定の条件数が与えられると、補正加算の相対誤差は事実上 n とは独立となる。原理的に n よって線型に成長する O(nε2) があるが、この項は実質的にゼロと見なせる。というのも最終結果が精度 ε に丸められるので、n がおよそ 1/ε かそれ以上でない限り nε2 という項はゼロに丸められる[3]。倍精度の場合、その項が無視できなくなる n の値は 1016 ぐらいであり、多くの場合それほどの数値の総和を求めるのは現実的でない。したがって、条件数が固定なら補正加算の誤差は事実上 O(ε) となって、n とは独立である。

それに比べ、加算のたびに丸めが発生する単純な総和計算では、相対誤差は O ( ε n ) {\displaystyle O(\varepsilon n)} と条件数をかけた値として成長していく[3]。ただし、この最悪ケースは丸め方向が毎回同じ場合のみ発生するので、実際にはめったに観察されない。実際には丸め方向は毎回無作為に変化し、その平均はゼロに近づくことが多い。その場合の単純な総和の相対誤差は二乗平均平方根となり、 O ( ε n ) {\displaystyle O(\varepsilon {\sqrt {n}})} と条件数をかけた値として成長していく[8]。