Rustで有名アルゴリズムに挑戦(3) 乱数生成Xorshiftを実装しよう

Rustは実行効率や安全性を重視した人気のプログラミング言語ですが、難しいと言われることもあります。本連載ではいろいろな有名アルゴリズムを解くことでRustに慣れていきます。今回は、乱数生成アルゴリズムの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を変更可能にした理由ですが、乱数の生成では、生成した乱数の値が次回の乱数生成のシードに使われます。そのため、シードを更新する必要があるので変更可能としたのです。