この記事は「C3 Advent Calender」シリーズの24日目の記事です。
初めに
初めまして！私は、C3でGAMEとして活動しているねぎまとと申します。といってもGAMEは難しくてあまり活動できていないんですよね。unityムズカシイ…ダレカタスケテ…
今回の記事にはねぎくんが助っ人としていろいろな場所にスポーンするらしいです。
Y＜ねぎだよ！よろしくね！！
この記事を書くのに至った経緯
まずは一言
ざ け ん な
なんで私がここの担当なのか？確かに記事を書く日にちはいつでもいいよって言ったよ！？だとしてもクリスマスイヴに！！周りの優秀な先輩たちに自分の記事を投稿をする。こんなの心臓がいくつあってもプレッシャーで★爆散★しそうですね。記事の日程を決めるのにあたって疑似乱数というのが使われたらしいですね。というわけで疑似乱数について知ろう（？）ということに至りました。
(実は12/15~12/20までインフルエンザで寝込んでました許してください… すべてはインフルのせいだ！！)
Y＜ねぎまと、無事にAdovent Calender書ききれるんかなぁ……
疑似乱数ってなに？
乱数って何でしょう？
Y＜ランダムな値です!
そうですね。では、これは知っていますか？
プログラミングで乱数は作れない
Y＜何言ってんの！？
みなさんもねぎくんと同じことを思っているところでしょう。私も最初はそう思っていました。実はプログラムで作れるのは乱数ではなく疑似乱数なのです！皆さんの頭の中には？マークで飽和していますね。大丈夫！一つずつ解決していきましょう！！
Y＜よろしくお願いしまーす！！
乱数と疑似乱数の違い
乱数列は次に出る値は絶対に予測できない列のことであり疑似乱数はワンチャン予測可能な列のことを言います。これは例をもとに説明していきましょう。
乱数の例はサイコロです。例えば、
サイコロを2回投げたところ1回目には1,2回目には2が出ました。
では3回目には何の目が出るでしょうか？
Y＜3だと思いまーす！！
ねぎくん…必ずそうなるわけではないでしょう……答えは「わからない」ですよね。分かった人は予知能力を持っていますね。僕にもその能力を分けてほしいな。
Y＜僕にも頂戴！！
それに対して、疑似乱数は漸化式と例えると分かりやすいと思います。
nを1以上の自然数とし、以下の漸化式を定義する。
aₙ₊₁ = aₙ+1, a₁ = 1
このれなら、a₁₀ = 10, a₁₀₀ = 100と予測できますよね。
これをより複雑にすると疑似乱数というものになります。
つまり、乱数は次が予測できない,完全にランダムな数のことで、疑似乱数は次がほぼ予測できないけどルールはある数のことです。偽物の乱数ってこと。
疑似乱数のメリット
なぜ疑似乱数を使うんでしょうか？以下のような理由があるようです。
➀ とても素早く計算できる
Y＜漸化式の計算とか余裕だよ！！
漸化式の計算なんか人間でちょちょいのちょいだもんね。そんな簡単な計算をコンピューターにやらせてみたらもう計算が止まらなくなっちゃうよ。これはとてもうれしいことだね。
➁ 導入が簡単
筆者は、大学の授業でC言語を習ってるくらいしかプログラミング経験がないど初心者でもrand()を使えば疑似乱数マスターだ。こんなにうれしいことはないね。
Y＜C言語ではrand関数を使えば乱数を生成できるもんね！！
➂ 再現可能がある
筆者初めて知ったんだけどシミュレーションとかデバックに乱数を使うことがあるらしい。
Y＜へぇ～そうなんだ！
そういうのをするときにめっちゃ便利なんだって。
疑似乱数のデメリット
そんな便利な疑似乱数君。もちろんデメリットもあるようで…
➀ 完全なランダムではない
ルールが分かってしまえばランダムではなくなります。ランダムではなくなるということは、セキュリティ関係で疑似乱数を使ってしまうと……そんなことは想像もしたくないですね。
Y＜僕の個人情報がもれちゃうの？そんなのやだぁ~…
➁ 周期がある
疑似乱数で出した乱数列には周期があるんだって。つまり、あるタイミングでもとに戻ってきちゃう。これは困った。
総評
疑似乱数は偽物の乱数だけど、便利だから使われてるって感じですね。乱数っぽいのに予想できる可能性がある、いつか自分も予測してみたいなぁ
Y＜ねぎまとくんが預言者になる日もそう遠くはないのかも！？
いろいろな乱数
いままで、乱数いろんな人がいろんな方法で乱数を作ってきました。
つまり、乱数の作り方はいっぱいあるのです。
(別の方法を使っていれば 私がクリスマスイブに記事を出すこと もなかったかもしれない...)
乱数のはじまり
そんな乱数の始まりはいつなんでしょう？乱数の歴史は約100年前からあります。
Y＜以外と短いね。
1927年に統計学者ティペットが最初の乱数を作成しました。国税調査のデータの中位数を使って41600個の数字を生成しました。
1955年には、RAND社が『A Million Random Digits』という100万個の乱数を含む本を出版しました。これは電子ノイズから生成された真の乱数でした。
Y＜乱数の始まりって国税調査から始まってたんだ！？
コンピュータの父
ジョン・フォン・ノイマンさんが疑似乱数生成方法について提案していました。方法は以下のようになっています。
① 4桁の種(シード)から始める。(例:1234)
② シードの値を2乗する。(例:1234² = 1522756)
③ ②の結果の中央をとる。(例:1「5227」56 → 5227)
④ ③の値をシードとして繰り返す。
この方法は簡単ですが周期が短く、すぐに同じパターンを繰り返してしまうという欠点があります。
例:3792² = 14379264 → 3792
Y＜使う数字によっては乱数として機能しなくなるんだね
線形合同法
Y＜いかにも難しそうな名前だなぁ…
1948年にレーマーという人によって提案されました。たしかに難しそうな名前ですね。ですが意外に言っていることは簡単です。線形合同法とは以下の式を指します。
Xₙ₊₁ = (a × Xₙ + c) mod m
ここでa,c,n,mはすべて自然数
なんとこの式を解くだけで乱数として機能する画期的な等式なのです！使い方は超簡単！a,c,Xₙ,mに値を代入するだけで使えます。
例えばa = 5, c = 1,m = 16, X₁ = 7とすると
X₂ = (5 × 7 + 1) mod 16 = 36 mod 16 = 4
X₃ = (5 × 4 + 1) mod 16 = 21 mod 16 = 5
X₄ = (5 × 5 + 1) mod 16 = 26 mod 16 = 10 ……
このように乱数列を生成することが出来ます。これは現在でも広く使われている乱数生成器のうちの1つです。
Y＜なぁんだ、意外と簡単じゃん！
Xorshift
2003年にジョージ・マルサグリアによって提案されました。Xorshiftのプログラムは以下のようになっています。
int x;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
Y＜え？この4行で本当に乱数列として機能しているの？
実は機能しているんです！！
簡単に言うと、
x << 13 は、xを13ビット左にずらしたやつ。(例：0011 0100 1010 1011 → 0110 0000 0000 0000)
x ^= a は、x = x^a
理解すれば単純な式だけど、値はめっちゃ複雑。
私も最初に見たときにナニコレ?となっていましたが、知れば知るほど面白く感じるものやなぁ。これの強みは、ほとんどのプログラミング言語で使用できることや非常に簡単に実装ができることがあります。
日本人が生み出した乱数
ちょこっと昔に戻っちゃいますが1997年に松本眞、西村拓士によってメルセンヌ・ツイスタという方法が開発されました。これは現在最も広く使われている疑似乱数生成器です。
メルセンヌ・ツイスタは、
・メルセンヌ:周期がメルセンヌ素数2^19937 - 1 である
・ツイスタ:ビットをねじる(twist)操作を行う
という名前の由来があります。
周期が2^19937 - 1であるためセキュリティの用途では十分な疑似乱数生成器として扱われます。
おわりに
もうね調べれば調べるほど乱数に対してすげーとしか思えなくなっちゃった。無作為に数字を抽出する作業に意外にも深い歴史があり、それに挑戦する人たちの努力を知れてもう驚いちゃった。俺も来年はGAME制作に向けて色々と挑戦するぞ！！
Y＜頑張って！！僕も応援してるよ！！
低クオリティなこの記事を最後まで読んでくださり本当にありがとうございました！いよいよ長かった「C3 Advent Calender」も明日でラスト！！明日はshinyaさんの記事です。お楽しみに！
Y＜お楽しみに~！！