カハンの加算アルゴリズム
カハンのアルゴリズムでの誤差成長は入力数 n に対して O ( 1 ) {\displaystyle O(1)} だが、ペアごとの和(英語版)では若干悪い O ( log  n ) {\displaystyle O(\log n)} となる。これは入力を再帰的に半分に分けていって、再帰的に加算を行う方式である。この技法は単純な総和計算に比べて加算回数が増えないという利点があり(カハンのアルゴリズムでは演算回数が4倍に増える)、並列計算も可能という利点がある。通常、再帰の行き着いた基本ケースでは1回または0回の加算になるが、再帰のオーバーヘッドを低減させるため n がある程度小さくなったらそれ以上再帰させないという方式も考えられる。ペアごとの和と同様の技法は高速フーリエ変換 (FFT) アルゴリズムでよく使われており、そのためFFTでは誤差が対数的に成長することが多い。
カハンの加算アルゴリズム(英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム)とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合に、計算の途中の誤差を保持することで補正する。Compensated summation(補正加算)とも呼ぶ。
単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち n {\displaystyle {\sqrt {n}}} に比例する誤差が生じる(丸め誤差はランダムウォークを形成する)。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる。
このアルゴリズムの名は考案したウィリアム・カハンに因む。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する(文書化されたのはカハンとほぼ同時期である)。その他の類似例としてはΔΣ変調が挙げられる。ΔΣでは、誤差の蓄積の保持が積分となっている。