4

私は内部の「すべての開発者が知っておくべき」wikiページをまとめています。

私はに関する多くの議論を見ましたrand() % Nが、それをすべて説明する単一のWebページではありませんでした。

たとえば、この問題がC固有およびLinux固有だけであるのか、それともWindows、C ++、にも当てはまるのか、私は興味があります。Java、.Net、Python、Perl。

私がこれの底に到達するのを手伝ってください。また、数字はどれだけランダムではないのでしょうか？ありがとうございました！

4

2 に答える 2

2

参照できるWebページはありませんが、役立つ「封筒の裏」の説明があるかもしれません。単純な乱数ジェネレーターが機能する方法は、次の手順に従うことです。

  1. 最後に生成されnた番号またはシード番号を使用します。
  2. その数に特別な大きな数を掛けます
  3. 別の特別な多数を追加します
  4. それを3番目の特別な大きな数で割り、余りを捨てます
  5. 結果を返す

ここで、ステップ4を除くすべてで何が起こるかを考えると、下位ビットのみが結果の下位ビットを変更できる操作を実行しています。1001と100...00001を加算すると、計算の上限に関係なく、... 02で終了します（基数2について話していましたが、実際にはこれらの数値は基数12です）。同様に、乗算すると、何があっても1で終わります。

トップエンドでも同様の問題があり、10億倍の10億が、数百の枯れた数の寄与を常に支配します。これは、真ん中が良いことが起こる場所であるという事実を示しています。ここでは、高、中、低の多くのビットが相互作用します。

それが除算ステップの目的であり、相互作用がそれほど多くなかった結果の一番下のチャンクを切り取ります。乗算がマシンワードに収まらなくなったときにコンピュータが上位ビットをドロップするため、通常、最上位のチャンクは切り取られません。

結局のところ、カットオフポイントはやや恣意的であり、アルゴリズムを設計した人よりも気が利く可能性がありますが、それでも数ビットを切り落とすことができます。

彼らがどれほど悪いことがあるかというあなたの質問のために、彼らは本当に悪いことがありえます。これを確認する最も簡単な方法は、個々の数値をタプルにグループ化してグラフ化することです。したがって、乱数a, b, c, d, ...グラフ(a,b), (c,d), ...があり、結果を確認した場合。これはスペクトルテストと呼ばれ、ランドはそれを美しく失敗させます。これは私が試すためのリンクを持っていますhttp://random.mat.sbg.ac.at/results/karl/spectraltest/

于 2010-04-23T16:08:54.113 に答える
2

http://en.wikipedia.org/wiki/Linear_congruential_generatorを確認してください。これは、ほとんどの組み込み乱数ジェネレーターで使用されているアルゴリズムである可能性があります。

下にスクロールして、「LCGのさらなる問題は、生成されたシーケンスの下位ビットの周期がはるかに短いことです。」で始まる段落を探してくださいrand() % N。

于 2010-04-04T20:02:18.300 に答える