擬似コードと解説

ウィキペディア小見出し辞書

擬似コードと解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/16 00:14 UTC 版)

「カハンの加算アルゴリズム」の記事における「擬似コードと解説」の解説

このアルゴリズムの擬似コードは以下の通り: 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 内のデータも四倍精度にしなければならない。