Beste svaret
Mest tilfeldige tallgenerering bruker ikke kompliserte algoritmer, men bruker bare noen nøye utvalgte tall og deretter noen aritmetiske triks.
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;
}
Hvis du ønsker en mulig tregere men tilfeldig tallgenerator av høyere kvalitet, kan en mulig generator være Mersenne Twister. Mersenne twister er standard tilfeldig tallgenerator for Python, Ruby, R, PHP, Matlab, og er også tilgjengelig i C ++. Den bruker noen ganske kule bitvise operatører som kan sees fra psuedokoden nedenfor:
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)
}
}
}
Svar
I sin 1949-tale sa Von Neumann: "Enhver som vurderer aritmetiske metoder for å produsere tilfeldige sifre, er selvfølgelig i en tilstand av synd."
Til å begynne med kan en datamaskin ikke produsere helt tilfeldige tall av seg selv. De "tilfeldige" tallene som en datamaskin produserer er pseudo-tilfeldige tall . Sekvensen som produseres bestemmes av noen innledende verdier gitt til programmet, dvs. frøet. Algoritmer bruker disse starttilstandene til programmene eller nøkkelen som gis til et program for å produsere tilfeldige tall. Virkelig tilfeldige tall kan produseres ved på en eller annen måte å trekke ut tall fra tilfeldig forekommende naturfenomener, for eksempel et radioaktivt element som sender ut fartsfylte elektroner. For å få en bedre ide, se denne videoen (og ikke motstå å abonnere på kanalen deres, de har de mest fantastiske videoene på youtube):
Nå, kommer til den faktiske algoritmen. Den enkleste algoritmen er Midt-kvadratisk metode . Dette ble gitt av en fyr som heter bror Edvin (han har ikke blitt identifisert ennå) på midten av 1200-tallet. Det tar et 4-sifret frø fra miljøet, og kvadrerer det deretter. Deretter tar det hele tallet bortsett fra det første og siste sifferet som den tilfeldige sifersekvensen. Nå, hvis behovet for tilfeldige sifre blir dekket av det første trinnet, vel og bra. Hvis ikke, tar algoritmen de midterste 4 sifrene i tallet og gjentar hele prosessen igjen så lenge brukeren trenger nye tilfeldige sifre.
1. Introduksjon til tilfeldighet og tilfeldige tall 2. Midt-kvadratmetode 3. Tilfeldig nummergenerering