C言語 乱数生成アルゴリズム比較:どれが最適?【性能評価】

C言語 乱数生成アルゴリズム比較:どれが最適?【性能評価】

乱数生成は、シミュレーション、ゲーム開発、暗号化、統計分析など、様々な分野で不可欠な要素です。C言語には、rand()関数をはじめとする標準ライブラリの乱数生成機能が存在しますが、その品質や性能は、特定の用途には十分ではない場合があります。そこで、本記事では、C言語で利用可能な代表的な乱数生成アルゴリズムを比較検討し、それぞれの特性、性能、および適用場面について詳細に解説します。

1. 乱数生成の基礎

乱数生成アルゴリズムは、決定的な計算によって、統計的にランダムに見える数列を生成します。重要なのは、真のランダム性(物理的な現象に基づいた乱数生成)とは異なり、コンピュータで生成される乱数はあくまで擬似乱数であるという点です。

1.1 乱数の品質評価指標

擬似乱数生成アルゴリズムの品質を評価するためには、いくつかの重要な指標があります。

  • 一様性: 生成される乱数列が、定義された範囲内で均等に分布していること。特定の値に偏りがないことが重要です。
  • 独立性: 乱数列の中の各要素が、他の要素と統計的に独立していること。過去の値から次の値を予測できないことが求められます。
  • 周期性: 乱数列が繰り返されるまでの長さ。周期が短いと、シミュレーションなどで同じパターンが繰り返し発生し、結果の信頼性が損なわれます。
  • 統計的検定: 乱数列が様々な統計的検定(カイ二乗検定、コルモゴロフ-スミルノフ検定など)に合格すること。これらの検定は、乱数列の偏りやパターンを検出するために用いられます。

1.2 乱数生成におけるシード値

乱数生成アルゴリズムは、シード値と呼ばれる初期値に基づいて乱数列を生成します。同じシード値を設定すると、常に同じ乱数列が生成されます。これは、デバッグや再現性の確保に役立ちますが、セキュリティが重要な用途では、予測可能なシード値を使用することは避けるべきです。

2. C言語における代表的な乱数生成アルゴリズム

2.1 rand()関数 (標準Cライブラリ)

  • アルゴリズム: 線形合同法 (Linear Congruential Generator, LCG) が一般的ですが、実装はコンパイラや環境によって異なります。
  • 特徴:
    • 標準ライブラリに含まれているため、移植性が高い。
    • 実装が簡単で、高速に乱数を生成できる。
    • 周期が短く、統計的な品質が低い傾向がある。特に、上位ビットに偏りが見られることが多い。
  • 使用例:

“`c

include

include

include

int main() {
// 現在時刻をシード値として設定
srand(time(NULL));

// 0から99までの乱数を5つ生成
for (int i = 0; i < 5; i++) {
printf(“%d\n”, rand() % 100);
}

return 0;
}
“`

  • 注意点:
    • rand()関数は、統計的な品質が低い可能性があるため、本格的なシミュレーションや暗号化には不向きです。
    • srand()関数でシード値を設定する際には、time(NULL)のように変化する値を使用することが推奨されます。
    • RAND_MAX マクロは、rand()関数が生成する乱数の最大値を定義します。生成範囲を調整する際に利用できます。

2.2 メルセンヌ・ツイスタ (Mersenne Twister, MT19937)

  • アルゴリズム: ひねり積フィードバックシフトレジスタ (Twisted Generalized Feedback Shift Register) を用いたアルゴリズム。
  • 特徴:
    • 非常に長い周期 (219937 – 1) を持つ。
    • 統計的な品質が高く、様々な統計的検定に合格する。
    • 計算量が比較的多く、rand()関数よりも遅い。
    • 実装が複雑。
  • 使用例:

“`c

include

include

include

// メルセンヌ・ツイスタの実装 (下記は簡略版です。通常はより洗練された実装を利用します)

define N 624

define M 397

define MATRIX_A 0x9908b0dfUL / constant vector a /

define UPPER_MASK 0x80000000UL / most significant w-r bits /

define LOWER_MASK 0x7fffffffUL / least significant w-r bits /

static unsigned long mt[N]; / the array for the state vector /
static int mti=N+1; / mti==N+1 means mt[N] is not initialized /

/ initializes mt[N] with a seed /
void init_genrand(unsigned long s)
{
mt[0]= s & 0xffffffffUL;
for (mti=1; mti> 30)) + mti);
/ See Knuth TAOCP Vol2, 3rd Ed, P.106 for multiplier. /
/ In the previous versions, MSBs of the seed affect /
/ only MSBs of the array mt[]. /
/ 2002/01/09 modified by Makoto Matsumoto /
mt[mti] &= 0xffffffffUL;
/ for >32 bit machines /
}
}

/ generates a random number on [0,0xffffffff]-interval /
unsigned long genrand_int32(void)
{
unsigned long y;
static unsigned long mag01[2]={0x0UL, MATRIX_A};
/ mag01[x] = x * MATRIX_A for x=0,1 /

if (mti >= N) { /* generate N words at one time */
    int kk;

    if (mti == N+1)   /* if init_genrand() has not been called, */
        init_genrand(5489UL); /* a default initial seed is used   */

    for (kk=0;kk<N-M;kk++) {
        y = (mt[kk]&UPPER_MASK) | (mt[kk+1]&LOWER_MASK);
        mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    for (;kk<N-1;kk++) {
        y = (mt[kk]&UPPER_MASK) | (mt[kk+1]&LOWER_MASK);
        mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    y = (mt[N-1]&UPPER_MASK) | (mt[0]&LOWER_MASK);
    mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

    mti = 0;
}

y = mt[mti++];

/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);

return y;

}

int main() {
// 現在時刻をシード値として設定
init_genrand(time(NULL));

// 0から99までの乱数を5つ生成
for (int i = 0; i < 5; i++) {
printf(“%lu\n”, genrand_int32() % 100);
}

return 0;
}
“`

  • 注意点:
    • メルセンヌ・ツイスタは、メモリ使用量がrand()関数よりも多い。
    • 暗号化用途には、より安全な乱数生成アルゴリズム (例: AES CTRモード) が推奨されます。

