números aleatórios distribuídos uniformemente relativamente primos de 2

Question

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?

Answer 1

Uma abordagem comum é descartar valores aleatórios acima do último ciclo completo, e apenas pedir um novo número aleatório.

Answer 2

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.

Answer 3

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)

Answer 4

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.