namespace std {
using knuth_b = shuffle_order_engine<minstd_rand0, 256>;
}
概要
knuth_b
は、MINSTD最小標準乱数生成器であるminstd_rand0
の生成順を並び替えた乱数生成法である。
knuth_b
では、minstd_rand0
によって生成された乱数を256
個バッファリングしておき、順番を入れ替えて値を選択していく。これにより、線形合同法(minstd_rand0
or minstd_rand
)を直接使用するよりも出力間の相関関係が小さくなり、乱雑さが増加する。
Donald Knuth氏の著書『The Art of Computer Programming, Second Edition, Volume 2, Seminumerical Algorithms』で考案された、リオーダーアルゴリズムBがそれだ。
このアルゴリズムは、Microsoft .NET FrameworkのSystem.Random
クラスにも、実装として使用されている。
要件
knuth_b
型オブジェクトをデフォルト構築した場合、10000番目に生成される擬似乱数の値は1112339016
であること。
乱数列の周期
不明(Boost.Randomのドキュメントより)
サイズ
(256 + 1) * sizeof(uint_fast32_t)
shuffle_order_engine
でバッファリングする要素の数(256) + minstd_rand0
の状態(1)。
パフォーマンス
minstd_rand0
の2〜3倍遅い程度。
詳細は、shuffle_order_engine
ページの動作説明を参照。
次元
次元数のトレードオフは、各出力の間(現在の状態と次の状態)の相関関係が、無視できるほどしかないということを意味する。たとえばN次元のランダムなベクトルを生成する場合、各次元の値に相関関係がほぼない状態にできる。
概要で説明したように、この手法は線形合同法によって生成された乱数を256
個バッファリングして生成順を入れ替えたものである。それによって、出力間の相関関係は小さくなってはいるが、無視できるほど小さい相関関係とは言いにくい。knuth_b
は、2次元以上のランダムな値を生成するために使用することもできるだろうが、そのような目的に使用するのであれば、mt19937
やmt19937_64
を使用することを推奨する。
シード、および生成される値の型
例
#include <iostream>
#include <random>
int main()
{
std::random_device seed_gen;
std::knuth_b engine(seed_gen());
for (int i = 0; i < 10; ++i) {
std::uint64_t result = engine();
std::cout << result << std::endl;
}
}
出力例
1626011263
899717059
1316478681
732866635
512074444
354532979
2021640279
2002307542
2064026990
375634814
バージョン
言語
- C++11
処理系
- Clang: ??
- GCC: 4.7.2 ✅
- ICC: ??
- Visual C++: ??