キャリー付き乗算法（MWC法）で乱数を生成するC++プログラムの実装方法

キャリー付き乗算法（MWC法）とは

キャリー付き乗算法（Multiply-With-Carry、略称MWC法）は、1991年にMarsagliaとZamanによって提案されたキャリー付き加算法（Add-With-Carry）ジェネレータの変種です。この手法の最大の利点は、コンピュータが最も得意とする単純な整数演算だけで動作するため、非常に高速に乱数列を生成できる点にあります。さらに、生成される乱数列の周期は約2⁶⁰から2^2000000にまで及ぶ、きわめて長い周期を持つことも大きな特徴です。

MWC法では、基数bはコンピュータのワードサイズと一致するように選ばれ、乗数aとラグr（遅延量）によって法p = ab^r − 1が決定されます。ここで、aは法pが素数となり、かつ長い周期が得られるように慎重に選択されます。

アルゴリズム

開始
   maximum_sequence_elements、b、r、c[maximum_sequence_elements]、
   x[maximum_sequence_elements] を宣言する
   変数 maximum_sequence_elements、b、r を読み込む
   m = rand() mod b
   c[0] = rand() mod m
   x[0] = rand() mod b
   i = 1 から maximum_sequence_elements まで以下を繰り返す
      x[i] = (m * x[i - r] + c[i - 1]) mod b
      c[i] = (m * x[i - r] + c[i - 1]) / b
      数列を出力する
   繰り返し終了
終了

サンプルコード

以下は、C++でMWC法を実装したサンプルプログラムです。

#include <iostream>
using namespace std;
int main(int argc, char **argv) {
    int max_Seq_Elements = 7;
    int b = 300;
    int m = rand() % b;
    int r = 1;
    int c[max_Seq_Elements];
    int x[max_Seq_Elements];
    c[0] = rand() % m;
    x[0] = rand() % b;
    cout << "乱数列は: " << x[0];
    for (int i = 1; i < max_Seq_Elements; i++) {
        x[i] = (m * x[i - r] + c[i - 1]) % b;
        c[i] = (m * x[i - r] + c[i - 1]) / b;
        cout << " " << x[i];
    }
    cout << "...";
}

コードのポイント

このプログラムでは、基数bを300に設定し、標準ライブラリのrand()関数を用いて乗数m、初期値x[0]、キャリーc[0]を初期化しています。その後、漸化式 x[i] = (m * x[i−r] + c[i−1]) mod b に従って乱数を順次生成し、同時に新しいキャリー値 c[i] = (m * x[i−r] + c[i−1]) / b を計算して次のステップへ引き継ぎます。なお、実行のたびに異なる乱数列を得たい場合は、rand()を呼び出す前にsrand()で乱数種を設定しておくとよいでしょう。

実行結果

乱数列は: 177 173 226 221 56 157 84...