2.3 Xorshift シリーズ

  • アルゴリズム: ビット演算 (XOR, シフト) を組み合わせた高速なアルゴリズム。
  • 特徴:
    • 実装が非常に簡単で、高速に乱数を生成できる。
    • メモリ使用量が少ない。
    • 周期はメルセンヌ・ツイスタほど長くはないが、rand()関数よりは長いことが多い。
    • 種類が多く、パラメータによって品質が異なる。
  • 種類: Xorshift, Xorshift+, Xoshiro, Xoroshiro など
  • 使用例:

“`c

include

include

include

// Xorshift32の実装
static unsigned int xorshift_state = 123456789;

unsigned int xorshift32(void) {
unsigned int x = xorshift_state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return xorshift_state = x;
}

// シード値の設定
void xorshift32_seed(unsigned int seed) {
xorshift_state = seed;
}

int main() {
// 現在時刻をシード値として設定
xorshift32_seed(time(NULL));

// 0から99までの乱数を5つ生成
for (int i = 0; i < 5; i++) {
printf(“%u\n”, xorshift32() % 100);
}

return 0;
}
“`

  • 注意点:
    • Xorshift シリーズは、パラメータによっては統計的な品質が低い場合があるため、適切なパラメータを選択することが重要です。
    • xorshift_state の初期値(シード値)は、0以外の値にする必要があります。

2.4 線形フィードバックシフトレジスタ (Linear Feedback Shift Register, LFSR)

  • アルゴリズム: シフトレジスタとXOR演算を組み合わせたアルゴリズム。
  • 特徴:
    • 実装が簡単で、ハードウェア実装にも適している。
    • 周期はレジスタの長さに依存する。
    • 統計的な品質は低い傾向がある。
  • 使用例:

“`c

include

include

include

// LFSRの実装 (16ビット)
static unsigned short lfsr_state = 0xACE1u;
static unsigned short lfsr_period = 0;

unsigned short lfsr_step(void) {
lfsr_period++;
unsigned short bit = ((lfsr_state >> 0) ^ (lfsr_state >> 2) ^ (lfsr_state >> 3) ^ (lfsr_state >> 5) ) & 1u;
lfsr_state = (lfsr_state >> 1) | (bit << 15);
return lfsr_state;
}

// シード値の設定
void lfsr_seed(unsigned short seed) {
lfsr_state = seed;
lfsr_period = 0;
}

int main() {
// 現在時刻をシード値として設定
lfsr_seed(time(NULL));

// 0から99までの乱数を5つ生成
for (int i = 0; i < 5; i++) {
printf(“%hu\n”, lfsr_step() % 100);
}

return 0;
}
“`

  • 注意点:
    • LFSRは、周期が比較的短く、統計的な品質が低い傾向があるため、用途は限られます。
    • 適切なフィードバック多項式を選択することが重要です。

3. 性能評価

上記の乱数生成アルゴリズムの性能を比較するために、以下の観点から評価を行います。

  • 速度: 乱数生成にかかる時間。
  • メモリ使用量: アルゴリズムが使用するメモリの量。
  • 統計的品質: 生成される乱数列の統計的な偏りの有無。

3.1 速度

速度の評価は、各アルゴリズムで一定数の乱数を生成し、その時間を計測することで行います。以下は、簡単なベンチマークコードの例です。

“`c

include

include

include

define NUM_ITERATIONS 10000000

// rand() の速度計測
double benchmark_rand() {
clock_t start = clock();
for (int i = 0; i < NUM_ITERATIONS; i++) {
rand();
}
clock_t end = clock();
return (double)(end – start) / CLOCKS_PER_SEC;
}

// xorshift32 の速度計測
double benchmark_xorshift32() {
clock_t start = clock();
xorshift32_seed(time(NULL)); // シード初期化
for (int i = 0; i < NUM_ITERATIONS; i++) {
xorshift32();
}
clock_t end = clock();
return (double)(end – start) / CLOCKS_PER_SEC;
}

// メルセンヌ・ツイスタの速度計測 (上記の例を参考に実装してください)
double benchmark_mt19937() {
clock_t start = clock();
init_genrand(time(NULL));
for (int i = 0; i < NUM_ITERATIONS; i++) {
genrand_int32();
}
clock_t end = clock();
return (double)(end – start) / CLOCKS_PER_SEC;
}

int main() {
srand(time(NULL)); // rand() のシード初期化

printf(“rand() time: %f seconds\n”, benchmark_rand());
printf(“xorshift32 time: %f seconds\n”, benchmark_xorshift32());
printf(“mt19937 time: %f seconds\n”, benchmark_mt19937());

return 0;
}
“`

3.2 メモリ使用量

メモリ使用量の評価は、各アルゴリズムが使用する変数(状態変数など)のサイズを計測することで行います。

  • rand()関数: ほとんどの場合、状態変数は整数型変数1つ程度。
  • メルセンヌ・ツイスタ: 状態変数として大きな配列 (例: 624個の32ビット整数) を使用。
  • Xorshift: 状態変数として整数型変数1つ程度。
  • LFSR: 状態変数として整数型変数1つ程度。

3.3 統計的品質

統計的品質の評価は、Dieharder や TestU01 などの乱数検定スイートを用いることで行います。これらのツールは、乱数列に対して様々な統計的検定を実行し、その結果をレポートします。

4. アルゴリズム選択の指針

どの乱数生成アルゴリズムを選択するかは、アプリケーションの要件によって異なります。

  • 高速性: 速度が最優先される場合 (例: 大量の乱数を必要とする高速なシミュレーション): rand()関数や Xorshift シリーズが候補となります。
  • 品質: 統計的な品質が重要な場合 (例: 正確なシミュレーション、統計分析): メルセンヌ・ツイスタが適しています。
  • メモリ使用量: メモリ使用量が限られている場合 (例: 組み込みシステム): rand()関数、Xorshift シリーズ、LFSR が候補となります。
  • セキュリティ: 暗号化用途など、セキュリティが重要な場合: 専用の暗号論的擬似乱数生成器 (Cryptographically Secure Pseudo-Random Number Generator, CSPRNG) を使用する必要があります。例えば、OpenSSLなどの暗号ライブラリが提供する関数などが利用できます。

5. その他の乱数生成アルゴリズム

上記以外にも、様々な乱数生成アルゴリズムが存在します。

  • WELL (Well Equidistributed Long-period Linear): メルセンヌ・ツイスタよりも統計的品質が高いとされるアルゴリズム。
  • PCG (Permuted Congruential Generator): 高速で統計的な品質も高いとされる比較的新しいアルゴリズム。

6. C++ での乱数生成

C++11 以降では、<random> ヘッダーファイルで、より高度な乱数生成機能が提供されています。std::mt19937 (メルセンヌ・ツイスタ), std::ranlux48, std::minstd_rand など、様々な乱数生成エンジンと分布関数を利用できます。

“`c++

include

include

int main() {
std::random_device rd{};
std::mt19937 gen{rd()}; // メルセンヌ・ツイスタエンジン
std::uniform_int_distribution<> distrib{1, 6}; // 1から6までの整数を均等に生成

for (int n = 0; n < 10; ++n) {
std::cout << distrib(gen) << ‘ ‘;
}
std::cout << std::endl;
}
“`

C++の <random> ライブラリは、より柔軟で安全な乱数生成を行うために推奨されます。

7. まとめ

本記事では、C言語で利用可能な代表的な乱数生成アルゴリズムについて、それぞれの特性、性能、および適用場面について解説しました。rand()関数は手軽に利用できますが、品質が低い可能性があるため、用途によってはより高度なアルゴリズム (メルセンヌ・ツイスタ、Xorshift シリーズなど) を検討する必要があります。アプリケーションの要件を十分に理解し、適切なアルゴリズムを選択することが重要です。また、セキュリティが重要な用途では、暗号論的に安全な乱数生成器を使用する必要があります。C++を使用する場合は、<random> ライブラリの利用を検討してください。

参考文献

  • Park, S. K., & Miller, K. W. (1988). Random number generators: Good ones are hard to find. Communications of the ACM, 31(10), 1192-1201.
  • Matsumoto, M., & Nishimura, T. (1998). Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), 8(1), 3-30.
  • Marsaglia, G. (2003). Xorshift RNGs. Journal of Statistical Software, 8(14), 1-6.
  • O’Neill, M. E. (2015). PCG: A family of simple fast space-efficient statistically good algorithms for random number generation. Technical Report HMC-CS-2014-0905, Harvey Mudd College.

補足

  • 上記のベンチマークコードはあくまで参考です。より正確な性能評価を行うためには、コンパイラ最適化、CPUアーキテクチャ、OSなどの環境を考慮する必要があります。
  • 乱数生成アルゴリズムの実装は、様々なバリエーションが存在します。本記事で紹介した実装例は、あくまで一例です。
  • 乱数生成アルゴリズムに関する最新の研究動向を常に把握することが重要です。

コメントする

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

上部へスクロール