Melhor resposta
A maioria da geração de número aleatório não usa necessariamente algoritmos complicados, mas apenas usa alguns números cuidadosamente escolhidos e então alguns truques 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() {
}
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;
}
Se você quiser um gerador de números aleatórios possivelmente mais lento, mas de qualidade superior, um gerador possível pode ser o Mersenne Twister. O Mersenne twister é o gerador de número aleatório padrão para Python, Ruby, R, PHP, Matlab e também está disponível em C ++. Ele usa alguns operadores bit a bit muito legais, como pode ser visto no psuedocode abaixo:
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)
}
}
}
Resposta
Em sua palestra de 1949, Von Neumann disse: "Qualquer pessoa que considere métodos aritméticos de produção de dígitos aleatórios está, é claro, em estado de pecado."
Para começar, um computador não pode produzir números verdadeiramente aleatórios sozinho. Os números "aleatórios" que um computador produz são números pseudo-aleatórios . A seqüência produzida é determinada por alguns valores iniciais dados ao programa ie. a semente. Os algoritmos utilizam esses estados iniciais dos programas ou a chave dada a um programa para produzir números aleatórios. Números verdadeiramente aleatórios podem ser produzidos extraindo-se de alguma forma números de fenômenos naturais que ocorrem aleatoriamente, por exemplo, um elemento radioativo emitindo elétrons em ritmo acelerado. Para ter uma ideia melhor, consulte este vídeo (e não resista em se inscrever no canal deles, eles têm os vídeos mais incríveis no youtube):
Agora, chegando ao algoritmo real. O algoritmo mais fácil é o Método do quadrado do meio . Foi fornecido por um cara chamado irmão Edvin (ele ainda não foi identificado) em meados do século XIII. Ele pega uma semente de 4 dígitos do meio ambiente e a coloca em quadratura. Em seguida, leva o número inteiro, exceto o primeiro e o último dígito como a sequência de dígitos aleatórios. Agora, se a necessidade dos dígitos aleatórios for atendida na primeira etapa, tudo bem. Caso contrário, o algoritmo pega os 4 dígitos do meio do número e repete todo o processo novamente, desde que o usuário precise de novos dígitos aleatórios.
1. Introdução à aleatoriedade e aos números aleatórios 2. Método do quadrado médio 3. Geração de número aleatório