números aleatórios distribuídos uniformemente relativamente primos de 2
-
21-08-2019 - |
Pergunta
Um exemplo específico
Eu preciso gerar um número aleatório entre 0 e 2, inclusive. (Ou escolher aleatoriamente entre -1, 0, e 1).
A abordagem ingênua seria fazer algo como rand() mod 3
onde rand()
retorna um inteiro. Esta abordagem não irá gerar números aleatórios estatisticamente, a menos que o limite superior de rand()
não é relativamente primos (e o limite inferior é 0).
Por exemplo, assumindo rand () devolvido 2 bits (de 0 a 3, inclusive), o módulo iria mapear:
0 -> 0
1 -> 1 |
2 -> 2 |
3 -> 0
Esta inclinação em direção a 0 seria, obviamente, muito menos se mais bits seria devolvido, mas independentemente disso, a inclinação permaneceria.
A questão genérica
Existe um modo de gerar um número aleatório distribuído uniformemente entre 0 e n-1, inclusive, em que n é relativamente primos de 2?
Solução
Uma abordagem comum é descartar valores aleatórios acima do último ciclo completo, e apenas pedir um novo número aleatório.
Outras dicas
Pode ajudar escolher o seu rand () superior obrigado a ser k * n, onde k é um inteiro. Desta forma, o resultado será distribuída uniformemente desde que rand () é um bom gerador aleatório.
Se não for possível reduzir o limite superior, você pode escolher k para que k * n é tão perto de rand () limite superior quanto possível e descartar os resultados acima deste número de tentar novamente.
Consulte minha resposta a uma pergunta similar.
Basicamente, use sua RNG e tudo descarte acima N e tente novamente. Para otimização, você pode usar mod, e tudo descarte acima n * andar (MAX / n)
resposta genérica: Você precisa usar mais do que apenas 2 bits do número.
A minha regra de ouro é para gerar valores de ponto flutuante, x , 0,0 <= x <1,0, multiplicar por 3 e truncado. Que você deveria ir valores no intervalo de 0, 1 e 2 que dependem de um número maior de bits.