整数の乱数に関しての単純な疑問

特に何か問題があったわけでもないんですが、気になったので質問をしました。

乱数生成関数は元となる、乱数を生成し、それを実際に必要とする形に変形して使うと思うのですが
そのときに

整数値に変形している。
一定以上大きな範囲のものである。

この場合、絶対に出てこない整数が発生すると思うんですが、

その生成したい範囲に合わせてバイト数の違う乱数生成関数を用意した方がよいということですかね？

まぁ、めったにそんなに大きなもの必要にならない気がしましたが…

あと、もう一つ。

例として、1バイトの乱数を生成したときにそれを1~7の値に収める際、

7 * ({乱数の値} + 1)/256 (切り上げ)

のようにして、乱数を作りがちですが、数値によって微妙に偏りますよね？

(こういうことが起こらないために、ソシャゲとかパチンコで256分の～みたいな表記が出てくるのかなぁ、とも思いました。なんか、あまり気にしてなかったけれども、そう考えると面白い(笑))

真に1/7の乱数を作るなら乱数を生成したときに

035 → 1
3671 → 2
72107 → 3
108143 → 4
144179 → 5
180215 → 6
216251 → 7
252255 → もう一回

みたいにしなきゃいけないですよね？

行動規範の内容に同意します

回答3件

ベストアンサー

Rubyのrand()の実装を確認しましたが、マスクを取って越えていればその値を捨てて再度取得としてします。

Ruby 2.6.0のソースでの該当部分

rand()はRandom.rand()を呼び出して、引数が整数ならば最終的にCでのlimited_rand()を呼び出します。引数が2^32より小さければ、次のコードが本質です。

C
1    do {
2        val = genrand_int32(mt) & mask;
3    } while (limit < val);

limitが制限値で、0からlimitまで(limitを含める)の乱数を生成します。genrand_int32(mt)はメルセンヌツイスタ乱数生成機構造体であるmtからint32の乱数を取得します。msakはlimitに対するマスク値です。valが返す値になります。

例えばlimitが
42(00000000000000000000000000101010)
の場合maskは
63(00000000000000000000000000111111)
になります。ここでgenrand_int32(mt)が
1778888503(01101010000001111010111100110111)
を取得したとしましょう。マスク値と&をとって、valは55になりますが、これは42を越えているので、捨てられます。なので、次のループに移ります。今度は
1119376133(01000010101110000101001100000101)
を取得したとしましょう。マスク値と&を取るとvalは5になりますので、これは42以下となり、この数値を返します。

Rubyが乱数生成に使っているメルセンヌツイスタはビット単位で統計的に均等分布していることがわかっています。マスクを取って残った値も統計的にランダムです。そこから越えてしまっている場合だけ捨てて乱数を再度回すという方法を取っていると言うことです。

ちゃんとした言語では0からある値までの整数の乱数を生成する関数が標準で備わっており、それらの実装も同じようになっているはずです。メルセンヌツイスタのような品質の良い擬似乱数生成機で実装されていれば1/7も統計的な確率としては問題ないと思います。

注意が必要な言語

JavaScriptのMath.random()は[0, 1)の浮動小数点数を返す物しか標準で備わっていいません。今のところ、整数を掛けて、Math.floor()を取る以外に方法はありません(正確さは落ちる)。
PHP 7.1未満のrand()は品質の悪い擬似乱数生成機を使っています。7.1以上を使うかmt_rand()(メルセンヌツイスタ)を使うべきでしょう(7.1からrand()がmt_rand()を使うようになりました)。
ほとんどの環境においてC標準のrand()は品質の悪い擬似乱数生成機(線形合同法)であるためそもそも使うべきではありません。
C#の擬似乱数生成機はE. Donald Knuthの減算乱数生成機アルゴリズムの変更版を使っているようです。品質はどうなのかは詳しく調べてないのでわかりませんが、種の選び方が悪いとよろしくないようです。
Javaの擬似乱数生成機も品質の悪い線形合同法を使っているそうですので、統計などには使ってはいけません。

投稿2019/01/20 10:50

編集2019/01/23 09:50

raccy

総合スコア21749

GrayWingAliance

2019/01/20 11:31 編集

なるほど、言語によって選択する関数や留意点は全く違ってくるのですか。このRubyの実装はすごいですね… すごい簡潔で重さもなさそうです。感動を覚えました… メルセンヌツイスタの一様性は実測でなのか、理論的に完全に証明されているのか、が気になるので調べてみようと思います！

行動規範の内容に同意します

この場合、絶対に出てこない整数が発生すると思うんですが、

その生成したい範囲に合わせてバイト数の違う乱数生成関数を用意した方がよいということですかね？

はい、乱数ルーチンによって出てくる値の範囲が決まっていますので、それより大きな値を均等に生成するには、2回以上呼び出すことが必要となります。

真に1/7の乱数を作るなら

これもそのとおりですが、乱数の幅が広ければ相対的に影響は小さくなります。32ビットをそのまま7で割ってしまった場合、確率は0.14285714272～0.14285714295の範囲となって、乱数ルーチンの偏りのほうが問題となるレベルの話です。

なお、線形合同法による乱数の場合、下位ビットほど周期が短いという性質がありますので、余りを取るなどの操作はランダム性を下げることとなります。メルセンヌ・ツイスタなどはどのビットも均等にランダムです。

投稿2019/01/20 09:16

maisumakun

総合スコア146544

GrayWingAliance

2019/01/20 09:38

なるほど… 計算機で一様乱数は完全に再現できない。っていうのが、みそになるわけですか… 確かに有効桁数9桁以上の精度であれば対外、問題なさそうです。少し調べてみたんですが、言語やその中の関数で乱数生成の実装の種類がそれなりにあることに驚きました。実装毎の実測とってみたら面白そうですね。

行動規範の内容に同意します

整数値に変形している。

一定以上大きな範囲のものである。

この場合、絶対に出てこない整数が発生すると思うんですが、

なに言ってるかちょっとわからない。

その生成したい範囲に合わせてバイト数の違う乱数生成関数を用意した方がよいということですかね？

たとえば64bitの乱数を生成しそいつの下位n-byteを取り出せば(8byteまでの)n-byte乱数が作れます。

1バイトの乱数を生成したときにそれを1~7の値に収める際、
7 * ({乱数の値} + 1)/256 (切り上げ)
のようにして、乱数を作りがちですが、数値によって微妙に偏りますよね？

もっと大きな(4byteとか8byteとか)乱数を7で割って余り求めたほうがよくね?

投稿2019/01/20 09:15

episteme

総合スコア16612

GrayWingAliance

2019/01/20 09:21

>> - 整数値に変形している。 >> - 一定以上大きな範囲のものである。 >> この場合、絶対に出てこない整数が発生すると思うんですが、 > なに言ってるかちょっとわからない。例えば、1バイトの乱数を使って、1~500の整数を発生させるとしたら、出てこない整数が半分以上になりますよね？ということを言いたかったです。これは別にnバイトにした場合でも変わらないと思います。 >> 1バイトの乱数を生成したときにそれを1~7の値に収める際、 >> 7 * ({乱数の値} + 1)/256 (切り上げ) >> のようにして、乱数を作りがちですが、数値によって微妙に偏りますよね？ > もっと大きな(4byteとか8byteとか)乱数を7で割って余り求めたほうがよくね? 大きな乱数を使った場合にも必要としている整数の個数が2^n個でない場合は偏りが出るのは変わらないと思います。(それだけ正確な乱数が必要な場面があるかどうかは疑問ではありますが)