Bedste svar
Generering af tilfældigt tal bruger ikke komplicerede algoritmer, men bruger bare nogle omhyggeligt valgte tal og derefter nogle aritmetiske tricks.
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 vil have en muligvis langsommere, men tilfældig talgenerator af højere kvalitet, kan en mulig generator være Mersenne Twister. Mersenne-twisteren er standard tilfældig talgenerator for Python, Ruby, R, PHP, Matlab og er også tilgængelig i C ++. Det bruger nogle ret seje bitvise operatorer, som det kan ses fra psuedocode 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 tale fra 1949 sagde Von Neumann: "Enhver, der overvejer aritmetiske metoder til at fremstille tilfældige cifre, er naturligvis i en tilstand af synd."
Til at begynde med kan en computer ikke producere virkelige tilfældige tal af sig selv. De "tilfældige" numre, som en computer producerer, er pseudo-tilfældige tal . Den producerede sekvens bestemmes af nogle indledende værdier, der gives til programmet, dvs. frøet. Algoritmer bruger disse indledende tilstande for programmerne eller nøglen til et program til at producere tilfældige tal. Virkelig tilfældige tal kan produceres ved på en eller anden måde at udtrække tal fra tilfældigt forekommende naturlige fænomener, for eksempel et radioaktivt element, der udsender hurtige elektroner. For at få en bedre idé henvises til denne video (og ikke modstå at abonnere på deres kanal, de har de mest fantastiske videoer på youtube):
Nu kommer til den faktiske algoritme. Den nemmeste algoritme er Midt-kvadratisk metode . Dette blev givet af en fyr ved navn broder Edvin (han er endnu ikke identificeret) i midten af det 13. århundrede. Det tager et 4-cifret frø fra miljøet og kvadrerer det derefter. Derefter tager det hele tallet bortset fra det første og det sidste ciffer som den tilfældige cifersekvens. Nu, hvis behovet for tilfældige cifre er opfyldt ved det første trin, godt og godt. Hvis ikke dog, tager algoritmen de midterste 4 cifre i nummeret og gentager hele processen igen, så længe brugeren har brug for nye tilfældige cifre.
1. Introduktion til tilfældighed og tilfældige tal 2. Midt-kvadratisk metode 3. Tilfældig nummergenerering