Skip to content

Latest commit

 

History

History
269 lines (212 loc) · 10.8 KB

philox_engine.md

File metadata and controls

269 lines (212 loc) · 10.8 KB

philox_engine

  • random[meta header]
  • std[meta namespace]
  • class template[meta id-type]
  • cpp26[meta cpp]
  • [mathjax enable]
namespace std {
  template <class UIntType, size_t w, size_t n, size_t r, UIntType... consts>
  class philox_engine;

  using philox4x32 = …;
  using philox4x64 = …;
}
  • philox4x32[link philox4x32.md]
  • philox4x64[link philox4x64.md]

概要

philox_engineクラスは、カウンターベースの乱数アルゴリズム (Counter-based random number generator, CBRNG) のPhilox法による擬似乱数生成エンジンである。

Philox法は、以下のような特徴を持つ：

  1. 小さい容量の状態をもつ (Philox4x32の状態は32ビットの値 * 10個の要素)
  2. 長い周期をもつ (Philox4x32の周期は2130)
  3. ベクトル化・並列化がしやすい

philox_engineは、 $ m = 2^{w}−1 $ であるとして、区間[0, m]の符号なし整数の乱数を生成する。

  • オブジェクトの状態としては、以下をもつ：

    • n個のwビットの符号なし整数からなるシーケンス $X$
    • n/2個のresult_type値からなるシーケンス $K$
    • n個のresult_type値からなるシーケンス $Y$
    • スカラー値i

    ここでそれぞれの値は以下の意味をもつ：

    • $X$ は $ n \cdot w $ ビットの符号なし整数のカウンター値 $ Z=\sum_{j=0}^{n-1}X_{j} \cdot 2^{wj} $ の解釈である
    • $K$ はキー
    • $Y$ は生成された値のバッファ
    • $i$ は $Y$ バッファのインデックス値

  • 乱数生成アルゴリズムは、遷移アルゴリズムを適用したあと、Yのi番目に格納された値を返す

  • 状態遷移は、以下のアルゴリズムで実行される：

    i=i+1
if (i == n){
    Y = Philox(K, X) // 下記参照
    Z = (Z+1)
    i = 0
}

  • Philox関数は、長さn/2のシーケンスKと、長さnのシーケンスXを、長さnのシーケンスYにマッピングする。Philox関数はX内の値にrラウンドのSPN構造 (substitution-permutation network) を適用する。生成アルゴリズムのひとつのラウンドは以下のステップを実行する：

      1. 前のラウンドの出力シーケンスX'（第1ラウンドの場合はX）を並べ替えて中間状態Vを得る： $$ V_{j} = X'_{f(j)} $$ ここでj = 0, …, n-1であり、f(j)は以下のテーブルで定義される (n=2のシーケンスは順列ではない)：
    j=0 j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 j=10 j=11 j=12 j=13 j=14 j=15
    n=2 0 1
    n=4 0 3 2 1
    n=8 2 1 4 7 6 5 0 3
    n=16 0 9 2 13 16 11 4 15 10 7 12 13 14 5 8 1
      1. シーケンス $V$ の要素には以下の計算が適用される： $$ X'{2 \cdot k} = mullo(V{2 \cdot k + 1},\ M_{k},\ w) $$ $$ X'{2 \cdot k + 1} = mulhi(V{2 \cdot k + 1},\ M_{k}, w)\ xor\ key_k^q\ xor\ V_{2 \cdot k} $$
      • ここで以下のように定義する：
        • mullo(a, b, w)関数は、aとbを掛けた剰余の下半分を返す： $ a \cdot b\ mod \ 2^{w} $
        • mulhi(a, b, w)関数は、aとbを掛けた上半分を返す： $ \left( \lfloor (a \cdot b) / 2^{w} \rfloor \right) $ 。kは0, …, n/2-1のインデックスシーケンスである
        • qは0, …, r - 1のラウンドのインデックスである
        • $ key_k^q $ はラウンドqのk番目のラウンドキーであり、 $ key_k^q = \left( K_{k}\ +\ q \cdot C_{k} \right)\ mod\ 2^{w} $
        • $ K_{k} $ はシードで一度生成されたキーであり、seed()関数が呼ばれない限り固定である
        • $ M_{k} $ はmultipliersである
        • $ C_{k} $ はround_constsである

  • 一回のラウンド関数がr回適用されたあと、PhiloxはシーケンスY=X'を返す

  • このクラスオブジェクトのテキスト表現は、 $ K_{0}, …, K_{n/2-1}, X_{0}, …, X_{n-1}, i $ の順で対応する

    • 備考: ストリーム演算子は、必要に応じて $K$ と $X$ から $Y$ を再構築できる

