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