Jaký je algoritmus použitý pro generování náhodných čísel?


Nejlepší odpověď

Většina generování náhodných čísel nevyžaduje složité algoritmy, ale používá pouze pečlivě zvolená čísla a poté některé aritmetické triky.

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;

}

Pokud chcete pomalejší, ale kvalitnější generátor náhodných čísel, jedním z možných generátorů může být Mersenne Twister. Mersenne twister je výchozí generátor náhodných čísel pro Python, Ruby, R, PHP, Matlab a je k dispozici také v C ++. Využívá některé docela skvělé bitové operátory, jak je vidět z níže uvedeného psuedocode:

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)

}

}

}

Odpověď

Ve svém proslovu z roku 1949 Von Neumann řekl: „Každý, kdo uvažuje o aritmetických metodách vytváření náhodných číslic, je samozřejmě ve stavu hříchu.“

Za prvé, počítač sám o sobě nemůže vytvořit skutečně náhodná čísla. „Náhodná“ čísla, která počítač vytváří, jsou pseudonáhodná čísla . Vyrobená sekvence je určena některými počátečními hodnotami danými programu, tj. semínko. Algoritmy využívají tyto počáteční stavy programů nebo klíče daného programu k vytváření náhodných čísel. Skutečně náhodná čísla lze vyrobit nějakým způsobem extrahováním čísel z náhodně se vyskytujících přírodních jevů, například radioaktivního prvku emitujícího rychle se rozvíjející elektrony. Chcete-li získat lepší představu, podívejte se na toto video (a neodporujte při přihlášení k odběru jejich kanálu, mají ta nejúžasnější videa na youtube):

Nyní přicházíme ke skutečnému algoritmu. Nejjednodušší algoritmus je Metoda středního čtverce . Tuto metodu zadal nějaký chlapík jménem bratr Edvin (dosud nebyl identifikován) v polovině 13. století. Trvá čtyřmístné semeno z prostředí a poté jej umocňuje. Poté vezme celé číslo kromě první a poslední číslice jako sekvenci náhodných číslic. Nyní, je-li potřeba náhodných číslic splněna prvním krokem, dobře a dobře. Pokud tomu tak není, algoritmus vezme prostřední 4 číslice čísla a celý proces opakuje znovu, dokud uživatel potřebuje nové náhodné číslice.

1. Úvod do náhodnosti a náhodných čísel 2. Metoda středního čtverce 3. Generování náhodných čísel

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *