Kahan summation algorithmを試してみました。
発端
0.01f を 10000 回足すと 100.003f になる話に関連して、カハンの加算アルゴリズムを使うと、浮動小数点数の合計を求めるときの誤差を減らせることも知っておきたい https://t.co/Ctrz6V3QQ6 pic.twitter.com/FPPrUG2v8W
— Ryo Suzuki (@Reputeless) 2018年11月19日
発端はこの@Reputeless
さんのツイートからです。
コンピューターが発明された以後、そして2進数が発明してメモリ領域のあらゆる値を表現するにとって採用されてから浮動小数点は大きな数まで表現できるようになりました。
しかし浮動小数点は整数とは表現が違って浮動小数点は単なる2進数の羅列じゃなくIEEE754という表現の規定にそってメモリの領域の2進数を操ります。そしてその表現による重大な問題があります。
すべての素数を完全に表現することができないという事です。何故ならIEEE754の表現によると、0.01
みたいな素数てんは2進数でぴったりと表現できることができません。0.5
0.25
のように2で割れられる小数点は誤差なしに表現できますが、0.01
の場合には実際には0.001000001
みたいになってしまいます。
勿論浮動小数点一つ一つの誤差は大きくないですが、問題はこの浮動小数点を何千回も演算すると誤差が大きくなって、望ましい値とはだいぶ違ってしまいます。その誤差による演算が違ってしまうのを防ぐために開発されたのがPairwise summation
かKahan Summation Algoritihm
です。今回はPairwise
の代わりにKahan
を取り上げてみたいと思います。
説明
Kahan summation algorithm - Wikipedia
Kahan summation algorithm
は浮動小数点の演算の際に正確度の欠如による誤差を減らす為のアルゴリズムである。Pairwise summation algorithm
とは違いリストの形で一連の浮動小数点を渡さなくても、実時間で補正を行うことができる。
浮動小数点をN個演算するときに、最悪の場合Nに比例して誤差(Error)が大きくなる傾向がある。しかし演算するときに補正を行うと最悪の場合にもエラーバウンドはNに独立となり、ただ今使っている浮動小数点の正確度だけに依存するようになる。
実装コード
void KahanProcess(std::vector<float>& input) { auto com = 0.0f; for (const auto& value : input) { const auto y = value - com; const auto t = kahanSum + y; com = (t - kahanSum) - y; (void)com; kahanSum = t; } }
このアルゴリズムで注目すべきのところはcom
に補正を入れて、浮動小数点の正確度の欠如によるアンダフローを防ぐことだと思います。そして浮動小数点ごとの補正を演算するために、今までの合計を引き算してcom
を求めます。
Neumaier-Summation
という、Kahan
からより正確に補正を行うアルゴリズムも存在します。
結果
私がテストしたコードではstd::vector<>
に1,000,000個の0.01f
を入れてこれらを和して10,000.0
からいくらの誤差が出るかを検証します。そしてコード演算の結果、このように出ました。
PS C:\Users\jmyun\Documents\Dev\SH-Algorithm\Algorithm\KahanCompensation> .\a.exe Test "Plain-Sum" took 1415200ns. Test "Kahan-Sum" took 5268500ns. Expected : 10000.000000 Given(Plain-Sum) : 9865.223633 Given(Kahan-Sum) : 10000.000000
普通(Plain)に小数点を和したのは9865.224
の10000
から随分離れた数値が出たのが分かりますが、Kahan
を使用すると補正により10,000.0
が求められるのを確認できます。勿論補正のための追加演算が行われますので普通の和よりはだいぶ遅いです。
そのためのPairwise-Summation
というまた別の和演算補正アルゴリズムがありますが、そちらは誤差がO(lgN)
に比例している短所や浮動小数点をまとめたリストの形で渡さなければならない短所があります。(だとしてもPlainよりは誤差がほぼないです。)