Bästa svaret
De flesta slumptalsgenerering behöver inte komplicerade algoritmer, men använder bara några noggrant utvalda siffror och sedan några aritmetiska knep.
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;
}
Om du vill ha en möjligen långsammare men högkvalitativ slumptalsgenerator kan en möjlig generator vara Mersenne Twister. Mersenne-twister är standardgenerator för slumpmässiga tal för Python, Ruby, R, PHP, Matlab, och finns även i C ++. Den använder några ganska coola bitvisa operatorer, vilket framgår av psuedocoden nedan:
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 sitt samtal från 1949 sa Von Neumann: "Den som överväger aritmetiska metoder för att producera slumpmässiga siffror är naturligtvis i ett tillstånd av synd."
Till att börja med kan en dator inte producera riktigt slumpmässiga nummer av sig själv. De "slumpmässiga" siffrorna som en dator producerar är pseudoslumpmässiga nummer . Den producerade sekvensen bestäms av några initialvärden som ges till programmet, dvs. fröet. Algoritmer använder dessa initialtillstånd för programmen eller nyckeln till ett program för att producera slumptal. Verkligen slumpmässiga tal kan produceras genom att på något sätt extrahera nummer från slumpmässigt förekommande naturfenomen, till exempel ett radioaktivt element som avger snabba elektroner. För att få en bättre uppfattning, hänvisa till den här videon (och motstå inte att prenumerera på deras kanal, de har de mest fantastiska videorna på youtube):
Nu kommer den faktiska algoritmen. Den enklaste algoritmen är Mitt-kvadratmetoden . Detta gavs av någon kille som heter broder Edvin (han har inte identifierats ännu) i mitten av 1200-talet. Det tar ett fyrsiffrigt utsäde från miljön och kvadrerar det sedan. Därefter tar det hela talet förutom den första och den sista siffran som slumpvisa siffror. Nu, om behovet av slumpmässiga siffror uppfylls av det första steget, bra och bra. Om inte ändå tar algoritmen de fyra mitten av siffrorna och upprepar hela processen igen så länge användaren behöver nya slumpmässiga siffror.
1. Introduktion till slumpmässighet och slumpmässiga siffror 2. Metod på mitten kvadrat 3. Slumpmässig nummergenerering