乱数生成Xorshiftを実装しよう

• 

  Xorshiftで乱数を300個生成して表示したところ

乱数について

乱数生成は古くからコンピューターにとってなくてはならないライブラリの一つです。乱数がなければ、ゲームはつまらないものになります。例えば、常に同じカードが配られるカードゲームなど面白くありません。乱数を利用することで、繰り返し遊べるゲームを作ることができます。また、暗号などセキュリティの分野でも乱数が活用されています。

なお、一口に「乱数」と言っていますが、厳密に言うと、計算によって生成する乱数は「疑似乱数」と呼ばれます。サイコロを実際に振って得られる真の乱数とは違って、計算によって乱数っぽく見えるものを生成しているので、このように区別して呼びます。しかし、正確無比なコンピューターを使って、できるだけデタラメな数を生成しようと努力するのですから、その仕組みを学ぶのは面白いものです。

Rustで疑似乱数を生成しよう

興味深いことに、Rustでは標準ライブラリが非常に小さいのが特徴の一つであり、他の言語では当然のようにある乱数生成ライブラリは標準添付されていません。そのため、一般的な用途で乱数を使いたい場合には、Rustの有名ライブラリの一つ「randクレート」をインストールして使います。

しかし、今回はrandクレートを使うのではなく、Xorshiftと呼ばれるアルゴリズムを利用して、ゼロから乱数生成関数を実装してみましょう。

Xorshiftについて

それでは、XorshiftをRustで実装していきましょう。Xorshiftとはその名の通りXOR演算とビットシフト演算を利用した乱数生成アルゴリズムです。2003年にGeorge Marsaglia氏が提案したアルゴリズムです。XOR演算とビットシフトを数回行うだけで済むため、高速に乱数を生成できるのがポイントです。

どれだけ簡単に算出できるのかは、実際のプログラムを見ると分かりますので、実際のプログラムを見てみましょう。以下がRustでXorshiftを実装したプログラムです。

// アルゴリズムだけを記した未完成のプログラムです
// Xorshiftで乱数を計算 --- (*1)
fn xorshift(seed: &mut u64) -> u64 {
    *seed ^= *seed << 13;
    *seed ^= *seed >> 7;
    *seed ^= *seed << 17;
    *seed
}
fn main() {
    // 適当な値で乱数シードを初期化 --- (*2)
    let mut seed = 123456789;
    // 7回乱数を表示 --- (*3)
    for _ in 1..=7 {
        // 1から6の乱数を生成する --- (*4)
        let r = xorshift(&mut seed) % 6 + 1;
        println!("{}", r);
    }
}

上記のプログラムを「xorshift.rs」という名前で保存しましょう。 プログラムをコンパイルして実行するには、ターミナルで次のコマンドを実行します。

rustc ./xorshift.rs && ./xorshift

実行すると次のように乱数を7個表示します。

• 

  Xorshiftで乱数を生成して表示したところ

プログラムを詳しく確認してみましょう。プログラム(＊1)の関数xorshiftを見てみましょう。XOR演算とビットシフトだけで乱数を生成します。

(＊2)では乱数を生成するのに必要となる乱数シード(種)を指定します。ここで指定した乱数の値を基にして乱数を生成します。この値を変更することで生成する乱数が変化します。

(＊3)ではfor文を利用して7回繰り返し乱数を生成して表示します。(＊4)では割り算の余りを計算する演算子「%」を利用して指定の範囲の乱数を得ます。ここでは1から6の乱数を生成します。

関数宣言にある「&mut u64」ってどんな型？

ちなみに、Rustが初めての人が疑問に思うポイントは、上記プログラムにある関数xorshiftの引数型にある「&mut u64」の部分でしょうか。

そもそもRustで関数を宣言する場合、以下のような書式で記述します。ローカル変数を使う時には、型推論の機能があるので、明示的に型宣言をする機会はそれほどないのですが、関数を宣言するときには、引数の型や戻り値の型を明示的に宣言する必要があります。

[書式] Rustの関数宣言
fn 関数名( 引数名: 引数型 ) -> 戻り値型 {
    // ここに関数の定義
}

