独自の乱数生成器を C++ 標準ライブラリと組み合わせて使う

はじめに

タイトルのとおり、独自の乱数生成器を C++ 標準ライブラリと組み合わせて使おうという話です。

先日第三者として参加したレビューでコメントしたことを整理して文章にしました。

前提

いきなり本題に移りたい方はここは読み飛ばしていただいてかまいません。

とある目的で乱数を使います。

ハードウェア乱数生成器

開発しているシステムにはハードウェアで実装された (真の) 乱数生成器が搭載されています^[1]。
この乱数生成器は専用のドライバ経由で利用し、 C/C++ のプログラムからは次のようなシグネチャの関数としてアクセスできます:

Code 1

bool GenerateRandom(uint8_t* buffer, size_t length);

この関数は、範囲 [0, 255] の乱数を length 個生成し、 buffer から始まる連続領域に書き込みます。
成功した場合は true を, 何らかの要因で失敗した場合は false を, それぞれ返します。

実際にはこれに先立って初期化関数を呼ぶ必要があり、それで得られたセッションハンドルのようなものも GenerateRandom 関数に渡す必要がありますが、本記事の趣旨とは関係が薄いので省略しています。

フォールバック

ハードウェア乱数生成器を使った乱数生成は何らかの要因で失敗することがあり得ます。
そのような場合には疑似乱数生成器 (ソフトウェアで実装された、疑似乱数を生成するアルゴリズム) を使った乱数生成にフォールバックするという要件です。

C++ では標準ライブラリが疑似乱数生成器を提供していますのでこれが利用できます。
C++ 標準ライブラリの疑似乱数生成器は operator() で疑似乱数を生成します。

インタフェースをそろえる

このように両者の API はまったく異なりますが、生成された乱数を使う側からするとそろっている方が都合がよいです。

まずは、ハードウェア乱数生成器を利用する GenerateRandom 関数 (Code 1) と同じインタフェースを C++ 標準ライブラリの疑似乱数生成器を用いて実現するパターンです。
ナイーブな実装例を Code 2 に示します。
std::random_device クラスのコンストラクタと operator() は例外を投げる可能性がありますが、そこは省いています。

Code 2

#include <cstddef>
#include <cstdint>
#include <algorithm>
#include <random>

bool GenerateRandom(std::uint8_t* buffer, std::size_t length) {
  static std::random_device seedGen;
  static std::mt19937 engine{seedGen()};
  std::uniform_int_distribution<std::uint8_t> dist;
  std::generate(buffer, buffer + length, [&dist]() {
    return dist(engine);
  });
  return true;
}

これで、ハードウェア乱数生成器 (Code 1) も標準ライブラリの疑似乱数生成器も同じインタフェースで使えるようになりました。

一方、逆に、ハードウェア乱数生成器を C++ 標準ライブラリの乱数生成ライブラリのインタフェースに合わせるパターンもあるはずです。
ようやく本題です。

C++ の乱数生成ライブラリ

C++ は標準で (疑似) 乱数生成ライブラリを <random> にて提供しています。
このライブラリは次の 4 つのカテゴリから構成されています^[2]:

1. uniform random bit generators
2. random number engines
3. random number engine adaptors
4. random number distributions

このライブラリを使って疑似乱数を生成する際には、これらのカテゴリから適切なものを選んで組み合わせて使います。
呼ぶだけでいい感じの疑似乱数が得られた従来の std::rand 関数に比べると難しい, めんどうといった批判もあるようです^[3]が、素人目にはうまく設計されていると感じます^[4]。

独自の乱数生成器をこのライブラリと組み合わせて使う場合、どのカテゴリのクラスを作ればよいのでしょうか。
結論から述べると (1) uniform random bit generators です。

要件の包含関係では (1) uniform random bit generators は (2) random number engines を含んでおり、 (2) random number engines のクラスでも問題ありませんが、こちらの方が要件が厳しい分、実現の難易度は高いです。
今回のケースのようにハードウェアで実装された乱数生成器を使う場合は (1) uniform random bit generators を選ぶのが適切だと思います (参考文献 2)。

uniform random bit generators

uniform random bit generator は、一定の範囲内の符号なし整数を (理想的には) 等確率で返すような関数オブジェクトのことです。
規格の規定も載せておきます:

A uniform random bit generator g of type G is a function object returning unsigned integer values such that each value in the range of possible results has (ideally) equal probability of being returned.

(参考文献 1 の 28.5.3.3 Uniform random bit generator requirements [rand.req.urng])

要件

実装する必要があるインタフェースは限られていて、次の 4 つだけです:

• メンバ型 result_type
• 静的メンバ関数 min
• 静的メンバ関数 max
• 非静的メンバ関数 operator()

ここで、メンバ関数 min, max, operator() が返す値の型は result_type で、これは符号なし整数型です。
min が返す値は max が返す値よりも小さく、かつ、 operator() が返す値は範囲 [min(), max()] に収まっている必要があります。 これは自然な要件ですね。
また、メンバ関数 min, max は constexpr でなくてはなりません。
さらに、メンバ関数 operator() の計算量は償却定数時間 (amortized constant complexity) であることも求められます。

uniform random bit generators 要件は、 C++20 からは std::uniform_random_bit_generator コンセプトを使った記述に改められましたが、たぶん内容は変わっていないと思います。

実装サンプル

独自の乱数生成器を使って uniform random bit generator 要件を満たすクラス RandomNumberGenerator を書いてみました。
private メンバ関数 RandomNumberGenerator::randomizePool 内で呼び出している GenerateRandom 関数が、独自の乱数生成器を利用するインタフェースです。

