La mejor respuesta
La mayoría de la generación de números aleatorios no necesariamente usa algoritmos complicados, sino que solo usa algunos números cuidadosamente seleccionados y luego algunos trucos aritméticos.
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 desea un generador de números aleatorios posiblemente más lento pero de mayor calidad, un posible generador puede ser el Mersenne Twister. El tornado de Mersenne es el generador de números aleatorios predeterminado para Python, Ruby, R, PHP, Matlab, y también está disponible en C ++. Utiliza algunos operadores bit a bit bastante interesantes como se puede ver en el psuedocode a continuación:
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)
}
}
}
Respuesta
En su charla de 1949, Von Neumann dijo: "Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado".
Para empezar, una computadora no puede producir números verdaderamente aleatorios por sí misma. Los números "aleatorios" que produce una computadora son números pseudoaleatorios . La secuencia producida está determinada por algunos valores iniciales dados al programa, es decir. la semilla. Los algoritmos utilizan estos estados iniciales de los programas o la clave dada a un programa para producir números aleatorios. Los números verdaderamente aleatorios se pueden producir extrayendo de alguna manera números de fenómenos naturales que ocurren al azar, por ejemplo, un elemento radiactivo que emite electrones de ritmo rápido. Para tener una mejor idea, consulte este video (y no se resista a suscribirse a su canal, tienen los videos más increíbles en youtube):
Ahora, llegando al algoritmo real. El algoritmo más sencillo es Método del cuadrado medio . Se lo dio un tipo llamado Hermano Edvin (aún no ha sido identificado) a mediados del siglo XIII. Toma una semilla de 4 dígitos del medio ambiente y luego la cuadra. Luego, toma el número entero excepto el primer y el último dígito como secuencia de dígitos aleatorios. Ahora bien, si el primer paso satisface la necesidad de los dígitos aleatorios, está bien. Si no es así, el algoritmo toma los 4 dígitos centrales del número y repite todo el proceso de nuevo siempre que el usuario necesite nuevos dígitos aleatorios.
1. Introducción a la aleatoriedad y los números aleatorios 2. Método del cuadrado medio 3. Generación de números aleatorios