2

重複の可能性:
rand() はどのように機能しますか? 一定の傾向はありますか？何か良い使い方はありませんか？

私はそれを実装する方法を知っています。ただし、rand が内部でどのように動作するか、および rand 関数の「シード」値を初期化する必要がある理由を理解したいと思います。

別の言い方をすれば、rand 関数はどのようにシード値を使用して乱数を生成するのでしょうか?

4

4 に答える 4

5

より詳細な説明については、ウィキペディアを参照してください。

Linear Congruential Generator (LCG) は、最も古く、最もよく知られている疑似乱数ジェネレーター アルゴリズムの 1 つです。[1] それらの背後にある理論は理解しやすく、簡単に実装でき、高速です。

ジェネレーターは再帰関係によって定義されます。

X_{n+1} = ( a * X_n + c ) mod m

于 2012-09-28T15:09:41.393 に答える
5

正確な実装の詳細は、実装者次第です。しかし、GNU 実装 (glibc) は次のように rand() を実装します: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.15#l361

コメントはそれをかなりよく説明しています。

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
    congruential bit.  Otherwise, we do our fancy trinomial stuff,
    which is the same in all the other cases due to all the global
    variables that have been set up.  The basic operation is to add
    the number at the rear pointer into the one at the front
    pointer.  Then both pointers are advanced to the next location
    cyclically in the table.  The value returned is the sum generated, 
    reduced to 31 bits by throwing away the "least random" low bit.    
    Note: The code takes advantage of the fact that both the front and 
    rear pointers can't wrap on the same call by not testing the rear  
    pointer if the front one has wrapped.  Returns a 31-bit random number. */

なぜ常にシード値が必要なのかという質問について: コンピュータ サイエンスには真の乱数はありません。コンピューターは (計算理論では) 完全に決定論的な機械です。彼らは、結果が偶然である操作を実行することはできません。

ランダムに見える数のストリームを生成する疑似乱数ジェネレーターしかありませんが、それらは依然として決定論的な計算の結果です。そのため、シード値が必要です。各シードは、異なる数列になります。同じシードを使用すると、同じ一連の疑似乱数が得られます。

同じシードを取得すると、RNG が常に同じシーケンスを返すという動作を悪用できます。たとえば、古典的な宇宙シミュレーションEliteは、数百の惑星を含む巨大な宇宙を単一の整数に格納することができました。どうやってそれをしたのですか？宇宙全体がランダムに生成されました。ユニバースを再作成するために必要なすべてのデータはシード値であり、常にまったく同じユニバースが生成されました。

于 2012-09-28T15:11:02.743 に答える
3

ほとんどのrand実装は、基本的な数学を使用してミキシングを実行するLCGです。ほとんどの PRNG と同様に、固定された予測可能な数学関数を使用して作成された決定論的性質 (これは良い面と悪い面の両方であり、その使用目的によって異なります) を部分的に取り除くために、ランダム化されたシードが必要です。

于 2012-09-28T15:11:20.313 に答える
2

rand()実際に実装するために使用されるアルゴリズムに興味がある場合は、C の rand() に使用される一般的なアルゴリズムは何ですか? 興味があるかもしれません。glibc の実装と、他のアルゴリズムを説明する記事へのリンクがいくつかあります。

なぜシードを設定する必要があるのか​​という問題については、シードは、乱数ジェネレーターが毎回同じ数のシーケンスを生成するのを防ぐものです。真の乱数ジェネレーターは存在しないため、and を 5 回呼び出すsrand(constant)と、返さrand()れる 5 つの「乱数」は常に同じになります。ただし、使用されるたびに異なる値をシードする場合rand()(デフォルトは、Unix エポックからの秒数だと思います)、この問題は発生しません。

于 2012-09-28T15:12:21.030 に答える