Paras vastaus
Suurin osa satunnaislukujen generoinnista ei välttämättä käytä monimutkaisia algoritmeja, vaan käyttää vain joitain huolella valittuja numeroita ja sitten joitain aritmeettisia temppuja.
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;
}
Jos haluat hitaamman mutta laadukkaamman satunnaislukugeneraattorin, yksi mahdollinen generaattori voi olla Mersenne Twister. Mersennen twister on oletusarvoinen satunnaislukugeneraattori Pythonille, Ruby: lle, R: lle, PHP: lle, Matlabille, ja se on saatavana myös C ++: ssa. Se käyttää melko hienoja bittioperaattoreita, kuten alla olevasta psuedocode-koodista näkyy:
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)
}
}
}
vastaus
Vuonna 1949 pitämässään puheenvuorossa Von Neumann sanoi: "Jokainen, joka harkitsee aritmeettisia menetelmiä satunnaislukujen tuottamiseksi, on tietysti synnissä."
Aluksi tietokone ei voi tuottaa itse satunnaisia lukuja. Tietokoneen tuottamat "satunnaiset" luvut ovat näennäissatunnaisia lukuja . Tuotettu sekvenssi määräytyy joidenkin ohjelmalle annettujen alkuarvojen mukaan. siemen. Algoritmit hyödyntävät näitä ohjelmien alkutiloja tai ohjelmalle annettua avainta satunnaislukujen tuottamiseen. Todella satunnaiset luvut voidaan tuottaa erottamalla jotenkin numerot satunnaisesti esiintyvistä luonnonilmiöistä, esimerkiksi radioaktiivisesta elementistä, joka säteilee nopeatempoisia elektroneja. Saadaksesi paremman kuvan, katso tämä video (ja älä vastusta tilatessasi heidän kanavaaan, heillä on mahtavimmat videot YouTubessa):
Nyt tulossa varsinaiseen algoritmiin. Helpoin algoritmi on Keskineliön menetelmä . Tämän antoi eräs kaveri nimeltä Veli Edvin (häntä ei ole vielä tunnistettu) 1300-luvun puolivälissä. Se ottaa nelinumeroisen siemenen ympäristöstä ja neliöi sen. Sitten se ottaa kokonaisluvun, lukuun ottamatta ensimmäistä ja viimeistä numeroa, satunnaismerkkijonona. Jos ensimmäinen vaihe tyydyttää satunnaislukujen tarpeen, on hyvä. Jos ei, algoritmi ottaa numeron keskimmäiset 4 numeroa ja toistaa koko prosessin uudelleen niin kauan kuin käyttäjä tarvitsee uusia satunnaislukuja.
1. Satunnaisuuden ja satunnaislukujen esittely 2. Keskineliön menetelmä 3. Satunnaislukujen generointi