C++でミドルスクエア法を使って乱数を生成するプログラムの作成方法

ミドルスクエア法とは

ミドルスクエア法(中央二乗法)は、乱数を生成する最も単純な手法の一つです。「現在の数値を2乗し、その中央の桁を取り出す」という操作を繰り返すことで次々と乱数を作り出します。この手法は計算機科学の父として知られるジョン・フォン・ノイマンによって考案され、初期のコンピュータ時代に擬似乱数生成の方法として使われていました。

基本的な仕組み

例えば4桁の乱数を生成する場合、「1234」を2乗すると 1522756 となります。桁数を揃えるため先頭に0を付けて8桁の「01522756」にし、中央の4桁である「5227」を次の乱数として採用します。この操作を繰り返すことで乱数列が得られます。

ただし、この方法には大きな弱点があります。生成を続けると、同じ数値が何度も繰り返されたり、数列が以前に現れた値へ戻って無限ループに陥ったりする可能性があるのです。n桁の乱数を生成する場合、その周期は最大でも8ⁿ程度に抑えられます。さらに、中央のn桁がすべて0になると、ジェネレータは以後ずっと0を出力し続けます。0の連続は検出しやすいものの、発生頻度が高すぎるため、この手法を実用目的で使うことは現実的ではありません。あくまで擬似乱数生成の仕組みを学ぶための教育的な題材と捉えるのがよいでしょう。

入力 − 乱数の桁数を入力してください:4
出力 − 生成される乱数:6383, 14846, 8067, 51524, .........

アルゴリズム

ミドルスクエア法による乱数生成は、以下の手順で実装できます。

Begin
   middleSquareNumber(number, digit)
   配列を宣言し、next_number = 0 を代入する
   number を2乗した値を変数 sqn に代入する
   digit を 2 で割った値を変数 t に代入する
   sqn を a[t] で割り、その結果を sqn に格納する
   i = 0 から digit まで以下を繰り返す:
      next_number = next_number + (sqn mod (a[t])) * (a[i]);
      sqn = sqn / 10;
   繰り返し終了
   next_number を返す
End.

サンプルコード(C++)

以下は、ミドルスクエア法を実装したC++のサンプルプログラムです。ユーザーから希望する乱数の桁数を入力として受け取り、乱数を順番に生成して画面に表示します。配列 a[ ] は各桁の位(1、10、100…)を表しており、中央の桁を抽出するために使われています。

#include <iostream>
using namespace std;
int a[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
int middleSquareNumber(int number, int digit) {
    int sqn = number * number, next_number = 0;
    int t = (digit / 2);
    sqn = sqn / a[t];
    for (int i = 0; i < digit; i++) {
        next_number += (sqn % (a[t])) * (a[i]);
        sqn = sqn / 10;
    }
    return next_number;
}
int main(int argc, char **argv) {
    cout << "Enter the digit random numbers you want: ";
    int n;
    cin >> n;
    int start = 1;
    int end = 1;
    start = a[n - 1];
    end = a[n];
    int number = ((rand()) % (end - start)) + start;
    cout << "The random numbers are:\n" << number << ", ";
    for (int i = 1; i < n; i++) {
        number = middleSquareNumber(number, n);
        cout << number << ", ";
    }
    cout << ".........";
}

実行結果

プログラムをコンパイルして実行すると、以下のように乱数が出力されます。最初の値は rand() 関数による乱数を種として設定され、以降はミドルスクエア法によって次々と新しい数値が生成されていきます。

Enter the digit random numbers you want: 4
The random numbers are: 6383, 14846, 8067, 51524, .........