Beste Antwort
Die meisten Zufallszahlengenerierungen verwenden nicht unbedingt komplizierte Algorithmen, sondern nur einige sorgfältig ausgewählte Zahlen und dann Einige arithmetische 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;
}
Wenn Sie einen möglicherweise langsameren, aber qualitativ hochwertigeren Zufallszahlengenerator wünschen, kann der Mersenne Twister ein möglicher Generator sein. Der Mersenne-Twister ist der Standard-Zufallszahlengenerator für Python, Ruby, R, PHP, Matlab und auch in C ++ verfügbar. Es werden einige ziemlich coole bitweise Operatoren verwendet, wie aus dem folgenden Pseudocode ersichtlich ist:
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)
}
}
}
Antwort
In seinem Vortrag von 1949 sagte Von Neumann: "Jeder, der arithmetische Methoden zur Erzeugung zufälliger Ziffern in Betracht zieht, befindet sich natürlich in einem Zustand der Sünde." / p>
Zunächst einmal kann ein Computer selbst keine echten Zufallszahlen erzeugen. Die "Zufallszahlen", die ein Computer erzeugt, sind Pseudozufallszahlen . Die erzeugte Sequenz wird durch einige Anfangswerte bestimmt, die dem Programm gegeben werden, d. H. der Samen. Algorithmen verwenden diese Anfangszustände der Programme oder den einem Programm gegebenen Schlüssel, um Zufallszahlen zu erzeugen. Wirklich zufällige Zahlen können erzeugt werden, indem auf irgendeine Weise Zahlen aus zufällig auftretenden natürlichen Phänomenen extrahiert werden, beispielsweise einem radioaktiven Element, das schnelllebige Elektronen emittiert. Um eine bessere Vorstellung zu bekommen, lesen Sie dieses Video (und widersetzen Sie sich nicht, ihren Kanal zu abonnieren, sie haben die großartigsten Videos auf Youtube):
Kommen wir nun zum eigentlichen Algorithmus. Der einfachste Algorithmus ist der Mittelquadrat-Methode . Diese wurde Mitte des 13. Jahrhunderts von einem Mann namens Bruder Edvin (er wurde noch nicht identifiziert) angegeben. Es nimmt einen 4-stelligen Samen aus der Umgebung und quadriert ihn dann. Dann wird die ganze Zahl mit Ausnahme der ersten und der letzten Ziffer als zufällige Ziffernfolge verwendet. Nun, wenn die Notwendigkeit für die zufälligen Ziffern durch den ersten Schritt erfüllt wird, gut und gut. Wenn nicht, nimmt der Algorithmus die mittleren 4 Ziffern der Zahl und wiederholt den gesamten Vorgang erneut, solange der Benutzer neue zufällige Ziffern benötigt.
1. Einführung in Zufälligkeit und Zufallszahlen 2. Mittelquadratmethode 3. Zufallszahlengenerierung