Beste antwoord
De meeste genereren van willekeurige getallen gebruikt niet per se ingewikkelde algoritmen, maar gebruikt alleen een aantal zorgvuldig gekozen getallen en enkele rekenkundige trucs.
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;
}
Als je een mogelijk langzamere maar kwalitatief betere generator voor willekeurige getallen wilt, kan een mogelijke generator de Mersenne Twister zijn. De Mersenne twister is de standaard generator voor willekeurige getallen voor Python, Ruby, R, PHP, Matlab, en is ook beschikbaar in C ++. Het gebruikt een aantal behoorlijk coole bitsgewijze operatoren zoals te zien is in de onderstaande 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)
}
}
}
Answer
In zijn toespraak uit 1949 zei Von Neumann: "Iedereen die rekenkundige methoden overweegt om willekeurige cijfers te produceren, verkeert natuurlijk in een staat van zonde."
Om te beginnen kan een computer zelf geen echt willekeurige getallen produceren. De "willekeurige" getallen die een computer produceert, zijn pseudo-willekeurige getallen . De geproduceerde volgorde wordt bepaald door enkele beginwaarden die aan het programma zijn gegeven, dwz. het zaad. Algoritmen gebruiken deze begintoestanden van de programmas of de sleutel die aan een programma wordt gegeven om willekeurige getallen te produceren. Echt willekeurige getallen kunnen worden geproduceerd door op de een of andere manier getallen te extraheren uit willekeurig voorkomende natuurlijke fenomenen, bijvoorbeeld een radioactief element dat snelle elektronen uitzendt. Raadpleeg deze video om een beter idee te krijgen (en abonneer je niet op hun kanaal, ze hebben de meest geweldige videos op YouTube):
Nu komt we bij het eigenlijke algoritme. Het gemakkelijkste algoritme is het Middle-square-methode Deze werd gegeven door een of andere man die broeder Edvin heette (hij is nog niet geïdentificeerd) in het midden van de 13e eeuw. Het neemt een 4-cijferig zaad uit de omgeving en maakt het vervolgens vierkant. Vervolgens wordt het hele getal gebruikt, behalve het eerste en het laatste cijfer als de willekeurige cijferreeks. Nu, als de behoefte aan de willekeurige cijfers wordt vervuld door de eerste stap, goed en wel. Als dit niet het geval is, neemt het algoritme de middelste 4 cijfers van het nummer en herhaalt het hele proces zo lang als de gebruiker nieuwe willekeurige cijfers nodig heeft.
1. Inleiding tot willekeur en willekeurige getallen 2. Middle-square-methode 3. Genereren van willekeurige getallen