|
カハンの加算アルゴリズム（Kahan summation algorithm）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を最小化する数値解析のアルゴリズム。基本的にコンピュータ上で使用される。Compensated Summation（補正加算）とも呼ぶ〔「補正加算」と呼ばれる技法は他にもある。詳しくは 〕。 単純に ''n'' 個の数値の総和を計算すると、''n'' に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）。補正加算では最悪の場合の誤り限界 (error bound) は ''n'' とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる〔。 このアルゴリズムは考案したウィリアム・カハンの名を取り、こう呼ばれる。似たようなそれ以前の技法として、例えばブレゼンハムのアルゴリズムがあり、整数演算での誤差の蓄積を保持する（文書化されたのはカハンとほぼ同時期である〔Jack E. Bresenham, "Algorithm for computer control of a digital plotter" , ''IBM Systems Journal'', Vol. 4, No.1, January 1965, pp. 25–30〕）。また、ΔΣ変調では誤差（雑音）を加算するのみでなく積分する〔H. Inose, Y. Yasuda, J. Murakami, "A Telemetering System by Code Manipulation – ΔΣ Modulation," IRE Trans on Space Electronics and Telemetry, Sep. 1962, pp. 204–209.〕。 == 擬似コードと解説 == このアルゴリズムの擬似コードは以下の通り: function kahanSum(input) var sum = 0.0 var c = 0.0 // 処理中に失われる下位ビット群の補償用変数 for i = 1 to input.length do y = input - 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.7182とする。正確な加算結果は 10005.85987 であり、6桁に丸めると10005.9となる。単純に加算すると1回目の加算で 10003.1、2回目で 10005.8 となり、正しくない。 ''c'' の初期値はゼロとする。 y = 3.14159 - 0 ''y = input - 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'' 内のデータも四倍精度にしなければならない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「カハンの加算アルゴリズム」の詳細全文を読む スポンサード リンク
|