Najlepsza odpowiedź
Większość generowania liczb losowych nie wymaga koniecznie skomplikowanych algorytmów, ale używa tylko starannie dobranych liczb, a następnie kilka sztuczek arytmetycznych.
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;
}
Jeśli chcesz mieć możliwie wolniejszy, ale wyższej jakości generator liczb losowych, jednym z możliwych generatorów może być Mersenne Twister. Twister Mersenne jest domyślnym generatorem liczb losowych dla Pythona, Ruby, R, PHP, Matlab i jest dostępny również w C ++. Używa całkiem fajnych operatorów bitowych, jak widać na poniższym psuedokodzie:
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)
}
}
}
Odpowiedź
W swoim przemówieniu z 1949 roku Von Neumann powiedział: „Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu”.
Po pierwsze, komputer nie jest w stanie sam wytworzyć prawdziwie losowych liczb. „Losowe” liczby generowane przez komputer to liczby pseudolosowe . Wytworzona sekwencja jest określona przez pewne wartości początkowe nadane programowi, tj. nasiono. Algorytmy wykorzystują te początkowe stany programów lub klucza nadanego programowi do generowania liczb losowych. Prawdziwie losowe liczby można uzyskać, wyodrębniając w jakiś sposób liczby z losowo występujących zjawisk naturalnych, na przykład pierwiastka radioaktywnego emitującego szybko poruszające się elektrony. Aby uzyskać lepszy pomysł, zapoznaj się z tym filmem (i nie opieraj się subskrybowaniu ich kanału, mają najbardziej niesamowite filmy na youtube):
A teraz do właściwego algorytmu. Najłatwiejszym algorytmem jest Metoda środkowego kwadratu . Została podana przez jakiegoś gościa zwanego Bratem Edvinem (jeszcze nie został zidentyfikowany) w połowie XIII wieku. Pobiera 4-cyfrowe ziarno ze środowiska, a następnie podnosi je do kwadratu. Następnie przyjmuje całą liczbę z wyjątkiem pierwszej i ostatniej cyfry jako losowy ciąg cyfr. Teraz, jeśli potrzeba losowych cyfr jest zaspokojona w pierwszym kroku, dobrze i dobrze. Jeśli nie, algorytm bierze środkowe 4 cyfry numeru i powtarza cały proces, dopóki użytkownik potrzebuje nowych losowych cyfr.
1. Wprowadzenie do losowości i liczb losowych 2. Metoda środkowego kwadratu 3. Generowanie liczb losowych