一定のサイズ (サンプル実装では 256 個)^[5] の乱数プールを持たせ、独自の乱数生成器でプールを埋めておきます。
operator() が呼ばれるたびにこのプールから乱数を 1 個ずつ取り出して返します。
プールが枯渇すると、独自の乱数生成器を使って改めてプールを埋めます。

Code 3

#include <cstddef>
#include <cstdint>
#include <array>
#include <limits>

class RandomNumberGenerator {
 public:
  using result_type = std::uint8_t;

  static constexpr result_type min() noexcept {
    return std::numeric_limits<result_type>::min();
  }
  static constexpr result_type max() noexcept {
    return std::numeric_limits<result_type>::max();
  }

  RandomNumberGenerator() {
    randomizePool();
  }

  result_type operator()() {
    auto random = pool_[nextIndex_];
    if (++nextIndex_ >= pool_.size()) {
      randomizePool();
      nextIndex_ = 0UZ;
    }
    return random;
  }

 private:
  static constexpr std::size_t poolSize_{256UZ};

  std::array<result_type, poolSize_> pool_{};
  std::size_t nextIndex_{0UZ};

  void randomizePool() {
    GenerateRandom(pool_.data(), pool_.size());
  }
};

エラーの処理を省略しているのと、 RandomNumberGenerator クラスのコピー/ムーブ可能性 (をどうすべきか) は考えていません^[6]。

使い方

実装した RandomNumberGenerator クラスは uniform random bit generator 要件を満たします。
これはどういう意味かと言いますと、 std::random_device クラスと同様に扱えるということです。

例 1: 直接使う

必要な乱数の個数が一定以下であれば、 RandomNumberGenerator クラスを直接使ってもよいでしょう。

Code 4

#include <iostream>
#include <random>
#include "RandomNumberGenerator.hpp"

int main() {
  RandomNumberGenerator gen;
  std::uniform_int_distribution<> dice{1, 6};
  for (int i{0}; i < 10; ++i) {
    std::cout << dice(gen) << '\n';
  }
}

std::uniform_int_distribution::operator() メンバ関数テンプレートはテンプレート引数の型に uniform random bit generator 要件を要求します。
先ほど実装した RandomNumberGenerator クラスは同要件を満たすので std::uniform_int_distribution と組み合わせて使えるわけです。

std::uniform_int_distribution クラステンプレートが満たしている random number distribution 要件では、 operator() の計算量は引数の uniform random bit generator オブジェクトの償却定数回数の呼び出しと規定されています (参考文献 1 の 28.5.3.6 [rand.req.dist])。
これはつまり、先ほどの Code 4 において、 dice() の呼び出し回数と gen() の呼び出し回数が一致する保証はないということです。

例 2: random number engine のシードとして使う

疑似乱数生成器のシード (seed) を提供するために用いることもできます。

Code 5

#include <iostream>
#include <random>
#include "RandomNumberGenerator.hpp"

int main() {
  RandomNumberGenerator gen;
  std::mt19937 engine{gen()};
  std::uniform_int_distribution<> dice{1, 6};
  for (int i{0}; i < 1'000; ++i) {
    std::cout << dice(engine) << '\n';
  }
}

この例ではサイコロを 1,000 回振るため、 RandomNumberGenerator クラスの乱数プールを使い切ってしまいます。
プールが枯渇すると再びハードウェア乱数生成器にアクセスして乱数を生成させるのでコストがかかります。
そのコストを許容できない場合、かつ、疑似乱数でもよい (真の乱数でなくてもよい) 場合にはこの方法が使えます。

まとめ

本記事の前提として、標準ライブラリが提供している std::random_device ではなく、わざわざ独自の乱数生成器を使いたいという事情があります。
そのため、例 2 のような疑似乱数生成器 (std::mt19937 など) の使用は許容できないかもしれません。
それでも、例 1 のように std::uniform_int_distribution などの分布生成器が使えるのはメリットだと思います。

おわりに

本記事では、独自の乱数生成器であっても、要件に合わせて実装すれば標準ライブラリと組み合わせて使えることを示しました。

標準ライブラリのうち、 (狭義の) STL と呼ばれるコンテナやアルゴリズムについても同様のことが言えます。
標準ライブラリは単一目的の部品を組み合わせて使うように設計されているので、それを意識してうまくフィットするような部品として実装するとよいと思います。

参考文献

1. N4950: Working Draft, Standard for Programming Language C++.
2. C++ named requirements: UniformRandomBitGenerator (since C++11) - cppreference.com.
   https://en.cppreference.com/w/cpp/named_req/UniformRandomBitGenerator

脚注

1. CPU が備えている乱数命令とは別です。 SoC の IP コアのひとつかもしれませんし、 SoC とは別のチップかもしれません。

2. 参考文献 1 の 28.5 Random number generation [rand]。

3. まぁ、たいていの場合は std::random_device + std::mt19937 + std::uniform_int_distribution という「定番」の組み合わせですんでしまうのでひとつにまとまっていればと思わないこともありませんが、 std::uniform_int_distribution の恩恵にはよくあずかっています。

4. はなはだおこがましい。

5. NTTP などで指定できるようにしてもよいでしょう。

6. と言いつつも、データメンバ nextIndex_ がイテレータではなく文字どおりインデックスなのは、暗黙的に生成されるコピーコンストラクタでコピーできることを意図しました。