乱数生成に使用されるアルゴリズムは何ですか?


ベストアンサー

ほとんどの乱数生成では、複雑なアルゴリズムを使用する必要はありませんが、慎重に選択した数を使用してから使用します。いくつかの算術トリック。

C:

static unsigned int next = 1;

int rand\_r(unsigned int *seed){

*seed = *seed * 1103515245 + 12345;

return (*seed \% ((unsigned int)RAND\_MAX + 1));

}

int rand(void){

return (rand\_r(&next));

}

void srand(unsigned int seed) {

next = seed;

}

Java:

private final AtomicLong seed;

private static final long multiplier = 0x5DEECE66DL;

private static final long addend = 0xBL;

private static final long mask = (1L << 48) - 1;

public Random() {

this(seedUniquifier() ^ System.nanoTime());

}

private static long seedUniquifier() {

for (;;) {

long current = seedUniquifier.get();

long next = current * 181783497276652981L;

if (seedUniquifier.compareAndSet(current, next))

return next;

}

}

private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);

public Random(long seed) {

this.seed = new AtomicLong(initialScramble(seed));

}

private static long initialScramble(long seed) {

return (seed ^ multiplier) & mask;

}

おそらく低速で高品質のランダム数ジェネレーターが必要な場合は、MersenneTwisterを使用できます。メルセンヌツイスターは、Python、Ruby、R、PHP、Matlabのデフォルトの乱数ジェネレーターであり、C ++でも使用できます。以下の擬似コードからわかるように、かなりクールなビット演算子を使用しています。

int[0..623] MT

int index = 0

function initialize\_generator(int seed) {

i := 0

MT[0] := seed

for i from 1 to 623 {

MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i)

}

}

function extract\_number() {

if index == 0 {

generate\_numbers()

}

int y := MT[index]

y := y xor (right shift by 11 bits(y))

y := y xor (left shift by 7 bits(y) and (2636928640))

y := y xor (left shift by 15 bits(y) and (4022730752))

y := y xor (right shift by 18 bits(y))

index := (index + 1) mod 624 return y

}

function generate\_numbers() {

for i from 0 to 623 {

int y := (MT[i] & 0x80000000) + (MT[(i+1) mod 624] & 0x7fffffff)

MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))

if (y mod 2) != 0 {

MT[i] := MT[i] xor (2567483615)

}

}

}

回答

1949年の講演で、フォンノイマンは、「乱数を生成する算術的方法を検討する人は、もちろん、罪の状態にあります」と述べています。

そもそも、コンピューターはそれ自体では真に乱数を生成することはできません。コンピューターが生成する「乱数」は、疑似乱数です。生成されるシーケンスは、プログラムに与えられたいくつかの初期値によって決定されます。種子。アルゴリズムは、プログラムのこれらの初期状態またはプログラムに与えられたキーを利用して、乱数を生成します。真の乱数は、ランダムに発生する自然現象、たとえば、ペースの速い電子を放出する放射性元素から何らかの方法で数値を抽出することによって生成できます。より良いアイデアを得るには、このビデオを参照してください(そして、彼らのチャンネルを購読することに抵抗しないでください、彼らはyoutubeで最も素晴らしいビデオを持っています):

次に、実際のアルゴリズムについて説明します。最も簡単なアルゴリズムはミドルスクエア法。これは、13世紀半ばにエドビン兄弟(彼はまだ特定されていません)と呼ばれる男によって与えられました。環境から4桁のシードを取得し、それを2乗します。次に、最初と最後の桁を除く整数をランダムな桁シーケンスとして使用します。さて、ランダムな数字の必要性が最初のステップで満たされれば、うまくいきます。そうでない場合でも、アルゴリズムは数字の中央の4桁を取り、ユーザーが新しいランダムな数字を必要とする限り、プロセス全体を繰り返します。

1。 ランダム性と乱数の概要 2. 中二乗法 3. 乱数の生成

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です