std::knuth_b(C++11)

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がそれだ。

要件

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を使用することを推奨する。

シード、および生成される値の型

uint_fast32_t

例

#include <iostream>
#include <random>
#include <cstdint>

int main()
{
  std::random_device seed_gen;
  std::uint32_t seed = seed_gen();
  std::knuth_b engine(seed);

  for (int i = 0; i < 10; ++i) {
    std::uint64_t result = engine();
    std::cout << result << std::endl;
  }
}

出力例

バージョン

言語

C++11

処理系

Clang: ??
GCC: 4.7.2 ✅
ICC: ??
Visual C++: ??

参照

N1933 Improvements to TR1's Facility for Random Number Generation