はじめに
どうも、 @rabeneko と申します。
私は、N予備校( https://www.nnn.ed.nico/ )という学習サイトでプログラミング講師をしております。
N予備校では毎週火曜日と金曜日にプログラミング授業をしておりまして、そこで出た質問の解説をしております。
今回は、その授業中に出た、質問に対する回答をQiitaに書きたいと思います。
プログラミングを学んでいる方・学んでみたい方は、ぜひN予備校の授業を覗いてみてください。
プログラミングと乱数の話
今回は「乱数」についてです。
JavaScriptでは、 Math.random() という関数が用意されていて、実行すると0から1までのランダムな値を取得することができます。
Math.random()
0.6239205706732964
一見これで話は終わりそうなものですが、Math.random()のテキストを読むと、何やら良くわからない文章が…(汗)
Math.random()関数は、 0 以上 1 未満 (0 は含むが、 1 は含まない) の範囲で浮動小数点の擬似乱数を返します。その範囲ではほぼ均一な分布で、ユーザーは範囲の拡大をすることができます。実装側で乱数生成アルゴリズムの初期シードを選択します。ユーザーが初期シードを選択、またはリセットすることは出来ません。
擬似乱数？初期シード？
Math.random() の提供する乱数は、暗号に使用可能な安全性を備えていません。セキュリティに関連する目的では使用しないでください。代わりに Web Crypto API (より具体的には window.crypto.getRandomValues() メソッド) を使用してください。
安全性？
ただランダムな値を出すだけの関数なのに、何やら不思議な文章が書かれていますね。
一体どういうことなのか、できるだけ分かりやすく説明します。
そもそもプログラミングで乱数は作れない！？
乱数というのは、ランダムな数のことです。
ランダムというのは、 「結果が完全に予測できない状態」 の事を言います。
結論から言うと、プログラミングで「結果が完全に予測できない状態」を作り出すのは無理 なんです。
function double(x) {
return x * 2;
}
このdouble関数に「1」を入れたら、常に「2」が返ってきます。突然「3」が返ってくることは無いですよね。
プログラミングの世界では、どんな複雑な計算をする関数を用意した所で、入力が同じであれば出力は常に同じです。
プログラミングの世界では、 「常に正確な結果を返す」 ことはできますが、 「適当な結果を返す」 ことはできないようになっているんですね。
どんなランダムな抽選機をプログラミングで作っても、プログラミングであるがゆえに、必ずロジックがあって、そのロジックさえ分かれば結果を予測できてしまうんです。
そのため、プログラミングで作る乱数のことを、区別して 「疑似乱数」 と言います。
予測できないものは 「真乱数」 と言います。
世の中のアナログな抽選はうまくできている
週に2回、ロト6っていうクジをやっています。
ロト6は1から43までの数字のうち6つの当たり数字を当てます。
その6つの数字を決めるのは、不公平がないように「夢ロトくん」と呼ばれるアナログな抽選機で抽選しています。
どのボールが落ちてくるのか、全く予想がつきませんね。予測不可能です。
思えば、世の中って全く予想がつかないことばかりですよね。
明日世の中で何が起こるのか、全く想像がつきません。
もし地球、いや宇宙がプログラミングでできていたら、とんでもない技術だと思いませんか？
こういった考えで研究している人もいます。
詳しくは「シミュレーション仮説」で調べてみてください。
疑似乱数の作り方
プログラミングだけでは真乱数は作れませんので、疑似乱数を作るということは分かりましたが、疑似乱数は具体的にはどのように作るのでしょうか。
元も子もないことを言いますと、ここは数学の分野で、めちゃくちゃ凄い数学者のみなさんが長い年月かけて色々考えに考えられている分野です。
ですので、私も含め数学の素人は 「疑似乱数を自作するぞ」と思わずに、疑似乱数を作るライブラリを使うのが一番 です。
さておき、少しは考え方を知っておくのが良いと思いますので、簡単に触りだけ紹介します。
線形合同法
一番簡単な考え方、それが線形合同法です。
これはまず、数字4つ(A・B・C・D)を決めます。
そして、
- Aを、Bで掛け算して、Cを足して、Dで割った結果の余りを乱数とする
- 乱数の結果はAに保存し、次の乱数は前回の乱数の結果から出す
という関数を作ります。
試しに、数字4つを「1」「3」「1」「10」として作ってみたのが以下の関数です。
let x = 1;
function random() {
x = (x * 3 + 1) % 10;
return x;
}
これでrandom関数を実行すると、4という数字が返ってきます。
random()
4
で、もう一度実行すると
random()
3
で、もう一度実行すると
random()
0
となります。ちょっと乱数っぽいですよね。
最後10で割った余りをだしていますから、結果は
「0」「1」「2」「3」「4」「5」「6」「7」「8」「9」
のどれかになります。
ではこのrandom関数を使って、
「0」「1」「2」「3」「4」だったら「表」
「5」「6」「7」「8」「9」だったら「裏」
となるコイントスゲームを作ってみましょう。
let x = 1;
function random() {
x = (x * 3 + 1) % 10;
return x;
}
function toss() {
if (random() <= 4) {
console.log('表');
}
else {
console.log('裏');
}
}
toss関数を実行するとコイントスの結果が出力されます。
toss()
表
toss()
表
toss()
表
toss()
表
toss()
表
あれれ・・・何回やっても「表」しか出てきません・・・
ちなみにロジック的に裏が出ることはありません。
なぜかというのは、乱数の結果を並べてみると分かります。
random()
4
random()
3
random()
0
random()
1
random()
4
random()
3
random()
0
random()
1
4、3、0、1の繰り返しになっていますね…
そう、4つの数字をループしているだけなんです。
ではxの値を2にするとどうでしょうか。
(ちなみに、このxの値、最初に計算されるこの数字のことを 「シード」 「初期シード」 と言います。)
random()
7
random()
2
random()
7
random()
2
こちらは7と2の繰り返しです。コイントスの結果は「表」「裏」を繰り返すだけです。
ちなみにxが3の時は、4,3,0,1のループに入ります。
xが5の時は、5,6,9,8のループです。
なので、このrandom関数は、結果が偏っているため、「ずっと表が出続ける」「表と裏が交互に出続ける」「ずっと裏が出続ける」の 3パターンしかないことになります。
となれば、コイントスを2回やれば、3回目の結果は予測できてしまいます。
このように、疑似乱数には 「計算結果が前に出た数字になると、以降はループになる」 という特性があります。
この時のループの長さを 「周期」 と言い、今回のrandom関数の場合は、周期は「2」です。(2と7のループ)
出る数字が偏っていたり、周期が短かったりすると、今後の結果の想像がついてしまうため、「品質が悪く、安全性の低い疑似乱数」となるのです。
つまり疑似乱数では「結果がバラついている」「周期がより長い」ものを使う必要があります。
ちなみに線形合同法でも、最初の4つの数字をとんでもなく大きくすれば、結果がバラついているて周期がより長いものを作ることができます。
しかし、コンピュータは「とんでもなく大きい数字同士の掛け算」をとても苦手としているので、この考え方ですと、どこかで限界が来てしまいます。
メルセンヌ・ツイスタ
とんでもなく凄い数学者の人が思いついたものの一つが「メルセンヌ・ツイスタ」です。
私は数学の素人なので詳細は省きますが、623次元超立方体に均等分布し、2を19937回掛け算した数-1という周期を実現しているそうです。
これは10進数でいう6000桁に相当するようです。
実際の数字を見てみたい方は、以下のブログから見てみてください…
いやーもう凄い！何も考えずにメルセンヌ・ツイスタを使ってれば安心ですね（呆然）
Xorshift
メルセンヌ・ツイスタは、その分計算することも多いようで、「そこまでのものじゃなくていいから、より速く計算結果が出るものがいい」という考え方も出てきました。
XorshiftはGoogle Chromeで採用されている疑似乱数の生成プログラムで、2を128回掛け算した数-1という周期です。
だいたい1000京と1000京を掛け算したぐらいの周期です。
計算ロジックもメルセンヌ・ツイスタに比べるとはるかに簡単です。
まとめ
このように、プログラミングでは真の乱数を生み出すことはできず、疑似乱数を用いて、乱数っぽいものを生成しています。
プログラミングで乱数が必要な時は、自分でつくろうとせず、乱数を生成するライブラリを利用するのが良いでしょう。