ぎるばーとの日記

もっともっと遠くへ行きたい 空が広く見える場所まで

三角乱数

 マニアックな乱数記事を徐々に増やしていくキャンペーン。

 前回・前々回と、なぜ数学関数の使用を回避したいかを書いてなかったので、その補足から、、
 プログラムの数学関数、具体的にはサイン、コサイン、対数平方根などですが、処理が重いことが多いです。除法も加・減・乗法と比べれば若干重いとはいえ、これの回避は難しい……。
 数学関数を使わないかわりに、単位円内の一様乱数を作るための繰返しが入りました。その繰返し回数を見積もってみます。
 円と外接正方形の面積の比は\pi/4 \approx 0.785 \ldotsで、円内に点が入ったときに脱出。その逆数が繰返し回数の平均になります。幾何分布なので数回程度かかる場合もありますが、平均は1回ちょっとです。
 ちなみに、実際にサイン、コサインを使うより速いかは環境によりけりかも……?

 ここからが今日の本文。
 三角分布をPERTで使うという話は本当なのかどうか知りません。

Triangular distribution - Wikipedia, the free encyclopedia
 三角乱数、平方根を使う方法がWikipediaに書いてあります。が、もっといいやり方(感動的!)があるので紹介します。

A new method to simulate the triangular distribution
u \sim \text{Uniform}(0,1),\ v \sim \text{Uniform}(0,1)として、
(1-c)\text{MIN}(u,v) + c\text{MAX}(u,v)
 これで、三角乱数(a=0, b=1, cは最頻値で0以上1以下)になります。MINとMAXは比較だけなので、平方根の計算よりずっと軽い!

double randomTriangular(double c) {
    double u = Math.random(), v = Math.random();
    
    return (1.0 - c) * Math.min(u, v) + c * Math.max(u, v);
}

 この方法が紹介されているのをあまり見ませんが、美しいアルゴリズムの一つだと思います。