Meilleure réponse
La plupart des générations de nombres aléatoires nutilisent pas nécessairement des algorithmes compliqués, mais utilisent juste des nombres soigneusement choisis, puis quelques astuces arithmétiques.
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;
}
Si vous voulez un générateur de nombres aléatoires probablement plus lent mais de meilleure qualité, un générateur possible peut être le Mersenne Twister. Le twister Mersenne est le générateur de nombres aléatoires par défaut pour Python, Ruby, R, PHP, Matlab et est également disponible en C ++. Il utilise des opérateurs bit à bit assez sympas, comme le montre le psuedocode ci-dessous:
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)
}
}
}
Réponse
Dans son discours de 1949, Von Neumann a déclaré: "Quiconque envisage des méthodes arithmétiques de production de chiffres aléatoires est, bien sûr, dans un état de péché."
Pour commencer, un ordinateur ne peut pas produire de nombres vraiment aléatoires par lui-même. Les nombres "aléatoires" produits par un ordinateur sont des nombres pseudo-aléatoires . La séquence produite est déterminée par certaines valeurs initiales données au programme ie. la graine. Les algorithmes utilisent ces états initiaux des programmes ou la clé donnée à un programme pour produire des nombres aléatoires. Des nombres vraiment aléatoires peuvent être produits en extrayant dune manière ou dune autre des nombres de phénomènes naturels aléatoires, par exemple, un élément radioactif émettant des électrons à rythme rapide. Pour avoir une meilleure idée, reportez-vous à cette vidéo (et ne résistez pas à vous abonner à leur chaîne, ils ont les vidéos les plus impressionnantes sur youtube):
Passons maintenant à lalgorithme actuel. Lalgorithme le plus simple est le Méthode du carré moyen . Cela a été donné par un type appelé frère Edvin (il na pas encore été identifié) au milieu du 13ème siècle. Il prend une graine à 4 chiffres de lenvironnement, puis la met au carré. Ensuite, il prend le nombre entier à lexception du premier et du dernier chiffre comme séquence de chiffres aléatoires. Maintenant, si le besoin des chiffres aléatoires est satisfait par la première étape, très bien. Sinon, lalgorithme prend les 4 chiffres du milieu du nombre et répète le processus entier à nouveau tant que lutilisateur a besoin de nouveaux chiffres aléatoires.
1. Introduction au caractère aléatoire et aux nombres aléatoires 2. Méthode du carré du milieu 3. Génération de nombres aléatoires