Risposta migliore
La maggior parte della generazione di numeri casuali non utilizza necessariamente algoritmi complicati, ma utilizza solo alcuni numeri scelti con cura e poi alcuni trucchi aritmetici.
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;
}
Se vuoi un generatore di numeri casuali possibilmente più lento ma di qualità superiore, un possibile generatore può essere il Mersenne Twister. Il Mersenne Twister è il generatore di numeri casuali predefinito per Python, Ruby, R, PHP, Matlab ed è disponibile anche in C ++. Utilizza alcuni interessanti operatori bit per bit, come si può vedere dal codice psued di seguito:
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)
}
}
}
Risposta
Nel suo discorso del 1949, Von Neumann disse: "Chiunque consideri metodi aritmetici per produrre cifre casuali è, ovviamente, in uno stato di peccato."
Per cominciare, un computer non può produrre numeri veramente casuali da solo. I numeri "casuali" prodotti da un computer sono numeri pseudocasuali . La sequenza prodotta è determinata da alcuni valori iniziali dati al programma es. il seme. Gli algoritmi utilizzano questi stati iniziali dei programmi o la chiave data a un programma per produrre numeri casuali. Numeri veramente casuali possono essere prodotti estraendo in qualche modo numeri da fenomeni naturali che si verificano casualmente, ad esempio, un elemento radioattivo che emette elettroni veloci. Per avere unidea migliore, fai riferimento a questo video (e non resistere alliscrizione al loro canale, hanno i video più fantastici su YouTube):
Veniamo ora allalgoritmo effettivo. Lalgoritmo più semplice è Metodo del quadrato medio . Questo è stato fornito da un tizio chiamato Fratello Edvin (non è stato ancora identificato) a metà del XIII secolo. Prende un seme di 4 cifre dallambiente e poi lo piazza. Quindi, prende lintero numero tranne la prima e lultima cifra come sequenza di cifre casuali. Ora, se la necessità di cifre casuali è soddisfatta dal primo passo, bene e bene. In caso contrario, lalgoritmo prende le 4 cifre centrali del numero e ripete lintero processo finché lutente necessita di nuove cifre casuali.
1. Introduzione alla casualità e ai numeri casuali 2. Metodo del quadrato centrale 3. Generazione di numeri casuali