基本を確認したところで「&mut u64」の型宣言について考察しましょう。

まずu64というのは、符号なし64ビット整数を意味します。他にも、Rustで符号なし整数には、u8、u16、u32、u64、u128があり型名にビットサイズを含んでいます。u8では0から255までの値を表現できます。そして、u64では64ビット(8バイト)の整数0から18446744073709551615までの値を表現できます。

次に「&型名」のように記述すると参照型(C言語のポインタのようなもの)になります。ただし「&型名」と書いた場合には値を変更することはできず、値を変更したい場合には「&mut 型名」のように記述します。

つまり、関数xorshiftの引数seedの型「&mut u64」は、符号なし64ビット整数u64の変更可能な参照という意味になります。

なお、引数seedを変更可能にした理由ですが、乱数の生成では、生成した乱数の値が次回の乱数生成のシードに使われます。そのため、シードを更新する必要があるので変更可能としたのです。

現在時刻を利用して乱数を初期化するように改良しよう

上記のプログラムでは、乱数シードに固定値123456789を設定しているため、何度プログラムを実行しても毎回同じ乱数が表示されます。同じ順番で乱数が生成されてしまうのは問題があります。

そこで、多くの処理系では、乱数のシードとして、現在時刻やキー入力やマウス操作のタイミングなどを用いて乱数シードを初期化しています。

ここでは、現在時刻を利用して、実行するたびに異なる乱数が表示されるようにしてみましょう。

use std::time::SystemTime;

// Xorshiftで乱数を計算 --- (*1)
fn xorshift(seed: &mut u64) -> u64 {
    *seed ^= *seed << 13;
    *seed ^= *seed >> 7;
    *seed ^= *seed << 17;
    *seed
}
// 現在時刻(UNIXタイム)を取得 --- (*2)
fn get_time_msec() -> u64 {
    let now = SystemTime::now();
    return match now.duration_since(SystemTime::UNIX_EPOCH) {
        Ok(t) => t.as_micros() as u64,
        Err(_) => 0,
    }
}
fn main() {
    // 現在時刻でシードを初期化 --- (*3)
    let mut seed = get_time_msec() ^ 123456789;
    // 300個の乱数を表示 --- (*4)
    for _ in 0..300 {
        let r = xorshift(&mut seed) % 6 + 1;
        print!("{}, ", r);
    }
    println!("");
}

上記のプログラムを「xorshift2.rs」という名前で保存しましょう。 そして、以下のターミナルで以下のコマンドを実行すると、コンパイルしてプログラムを実行します。

rustc ./xorshift2.rs && ./xorshift2

プログラムを実行すると、1から6まで、300個の乱数が表示されます。

• 

  現在時刻をシードとして300個の乱数を表示したところ

簡単にプログラムを確認してみましょう。(＊1)ではXorshiftアルゴリズムで乱数を生成します。(＊2)は現在時刻をUNIXタイム（ミリ秒単位）で取得し、符号なし64ビット整数(u64)にして返します。なおUNIXタイムというのは、1970年1月1日午前0時0分0秒からの経過秒数です。そして、(＊3)では現在時刻を適当な値でXOR演算した値を乱数のシードに設定します。最後の(＊4)では乱数を300個生成して画面に表示します。

まとめ

以上、今回はRustで乱数生成アルゴリズムのXorshiftを実装してみました。Rustでこのアルゴリズムを実装する際のポイントは、乱数のシードをどのように扱うのかという部分です。

他の言語の乱数ライブラリではシードをグローバル変数に記録しておくことが多いのですが、Rustではグローバル変数が非推奨であるため簡単には使えません。そこで、今回紹介したプログラムでは、関数の引数に乱数シードを毎回指定するようにしました。なお、Rustの人気ライブラリであるrandクレートでは、乱数シードを構造体のフィールドに記録しています。

なお、乱数生成のアルゴリズムは他にもいろいろ種類があり、その仕組みを学ぶのは面白いものです。いろいろなアルゴリズムが公開されているので調べてみて、自分で実装してみると良いでしょう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。