Mi az algoritmus a véletlenszám-generáláshoz?


Legjobb válasz

A legtöbb véletlenszerű számgenerálás nem feltétlenül használ bonyolult algoritmusokat, hanem csak néhány gondosan megválasztott számot használ, majd néhány számtani trükk.

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() {

iv 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;

}

Ha esetleg lassabb, de jobb minőségű véletlenszám-generátort szeretne, akkor az egyik lehetséges generátor lehet a Mersenne Twister. A Mersenne twister az alapértelmezett véletlenszám-generátor Python, Ruby, R, PHP, Matlab számára, és C ++ nyelven is elérhető. Elég hűvös bitenkénti operátorokat használ, amint az az alábbi psuedocode-ból is kiderül:

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)

}

}

}

Válasz

1949-es beszédében Von Neumann azt mondta: "Aki véletlenszerű számjegyek előállításának aritmetikai módszereit fontolgatja, természetesen bűn állapotában van."

Először is, a számítógép önmagában nem képes valóban véletlenszerű számokat előállítani. A számítógép által előállított "véletlenszerű" számok ál-véletlenszerű számok . Az előállított szekvenciát a programnak adott kezdeti értékek határozzák meg, pl. a mag. Az algoritmusok ezeket a kezdeti állapotokat vagy a programnak adott kulcsot használják véletlenszámok előállítására. Valóban véletlenszerű számokat lehet előállítani úgy, hogy valamilyen módon kivonjuk a véletlenszerűen előforduló természeti jelenségekből a számokat, például egy gyors ütemű elektronokat kibocsátó radioaktív elem. Annak érdekében, hogy jobb ötletet kapjon, olvassa el ezt a videót (és ne álljon ellen a csatornájuk feliratkozásakor, a YouTube-on a legfélelmetesebb videók vannak):

Most a tényleges algoritmusra térünk. A legegyszerűbb algoritmus a Középnégyzet módszer . Ezt egy Edvin testvér nevű srác adta (még nem ismerték meg) a 13. század közepén. 4 számjegyű magot vesz ki a környezetből, majd négyzetre emeli. Ezután az egész számot veszi el, az első és az utolsó számjegy kivételével, mint véletlenszerű számjegy. Most, ha az első lépés kielégíti a véletlenszerű számjegyek szükségességét, akkor jó és jó. Ha nem, akkor az algoritmus felveszi a szám középső 4 számjegyét, és ismételje meg az egész folyamatot, amíg a felhasználónak új véletlenszerű számjegyekre van szüksége.

1. Bevezetés a véletlenszerűségbe és a véletlenszerű számokba 2. Középnégyzet módszer 3. Véletlenszám-generálás

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük