読者です 読者をやめる 読者になる 読者になる

syghの新フラグメント置き場

プログラミングTipsやコード断片の保管場所です。お絵描きもときどき載せます。

正規分布する乱数の生成(中心極限定理/Box-Muller)

.NET Framework WPF C#

コンピュートシェーダーでブラウン運動のシミュレーションを実装しようと思ったんですが、そのためにはまず正規乱数(正規分布する乱数)を生成する必要がありそうなので、まず自前のCPU向けコードで正規乱数を作るテストプログラムを書くことにしました。
正規乱数を作る方法はいくつかあるらしいのですが、今回は実装が簡単で高速な中心極限定理とBox-Muller法を使っています。

中心極限定理
{ \displaystyle
R_{normal} = \frac{\sum_{k=1}^{12} r_k}{6}
}

・Box-Muller法:
{ \displaystyle
Z_1 = \sqrt{-2\ln{X}}\cos{2\pi{Y}}
}
{ \displaystyle
Z_2 = \sqrt{-2\ln{X}}\sin{2\pi{Y}}
}

はてなブログtex記法(MathJax実装)は良いですね。数式の美しさはさすがに本家には及びませんが、ラスター画像ではなくベクトルデータが埋め込まれるのがすばらしいです。
ちなみにC++11ではBoostからの逆輸入によって標準ライブラリがかなり強化されています。たとえば <random> ライブラリを使うことで線形合同法だろうがメルセンヌツイスターだろうが、一様乱数だろうが正規乱数だろうが簡単に好みの乱数エンジンを作ることができます。*1
Visual C++ 2013付属のヘッダーをのぞいてみたところ、正規乱数分布(std::normal_distributionクラステンプレート)の実装にはどうもBox-Muller法が使われているようでした。

今回はGPU (HLSL/GLSL) への移植を視野に入れること、また実験の可視化のしやすさから、テストコードの実装にはC# + WPFを使うことにしました。JavaScriptのD3.jsとかも検討したんですが、あまりパフォーマンステストにはならないので却下(というかJavaScript自体があまり好きではない)。

static class MyRandomNumHelper
{
  // Box-Muller 法を使って標準正規分布 N(0, 1) を得る。
  public static void CreateNextStdNormalDistRandomsByBoxMullerTransform(Random randEngine, out double z1, out double z2)
  {
    // [0, 1] の一様乱数をまず生成。
    // ちなみに .NET の System.Random クラスの現在の実装は、Donald E. Knuth の減算式乱数生成アルゴリズムに基づいているらしい。
    // http://msdn.microsoft.com/en-us/library/System.Random.aspx

    var alpha = randEngine.NextDouble();
    var beta = randEngine.NextDouble();

    if (alpha == 0.0)
    {
      // 発散を防ぐ。
      alpha = 1.0;
    }

    var sqlog = Math.Sqrt(-2.0 * Math.Log(alpha));
    var theta = 2.0 * Math.PI * beta;
    z1 = sqlog * Math.Cos(theta);
    z2 = sqlog * Math.Sin(theta);
  }

  // 中心極限定理を使って標準正規分布 N(0, 1) を得る。
  public static double CreateNextStdNormalDistRandomByCentralLimitTheorem(Random randEngine)
  {
    double sum = 0;
    for (int i = 0; i < 12; ++i)
    {
      sum += randEngine.NextDouble();
    }
    return sum - 6.0;
  }
}

今回Box-Mullerでは特異点を回避するために分岐を入れましたが、作為的とも言えるこの安直な方法だとz1, z2がともにゼロになります。同じ数が連続して出現するのが好ましくない場合は注意しましょう。

ちなみに.NET 4.5時点でもWPFには標準でチャート系のコントロールが用意されていません。自分が探した中では、下記のような外部ライブラリがありました。

  1. Extended WPF Toolkit Plus
  2. Modern UI (Metro) Charts for Windows 8, WPF, Silverlight
  3. Silverlight/WPF Data Visuallization Toolkit

Extended WPF Toolkitは有名なライブラリですが、オープンソースでフリー(Ms-PL)のCommunity Editionと、有償のPlus Edition/Business Suiteがあり、チャート系は有償版にしかないそうです。
Modern UI Chartsはドイツ人のTorsten Mandelkow氏が開発したMs-PLライセンスのライブラリで、外観デザインは良いのですがカスタマイズ性が自分の求める方向とは違ったので今回は使わないことにしました。
Data Visualization Toolkit(以下DVTK)はもともとDavid Anson氏によってSilverlight 3/4, WPF 3.5/4向けに開発されたMs-PLライセンスのライブラリで、外観デザインがOffice 2010風でちょっと古い感じがしますが、Styleによる軸や凡例のカスタマイズ性が高いのが良いです。また、普通にVS 2012/2013でSilverlight 5, WPF 4.5向けにプロジェクトアップグレード・リビルドできたので、今回はDVTKを使うことにしました。

https://sygh-jp.github.io/content_hosting/my_program_ss/WpfNormalDistRand_ss_2014_09_15a.png

・DVTK for .NET 4.5:
SilverlightWpfDataVisualization_Net45.zip

・正規乱数のテストコード:
WpfNormalDistRand.zip

DVTKを利用する場合は、Ms-PLライセンスの条文に従ってください。

2016-08-08追記:
DVTKはすでに更新・開発が止まってしまっていますが、代わりにOxyPlotという良質のオープンソースライブラリ(MITライセンス)を見つけました。

2016年8月時点の最新版は2016-04-11リリースの1.0.0-unstable2100で、ずっとpre-releaseつまりベータ版扱いのようですが、軽く使ってみた限り大きな不具合は見つかりませんでした。

*1:自分は修士論文のための検証プログラムを、C++とBoostを使って書き、可視化にはDirect3Dを使っていました。もちろん修論にはpLaTeX2eを使っていました。内容自体は今思えば大したことなかったのですが、その後の自分の方向性を決定づけたと思っています。