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

Rustは実行効率や安全性を重視した人気のプログラミング言語ですが、難しいと言われることもあります。本連載ではいろいろな有名アルゴリズムを解くことでRustに慣れていきます。今回は、乱数生成アルゴリズムのXorshiftを実装してみましょう。

○乱数について

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

なお、一口に「乱数」と言っていますが、厳密に言うと、計算によって生成する乱数は「疑似乱数」と呼ばれます。サイコロを実際に振って得られる真の乱数とは違って、計算によって乱数っぽく見えるものを生成しているので、このように区別して呼びます。しかし、正確無比なコンピューターを使って、できるだけデタラメな数を生成しようと努力するのですから、その仕組みを学ぶのは面白いものです。
○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 > 7;
*seed ^= *seed 戻り値型 {
// ここに関数の定義
}

基本を確認したところで「&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を設定しているため、何度プログラムを実行しても毎回同じ乱数が表示されます。同じ順番で乱数が生成されてしまうのは問題があります。

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

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

.