5

重複の可能性:
乱数ジェネレーターはどのように機能しますか?

C/C++ での乱数ジェネレーターの内部実装を探しています。基本的には、rand() が呼び出されたときに正確に何が起こるかを知りたいと思っています。結局のところ、マシンは一連の明確な指示に従いますが、どうしてランダムになるのでしょうか!
編集: C/C++ で実装する方法を知りたいです。

4

3 に答える 3

12

それらは疑似乱数ジェネレーターであり、真にランダムなジェネレーターではありません。これは、「乱数」が関係するバグをより簡単に再現できるため、多くの場合良いことです。

Linux での読み取りなどの乱数ジェネレーターを取得できます/dev/randomが、C ライブラリに同梱されている通常の乱数ジェネレーターは通常そうではありません。

最も単純なものは、次のような線形合同ジェネレーターです。

n(x+1) = n(x) * A + C modulo M

A、Cおよびの適切に選択された値を使用しMます。

ウィキペディアの LCG に関するページには、さまざまな実装で使用されるサンプル値がいくつか示されています。たとえば、glibcそこにリストされているものにはa = 1103515245, c = 12345, m = 2^31次のような単純なものがあります。

static unsigned int seed = 1;
void srand (int newseed) {
    seed = (unsigned)newseed & 0x7fffffffU;
}
int rand (void) {
    seed = (seed * 1103515245U + 12345U) & 0x7fffffffU;
    return (int)seed;
}

余談: glibc の実装にはまだこのジェネレーター (タイプ 0 ジェネレーターと呼ばれる) が含まれていますが、(おそらく) 優れている、より洗練された 3 項式ジェネレーターも含まれています。

より長いサイクル時間 (繰り返しを開始するまでの時間) を持つ、より複雑なもの (メルセンヌ ツイスターなど) もあります。

真にランダムなジェネレーターは、真にランダムな入力ソースを使用する必要があります。これが、/dev/randomブロック (「エントロピーの待機」) がブロックされない場合がある理由/dev/urandomです。

「本当に」ランダムなソースは、キーストローク間のタイミング、ユーザーが入力したデータ、ネットワーク パケットの内容、ディスク I/O パターン、ICMP 応答がネットワークを介して戻ってくるまでの時間、その他あらゆる種類の驚異的な影響を受ける可能性があります。非決定的なもの。

暗号化に深く興味がない限り、通常の乱数ジェネレーターで問題ありません。

于 2012-08-14T06:10:15.593 に答える
1

コメントで述べたように、RAM マシンのランダム ジェネレーターは真のランダムではなく、疑似ランダムです。

java.util.RandomのJavaソースをいつでも見ることができます。

具体的には、メソッドnext(int bits)が探しているものです。

protected int next(int bits) {
      long oldseed, nextseed;
      AtomicLong seed = this.seed;
      do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
      } while (!seed.compareAndSet(oldseed, nextseed));
      return (int)(nextseed >>> (48 - bits));
}

(*) この回答は、Java としてタグ付けされ、特に C++ を求めていない以前のバージョンの質問に適合します。

于 2012-08-14T06:14:38.217 に答える
1

以下は単純な疑似乱数アルゴリズムです。

//generates pseudo random series of numbers 0...RAND_MAX - 1 with uniform distribution, starting with 0

static const int A = 15342; // any number in (0, RAND_MAX)
static const int C = 45194; // any number in [0, RAND_MAX)
static const RAND_MAX = 100000;

int rand()
{
    static int prev = 0; //seed. any number in [0, RAND_MAX)
    prev = ( prev * A + C ) % RAND_MAX;
    return prev;
}

ここで詳細を読むことができます: http://en.wikipedia.org/wiki/Linear_congruential_generator

于 2012-08-14T06:16:39.573 に答える