Blog

その乱数、適切ですか?

我々が普段生活している中では、気づかないところでコンピュータが生み出す「ランダム(乱数)」にお世話になっています。

スマホのゲームでガチャを回した時、アタリつき自動販売機で飲み物を買った時、モンテカルロ法シミュレーションを実行する時とさまざまです。

20年くらい前に日本人の数学者グループが考案した「メルセンヌツイスタ(MT)」と呼ばれる疑似乱数生成アルゴリズムは多くのプログラミング言語に実装され、今では疑似乱数が欲しいときのデファクトスタンダードになってるんじゃないでしょうか。

疑似乱数とは、乱暴に言っちゃえば「数が出るパターンに周期があるから、厳密には正しくないけど、だいたいランダムな数字の集まり」というものです。詳しいことは専門家の説明を読みましょう。疑似乱数の質はCPUの計算速度とメモリ量で決定するのですが、その中で効率が良い方法のひとつがMTなのです。MTの乱数周期は219937-1と、とても長いので実用に耐えられるわけです。

余談ですが計算資源が貧弱な頃、例えば8bit、16bit時代のテレビゲームは1から255までの数字を良い具合に散らしたテーブルで保持する、なんて無茶をやってます。この場合、乱数列周期28-1非常に短い。

一方、RSA暗号キーの生成など、暗号を作るときには周期性がある疑似乱数を使うと解読される可能性があります。そのため、キーを生成する際に「マウスを無作為に動かせ」「キーボードのキーをしっちゃかめっちゃかに叩け」といった指示が出ていた時代もありました。人為的なランダム入力を乱数の元にしていたわけです。

ところが10年くらい前から、CPUが持つ熱雑音などをもとに暗号化用の乱数がPCのハードウェアから取得できるようになりました。Linux処理系だと/dev/random、/dev/urandomがそれに該当します。

/dev/randomをファイルとして読み出すだけで、システムに溜まっている乱数が手に入ります。ただし、保持している情報量には限りがあるため、次の乱数が生成されるまで「処理をブロッキングする」か「疑似乱数で代用する」という限定条件があります。

前置きが長くなりました。その良質な乱数である/dev/randomがMTの乱数生成の代わりになるかどうか、を簡単なプログラムで検証してみました。

ちなみにphpであれば

これで4byte=32bit長の乱数が整数で入手できます。

ひたすらループを繰り返して、乱数を生成するテストプログラムを私のphp開発環境にて実行してみました。

試行回数(回) MT
(10,000,000回ループ)
/dev/random
(10,000回ループ)
1 2.84585 9.743988
2 2.868848 9.796494
3 2.865435 9.752865
4 2.836898 10.043154
5 2.832968 9.751514
6 2.866058 9.690516
7 2.91101 9.747249
8 2.857296 10.180832
9 2.856203 10.204445
10 2.872247 10.323912
平均 2.8612813 9.9234969

結論から言えば、実行速度的に比べる必要もありませんでした。速度差およそ300倍。

しかし、/dev/randomからの乱数取得も実装コストが低いため、用途と利用シーンによっては利用することも検討してよいのでは、と思います。

 

Author Profile

k.motoki
k.motoki

麺類とゲームをこよなく愛するプログラマ。会社周辺は安くて旨い店が多くて辛いです。(体重的に)

» 投稿一覧
  • Launch Cart次世代ECサイト構築システム 初期月額無料
  • LaunchMovie ECに特化した動画制作サービス

Archive

ページTOPへ