テンプレートパラメータ

  • UIntType : 生成する符号なし整数の型。
  • w : ワードサイズ。状態シーケンス内での各ワードのビット数
  • n : ワード数
  • r : ラウンド数
  • consts : 内部で使用するn個の定数値
    • $ M_{k} $ と $ C_{k} $ の値を表し、以下のようにグループ化される： $ \left[ M_{0}, C_{0}, M_{1}, C_{1}, M_{2}, C_{2}, …, M_{n/2-1}, C_{n/2-1} \right] $

適格要件

  • sizeof...(consts) == nがtrueであること
  • 0 < rがtrueであること
  • 0 < w && w <= numeric_limits<UIntType>::digitsがtrueであること

周期

$ n \cdot 2^{w \cdot n} $

サイズ

$ r \cdot w $ ビット

メンバ関数

構築・シード

名前 説明 対応バージョン
(constructor) コンストラクタ C++26
~philox_engine() = default; デストラクタ C++26
seed シードを設定する C++26
set_counter カウンターを設定する C++26

生成

名前 説明 対応バージョン
operator() 擬似乱数を生成する C++26
discard 指定した回数だけ擬似乱数を生成し、内部状態を進める C++26

静的メンバ関数

エンジンの特性

名前 説明 対応バージョン
min 生成し得る値の最小値を取得する C++26
max 生成し得る値の最大値を取得する C++26

メンバ型

型 説明 対応バージョン
result_type 擬似乱数生成結果の符号なし整数型 UIntType。 C++26

メンバ定数

定数 説明 対応バージョン
static constexpr size_t word_size ワードサイズ。状態シーケンス内での各ワードのビット数。テンプレートパラメータw。 C++26
static constexpr size_t word_count 状態のサイズ。状態シーケンスの要素数。生成される値が再発する程度を調整するための値。テンプレートパラメータn。 C++26
static constexpr size_t round_count ラウンド数。大きいほど乱数の質が高くなり、分布が改善する。テンプレートパラメータr。 C++26
static constexpr array<result_type, n / 2> multipliers カウンター値に対する乗数。 C++26
static constexpr array<result_type, n / 2> ラウンドごとのキー値 C++26
static constexpr result_type default_seed デフォルトのシード値。20111115u C++26

非メンバ関数

名前 説明 対応バージョン
operator== 等値比較 C++26
operator!= 非等値比較 (==により使用可能) C++26
operator<< ストリームへの出力 C++26
operator>> ストリームからの入力 C++26

例

基本的な使い方

#include <iostream>
#include <random>

int main()
{
  std::random_device seed_gen;

  // philox_engineのパラメータ設定済み別名であるphilox4x32を使用する。
  // ランダムなシードを使用して初期化
  std::philox4x32 engine{seed_gen()};

  for (int i = 0; i < 10; ++i) {
    // 乱数を生成
    std::uint32_t result = engine();
    std::cout << result << std::endl;
  }
}
  • std::philox4x32[link philox4x32.md]
  • std::uint32_t[link /reference/cstdint/uint32_t.md]
  • engine()[link philox_engine/op_call.md]

出力例

717409690
3816001420
2063273750
279442752
2836561695
431684143
3973522490
2090827657
748889484
859307553

多次元の乱数を生成する例

#include <print>
#include <random>

struct Vector {
  float x, y, z;
};

int main()
{
  std::uint32_t seed = 12345;

  // 2x2x2個のランダムなベクトルを生成する
  for (std::uint32_t x = 0; x < 2; ++x) {
    for (std::uint32_t y = 0; y < 2; ++y) {
      for (std::uint32_t z = 0; z < 2; ++z) {
        std::philox4x32 engine{seed};
        engine.set_counter({x, y, z, 0});

        std::uniform_real_distribution<float> dist{0, 1.0};

        Vector vec {
          dist(engine),
          dist(engine),
          dist(engine)
        };
        std::println("{},{},{}", vec.x, vec.y, vec.z);
      }
    }
  }
}
  • std::philox4x32[link philox4x32.md]
  • engine.set_counter[link philox_engine/set_counter.md]
  • uniform_real_distribution[link /reference/random/uniform_real_distribution.md]
  • std::uint32_t[link /reference/cstdint/uint32_t.md]
  • dist(engine)[link /reference/random/uniform_real_distribution/op_call.md]

出力例

0.8202247,0.18554558,0.8234037
0.4850654,0.9281539,0.43299365
0.26559144,0.98589313,0.31661463
0.88831127,0.4234704,0.9224362
0.0027833676,0.14429614,0.8929877
0.6186795,0.6290597,0.46478647
0.17204352,0.54567194,0.1469554
0.7067667,0.48607737,0.6880201

バージョン

言語

  • C++26

処理系

参照