NEUROMANTIC

自分でC/C++/UE4/Graphics/ゲームなどをやったことをメモするブログ

Kahan summation algorithmを試してみました。

発端

発端はこの@Reputelessさんのツイートからです。

コンピューターが発明された以後、そして2進数が発明してメモリ領域のあらゆる値を表現するにとって採用されてから浮動小数点は大きな数まで表現できるようになりました。

https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/IEEE_754_Single_Floating_Point_Format.svg/618px-IEEE_754_Single_Floating_Point_Format.svg.png

しかし浮動小数点は整数とは表現が違って浮動小数点は単なる2進数の羅列じゃなくIEEE754という表現の規定にそってメモリの領域の2進数を操ります。そしてその表現による重大な問題があります。

すべての素数を完全に表現することができないという事です。何故ならIEEE754の表現によると、0.01みたいな素数てんは2進数でぴったりと表現できることができません。0.5 0.25のように2で割れられる小数点は誤差なしに表現できますが、0.01の場合には実際には0.001000001みたいになってしまいます。

勿論浮動小数点一つ一つの誤差は大きくないですが、問題はこの浮動小数点を何千回も演算すると誤差が大きくなって、望ましい値とはだいぶ違ってしまいます。その誤差による演算が違ってしまうのを防ぐために開発されたのがPairwise summationKahan 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.22410000から随分離れた数値が出たのが分かりますが、Kahanを使用すると補正により10,000.0が求められるのを確認できます。勿論補正のための追加演算が行われますので普通の和よりはだいぶ遅いです。

そのためのPairwise-Summationというまた別の和演算補正アルゴリズムがありますが、そちらは誤差がO(lgN)に比例している短所や浮動小数点をまとめたリストの形で渡さなければならない短所があります。(だとしてもPlainよりは誤差がほぼないです。)

参照

Kahan summation algorithm - Wikipedia

Pairwise summation - Wikipedia