Por que as pessoas dizem que existe um viés de módulo ao usar um gerador de números aleatórios?

277

Já vi essa pergunta muito, mas nunca vi uma resposta concreta. Então, eu vou postar um aqui que, espero, ajudará as pessoas a entender por que exatamente existe um "viés de módulo" ao usar um gerador de números aleatórios, como rand()em C ++.

user1413793
fonte

Respostas:

394

O mesmo rand()ocorre com um gerador de números pseudo-aleatórios que escolhe um número natural entre 0 e RAND_MAX, que é uma constante definida em cstdlib(consulte este artigo para uma visão geral sobre rand()).

Agora, o que acontece se você deseja gerar um número aleatório entre digamos 0 e 2? Por uma questão de explicação, digamos que RAND_MAXseja 10 e decido gerar um número aleatório entre 0 e 2 ligando rand()%3. No entanto, rand()%3não produz números entre 0 e 2 com igual probabilidade!

Quando rand()retorna 0, 3, 6 ou 9 rand()%3 == 0 ,. Portanto, P (0) = 4/11

Quando rand()retorna 1, 4, 7 ou 10 rand()%3 == 1 ,. Portanto, P (1) = 4/11

Quando rand()retorna 2, 5 ou 8 rand()%3 == 2 ,. Portanto, P (2) = 3/11

Isso não gera os números entre 0 e 2 com igual probabilidade. Obviamente, para faixas pequenas, esse pode não ser o maior problema, mas para uma faixa maior isso pode distorcer a distribuição, influenciando os números menores.

Então, quando rand()%nretorna um intervalo de números de 0 a n-1 com igual probabilidade? Quando RAND_MAX%n == n - 1. Nesse caso, junto com nossa suposição anterior rand(), retorna um número entre 0 e RAND_MAXcom igual probabilidade, as classes de módulo de n também seriam igualmente distribuídas.

Então, como resolvemos esse problema? Uma maneira simples é continuar gerando números aleatórios até você obter um número no intervalo desejado:

int x; 
do {
    x = rand();
} while (x >= n);

mas isso é ineficiente para valores baixos de n, pois você só tem uma n/RAND_MAXchance de obter um valor no seu intervalo e, portanto, precisará realizar RAND_MAX/nchamadas rand()em média.

Uma abordagem fórmula mais eficaz seria a de levar algum grande gama com um divisível comprimento por n, como RAND_MAX - RAND_MAX % n, manter a geração de números aleatórios até que você obtenha um que mentiras na faixa, e em seguida, tomar o módulo:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

Para valores pequenos de n, isso raramente exigirá mais de uma chamada rand().


Trabalhos citados e leituras adicionais:


user1413793
fonte
6
Outra maneira de pensar sobre RAND_MAX%n == n - 1_ _ é (RAND_MAX + 1) % n == 0. Ao ler o código, costumo entender % something == 0como "igualmente divisível" mais facilmente do que outras maneiras de calculá-lo. Obviamente, se o seu stdlib em C ++ tiver RAND_MAXo mesmo valor que INT_MAX, (RAND_MAX + 1)certamente não funcionaria; portanto, o cálculo de Mark continua sendo a implementação mais segura.
Slipp D. Thompson
resposta muito boa!
Sayali Sonawane
Eu posso estar detalhando, mas se o objetivo é reduzir os bits desperdiçados, podemos melhorar isso levemente para a condição de borda em que RAND_MAX (RM) é apenas 1 a menos do que ser igualmente divisível por N. Nesse cenário, nenhum bit precisa ser desperdiçado por fazendo X> = (RM - RM% N)) que é de pouco valor para valores pequenos de N, mas se torna de maior valor para valores grandes de N. Como mencionado por Slipp D. Thompson, existe uma solução que funcionará apenas quando INT_MAX (IM)> RAND_MAX, mas é interrompido quando são iguais. No entanto, há uma solução simples para isso, podemos alterar o cálculo X> = (RM - RM% N) como segue:
Ben Personick
X> = RM - (((RM% N) + 1)% N))
Ben Personick 28/10
Postei uma resposta adicional explicando o problema em detalhes e fornecendo a solução de código de exemplo.
quer
36

Continue selecionando uma opção aleatória é uma boa maneira de remover o viés.

Atualizar

Poderíamos tornar o código rápido se procurarmos um x no intervalo divisível por n.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

O loop acima deve ser muito rápido, digamos 1 iteração, em média.

Nick Dandoulakis
fonte
2
Yuck :-P, a conversão para um duplo e a multiplicação por MAX_UPPER_LIMIT / RAND_MAX é muito mais limpa e apresenta um desempenho melhor.
boycy
22
@ boycy: você perdeu o ponto. Se o número de valores que rand()pode retornar não for múltiplo de n, faça o que fizer, inevitavelmente você receberá um 'viés de módulo', a menos que descartar alguns desses valores. user1413793 explica isso muito bem (embora a solução proposta nessa resposta seja realmente ruim).
TonyK
4
@ TonyK minhas desculpas, eu perdi o ponto. Não pensou muito e pensou que o viés se aplicaria apenas a métodos usando uma operação de módulo explícita. Graças para a fixação me :-)
boycy
A precedência do operador faz o RAND_MAX+1 - (RAND_MAX+1) % ntrabalho corretamente, mas ainda acho que deve ser escrito quanto RAND_MAX+1 - ((RAND_MAX+1) % n)à clareza.
Linus Arver
4
Isso não funcionará se RAND_MAX == INT_MAX (como acontece na maioria dos sistemas) . Veja meu segundo comentário para @ user1413793 acima.
BlueRaja - Danny Pflughoeft
19

@ user1413793 está correto sobre o problema. Não vou discutir isso mais além, exceto para dizer um ponto: sim, para valores pequenos ne grandes RAND_MAX, o viés do módulo pode ser muito pequeno. Mas usar um padrão de indução de viés significa que você deve considerar o viés toda vez que calcular um número aleatório e escolher padrões diferentes para casos diferentes. E se você fizer a escolha errada, os bugs introduzidos são sutis e quase impossíveis de realizar testes de unidade. Comparado a apenas usar a ferramenta adequada (como arc4random_uniform), isso é trabalho extra, não menos trabalho. Fazer mais trabalho e obter uma solução pior é uma engenharia terrível, especialmente quando é sempre bom fazer isso na maioria das plataformas.

Infelizmente, as implementações da solução são todas incorretas ou menos eficientes do que deveriam. (Cada solução tem vários comentários que explicam os problemas, mas nenhuma das soluções foi corrigida para resolvê-los.) Isso provavelmente confunde quem procura respostas, por isso estou fornecendo uma implementação em bom estado aqui.

Novamente, a melhor solução é apenas usar arc4random_uniformnas plataformas que a fornecem, ou uma solução à distância semelhante para sua plataforma (como Random.nextIntem Java). Ele fará a coisa certa sem nenhum custo de código para você. Esta é quase sempre a decisão correta a ser feita.

Se você não tiver arc4random_uniform, poderá usar o poder do código-fonte aberto para ver exatamente como ele é implementado em um RNG de maior alcance ( ar4randomnesse caso, mas uma abordagem semelhante também pode funcionar em cima de outros RNGs).

Aqui está a implementação do OpenBSD :

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Vale ressaltar o último comentário de confirmação desse código para aqueles que precisam implementar coisas semelhantes:

Altere arc4random_uniform () para calcular 2**32 % upper_boundcomo -upper_bound % upper_bound. Simplifica o código e o torna o mesmo nas arquiteturas ILP32 e LP64, e também um pouco mais rápido nas arquiteturas LP64 usando um restante de 32 bits em vez de um restante de 64 bits.

Apontado por Jorden Verwer no tech @ ok deraadt; sem objeções de djm ou otto

A implementação Java também é facilmente localizável (consulte o link anterior):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }
Rob Napier
fonte
Observe que, se arcfour_random() realmente usar o algoritmo RC4 real em sua implementação, a saída definitivamente terá algum viés. Esperamos que os autores da sua biblioteca tenham passado a usar um CSPRNG melhor por trás da mesma interface. Lembro-me de que um dos BSDs atualmente usa o algoritmo ChaCha20 para implementar arcfour_random(). Mais informações sobre os preconceitos RC4 saída que torná-lo inútil para a segurança ou outras aplicações críticas, tais como vídeo poker: blog.cryptographyengineering.com/2013/03/...
rmalayter
2
@rmalayter No iOS e OS X, o arc4random lê em / dev / random, que é a entropia da mais alta qualidade no sistema. (O "arc4" no nome é histórico e preservado para compatibilidade.)
Rob Napier
@ Rob_Napier é bom saber, mas /dev/randomtambém usou o RC4 em algumas plataformas no passado (o Linux usa SHA-1 no modo contador). Infelizmente, as páginas de manual que encontrei por meio de pesquisa indicam que o RC4 ainda está em uso em várias plataformas que oferecem arc4random(embora o código real possa ser diferente).
precisa saber é o seguinte
1
Estou confuso. Não é -upper_bound % upper_bound == 0??
91319 Jon McClung
1
@JonMcClung -upper_bound % upper_boundserá realmente 0 se intfor maior que 32 bits. Deveria ser (u_int32_t)-upper_bound % upper_bound)(assumindo que u_int32_tseja um BSD-ism para uint32_t).
22819 Ian Abbott
14

Definição

Viés do módulo é o viés inerente ao uso da aritmética do módulo para reduzir um conjunto de saída para um subconjunto do conjunto de entrada. Em geral, existe um viés sempre que o mapeamento entre o conjunto de entrada e saída não é igualmente distribuído, como no caso de usar aritmética de módulo quando o tamanho do conjunto de saída não é um divisor do tamanho do conjunto de entrada.

Esse viés é particularmente difícil de evitar na computação, onde os números são representados como cadeias de bits: 0s e 1s. Encontrar fontes verdadeiramente aleatórias de aleatoriedade também é extremamente difícil, mas está além do escopo desta discussão. Para o restante desta resposta, suponha que exista uma fonte ilimitada de bits verdadeiramente aleatórios.

Exemplo de Problema

Vamos considerar a simulação de uma rolagem de dados (0 a 5) usando esses bits aleatórios. Como existem 6 possibilidades, precisamos de bits suficientes para representar o número 6, que é 3 bits. Infelizmente, três bits aleatórios produzem 8 resultados possíveis:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Podemos reduzir o tamanho do resultado definido para exatamente 6 assumindo o valor módulo 6, no entanto, isso apresenta o problema de polarização do módulo : 110gera um 0 e 111gera um 1. Esse dado é carregado.

Soluções Potenciais

Abordagem 0:

Em vez de confiar em bits aleatórios, em teoria, alguém poderia contratar um pequeno exército para rolar dados o dia todo e registrar os resultados em um banco de dados, e depois usar cada resultado apenas uma vez. Isso é tão prático quanto parece, e mais do que provavelmente não produziria resultados verdadeiramente aleatórios de qualquer maneira (trocadilhos).

Abordagem 1:

Em vez de usar o módulo, uma solução ingénuo mas matematicamente correcto é a resultados de descarte que o rendimento 110e 111e simplesmente tentar novamente com 3 novos bits. Infelizmente, isso significa que há uma chance de 25% em cada rolagem de que será necessária uma repetição, incluindo cada uma delas . Isso é claramente impraticável para todos, exceto para os usos mais triviais.

Abordagem 2:

Use mais bits: em vez de 3 bits, use 4. Isso gera 16 resultados possíveis. Obviamente, relançar sempre que o resultado for maior que 5 piora as coisas (10/16 = 62,5%), para que sozinho não ajude.

Observe que 2 * 6 = 12 <16, para que possamos obter com segurança qualquer resultado menor que 12 e reduzir esse módulo 6 para distribuir uniformemente os resultados. Os outros quatro resultados devem ser descartados e, em seguida, relançados como na abordagem anterior.

Parece bom no começo, mas vamos verificar a matemática:

4 discarded results / 16 possibilities = 25%

Nesse caso, 1 bit extra não ajudou em nada!

Esse resultado é lamentável, mas vamos tentar novamente com 5 bits:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Uma melhoria definitiva, mas não boa o suficiente em muitos casos práticos. A boa notícia é que adicionar mais bits nunca aumentará as chances de precisar descartar e relançar . Isso vale não apenas para dados, mas em todos os casos.

Como demonstrado , no entanto, adicionar um bit extra pode não mudar nada. De fato, se aumentarmos nosso rolo para 6 bits, a probabilidade permanecerá 6,25%.

Isso gera 2 perguntas adicionais:

  1. Se adicionarmos bits suficientes, existe uma garantia de que a probabilidade de um descarte diminua?
  2. Quantos bits são suficientes no caso geral?

Solução Geral

Felizmente, a resposta para a primeira pergunta é sim. O problema com 6 é que 2 ^ x mod 6 alterna entre 2 e 4, que coincidentemente são um múltiplo de 2 um do outro, de modo que, para um x uniforme> 1,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Assim, 6 é uma exceção e não a regra. É possível encontrar módulos maiores que produzam poderes consecutivos de 2 da mesma maneira, mas eventualmente isso deve ser contornado, e a probabilidade de um descarte será reduzida.

Sem oferecer mais provas, em geral o uso do dobro do número de bits necessário fornecerá uma chance menor, geralmente insignificante, de descarte.

Prova de conceito

Aqui está um exemplo de programa que usa o libcrypo do OpenSSL para fornecer bytes aleatórios. Ao compilar, certifique-se de vincular à biblioteca com a -lcryptoqual a maioria das pessoas deve ter disponível.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

Encorajo a jogar com os valores MODULUSe ROLLSpara ver quantas repetições realmente acontecem na maioria das condições. Uma pessoa cética também pode querer salvar os valores calculados em arquivo e verificar se a distribuição parece normal.

Jim Wood
fonte
Eu realmente espero que ninguém tenha copiado cegamente sua implementação aleatória uniforme. A randomPool = RAND_bytes(...)linha sempre resultará randomPool == 1devido à afirmação. Isso sempre resulta em um descarte e um relançamento. Eu acho que você queria declarar em uma linha separada. Conseqüentemente, isso fez com que o RNG retornasse 1para cada iteração.
Qix - MONICA FOI ERRADA em
Para ser claro, randomPoolsempre será avaliado de 1acordo com a documentaçãoRAND_bytes() do OpenSSL , pois ele sempre será bem-sucedido graças à RAND_status()asserção.
Qix - MONICA FOI ERRADA em
9

Existem duas queixas usuais com o uso do módulo.

  • um é válido para todos os geradores. É mais fácil ver em um caso limite. Se o seu gerador tiver um RAND_MAX que é 2 (que não é compatível com o padrão C) e você deseja apenas 0 ou 1 como valor, o uso do módulo gerará 0 duas vezes mais (quando o gerador gerar 0 e 2) gerar 1 (quando o gerador gerar 1). Observe que isso é verdade assim que você não descarta valores, qualquer que seja o mapeamento que você está usando dos valores do gerador para o desejado, um ocorrerá duas vezes mais que o outro.

  • algum tipo de gerador tem seus bits menos significativos menos aleatórios que o outro, pelo menos para alguns de seus parâmetros, mas, infelizmente, esses parâmetros têm outra característica interessante (como ter RAND_MAX um a menos que uma potência de 2). O problema é bem conhecido e, por um longo tempo, a implementação da biblioteca provavelmente evita o problema (por exemplo, a implementação de amostra rand () no padrão C usa esse tipo de gerador, mas descarta os 16 bits menos significativos), mas alguns gostam de reclamar isso e você pode ter azar

Usando algo como

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

gerar um número aleatório entre 0 e n evitará os dois problemas (e evita o estouro com RAND_MAX == INT_MAX)

BTW, C ++ 11 introduziu maneiras padrão para a redução e outro gerador que não rand ().

AProgrammer
fonte
n == RAND_MAX? 1: (RAND_MAX-1) / (n + 1): Entendo que a idéia aqui é primeiro dividir RAND_MAX em tamanho de página igual N, depois retornar o desvio dentro de N, mas não consigo mapear o código para isso com precisão.
zinking
1
A versão ingênua deve ser (RAND_MAX + 1) / (n + 1), pois há valores RAND_MAX + 1 para dividir em n + 1 buckets. Se para evitar o estouro ao calcular RAND_MAX + 1, ele pode ser transformado em 1+ (RAND_MAX-n) / (n + 1). Para evitar o estouro ao calcular n + 1, o caso n == RAND_MAX é verificado primeiro.
AProgrammer
+ mais, dividir parece estar custando mais, mesmo em comparação com números regenerados.
zinking 15/06/12
4
Tomar o módulo e dividir têm o mesmo custo. Alguns ISA fornecem apenas uma instrução que fornece sempre as duas. O custo da regeneração de números dependerá de ne RAND_MAX. Se n for pequeno em relação a RAND_MAX, pode custar muito. E, obviamente, você pode decidir que os vieses não são importantes para a sua aplicação; Eu apenas dou um jeito de evitá-los.
AProgrammer
9

A solução de Mark (a solução aceita) é quase perfeita.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

editou Mar 25 '16 às 23:16

Mark Amery 39k21170211

No entanto, há uma ressalva que descarta 1 conjunto válido de resultados em qualquer cenário em que RAND_MAX( RM) é 1 menor que um múltiplo de N(Onde N= o número possível de resultados válidos).

ou seja, quando a 'contagem de valores descartados' ( D) é igual a N, então eles são realmente um conjunto válido ( V), não um conjunto inválido ( I).

O que causa isso é que, em algum momento, Mark perde de vista a diferença entre Ne Rand_Max.

Né um conjunto cujos membros válidos são compostos apenas por números inteiros positivos, pois contém uma contagem de respostas que seriam válidas. (por exemplo: Set N= {1, 2, 3, ... n })

Rand_max No entanto, é um conjunto que (conforme definido para nossos propósitos) inclui qualquer número de números inteiros não negativos.

Em sua forma mais genérica, o que é definido aqui como Rand Maxé o Conjunto de todos os resultados válidos, que teoricamente podem incluir números negativos ou valores não numéricos.

Portanto, Rand_Maxé melhor definido como o conjunto de "Respostas possíveis".

No entanto, Nopera contra a contagem dos valores dentro do conjunto de respostas válidas, portanto, mesmo conforme definido em nosso caso específico, Rand_Maxserá um valor um a menos que o número total que ele contém.

Usando a solução de Mark, os valores são descartados quando: X => RM - RM% N

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Como você pode ver no exemplo acima, quando o valor de X (o número aleatório que obtemos da função inicial) é 252, 253, 254 ou 255, nós o descartávamos, mesmo que esses quatro valores incluam um conjunto válido de valores retornados .

IE: Quando a contagem dos valores Descartados (I) = N (O número de resultados válidos), um conjunto válido de valores de retorno será descartado pela função original.

Se descrevermos a diferença entre os valores N e RM como D, ou seja:

D = (RM - N)

Então, à medida que o valor de D se torna menor, a Porcentagem de relançamentos desnecessários devido a esse método aumenta a cada multiplicativo natural. (Quando RAND_MAX NÃO é igual a um número primo, isso é uma preocupação válida)

POR EXEMPLO:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Como a porcentagem de Rerolls necessários aumenta quanto mais N chega ao RM, isso pode ser uma preocupação válida para muitos valores diferentes, dependendo das restrições do sistema que ele está executando e dos valores que estão sendo procurados.

Para negar isso, podemos fazer uma alteração simples, como mostrado aqui:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

Isso fornece uma versão mais geral da fórmula, que explica as peculiaridades adicionais do uso do módulo para definir seus valores máximos.

Exemplos de uso de um valor pequeno para RAND_MAX, que é um multiplicativo de N.

Mark'original Version:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Versão Generalizada 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

Além disso, no caso em que N deve ser o número de valores em RAND_MAX; nesse caso, você pode definir N = RAND_MAX +1, a menos que RAND_MAX = INT_MAX.

Em termos de loop, você pode simplesmente usar N = 1, e qualquer valor de X será aceito, no entanto, e inserir uma instrução IF para o seu multiplicador final. Mas talvez você tenha um código que possa ter um motivo válido para retornar 1 quando a função for chamada com n = 1 ...

Portanto, pode ser melhor usar 0, o que normalmente forneceria um erro Div 0, quando você deseja ter n = RAND_MAX + 1

Versão generalizada 2:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

Ambas as soluções resolvem o problema com resultados válidos descartados desnecessariamente, que ocorrerão quando RM + 1 for um produto de n.

A segunda versão também aborda o cenário de casos extremos quando você precisa de n para igualar o conjunto total possível de valores contidos em RAND_MAX.

A abordagem modificada em ambos é a mesma e permite uma solução mais geral para a necessidade de fornecer números aleatórios válidos e minimizar os valores descartados.

Reiterar:

A solução geral básica que amplia o exemplo da marca:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

 x %= n;

A solução geral estendida que permite um cenário adicional de RAND_MAX + 1 = n:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

    x %= n;
} else {
    x = rand();
}

Em alguns idiomas (idiomas especialmente interpretados), fazer os cálculos da operação de comparação fora da condição while pode levar a resultados mais rápidos, pois esse é um cálculo único, independentemente de quantas tentativas forem necessárias. YMMV!

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x; // Resulting random number
int y; // One-time calculation of the compare value for x

if n != 0 {
    y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 
    do {
        x = rand();
    } while (x > y);

    x %= n;
} else {
    x = rand();
}
Ben Personick
fonte
Não é seguro dizer que o problema com a solução de Mark é que ele trata RAND_MAX en como a mesma "unidade de medida" quando na verdade eles significam duas coisas diferentes? Enquanto n representa o "número de possibilidades" resultante, RAND_MAX representa apenas o valor máximo da possibilidade original, onde RAND_MAX + 1 seria o número original de possibilidades. Estou surpreso que ele não chegar ao seu conclusão, pois ele parecia ter reconhecido n e RAND_MAX não eram a mesma coisa com a equação:RAND_MAX%n = n - 1
Danilo Souza Moraes
@ DaniloSouzaMorães Obrigado Danilo, você colocou o assunto de forma muito sucinta. Fui demonstrar o que ele estava fazendo junto com o porquê e como, mas acho que nunca fui capaz de afirmar o que ele estava fazendo de maneira eloquente, pois fico tão envolvido nos detalhes da lógica de como e por que existe um problema, que não estou afirmando tão claramente o que está em questão. Você se importa se eu alterar minha resposta para usar parte do que você escreveu aqui como meu próprio resumo da questão sobre o que e onde a solução aceita está fazendo o que precisa ser tratado próximo ao topo?
Ben Personick
Isso seria demais. Vá em frente
Danilo Souza Morães
1

Com um RAND_MAXvalor de 3(na realidade, deve ser muito maior que isso, mas o viés ainda existiria), faz sentido a partir desses cálculos que existe um viés:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

Nesse caso, % 2é isso que você não deve fazer quando quiser um número aleatório entre 0e 1. Você pode obter um número aleatório entre 0e 2fazendo isso % 3, porque neste caso: RAND_MAXé um múltiplo de 3.

Outro método

Há muito mais simples, mas para adicionar a outras respostas, eis a minha solução para obter um número aleatório entre 0e n - 1, portanto n, possibilidades diferentes, sem viés.

  • o número de bits (não bytes) necessário para codificar o número de possibilidades é o número de bits de dados aleatórios necessários
  • codificar o número de bits aleatórios
  • se esse número for >= n, reinicie (sem módulo).

Não é fácil obter dados realmente aleatórios, por que usar mais bits do que o necessário?

Abaixo está um exemplo no Smalltalk, usando um cache de bits de um gerador de números pseudo-aleatórios. Como não sou especialista em segurança, use por sua conta e risco.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r
Rivenfall
fonte
-1

Como a resposta aceita indica, o "viés do módulo" tem suas raízes no baixo valor de RAND_MAX. Ele usa um valor extremamente pequeno de RAND_MAX(10) para mostrar que se RAND_MAX fosse 10, você tentaria gerar um número entre 0 e 2 usando%, resultariam nos seguintes resultados:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

Portanto, existem 4 saídas de 0 (chance 4/10) e apenas 3 saídas de 1 e 2 (3/10 chances cada).

Então é tendencioso. Os números mais baixos têm uma chance melhor de sair.

Mas isso só aparece tão obviamente quando RAND_MAXé pequeno . Ou, mais especificamente, quando o número pelo qual você está modificando é grande em comparação comRAND_MAX.

Uma solução muito melhor do que o loop (que é incrivelmente ineficiente e nem deveria ser sugerido) é usar um PRNG com uma faixa de saída muito maior. O algoritmo Mersenne Twister tem uma saída máxima de 4.294.967.295. Como tal, MersenneTwister::genrand_int32() % 10para todos os efeitos, será igualmente distribuído e o efeito do viés do módulo desaparecerá.

bobobobo
fonte
3
O seu é mais eficiente e provavelmente é verdade que, se RAND_MAX for significativamente maior, o número pelo qual você está modificando, no entanto, o seu ainda será tendencioso. É verdade que todos são geradores de números pseudo-aleatórios e, por si só, é um tópico diferente, mas se você assume um gerador de números totalmente aleatório, seu caminho ainda influencia os valores mais baixos.
user1413793
Como o valor mais alto é ímpar, MT::genrand_int32()%2escolhe 0 (50 + 2,3e-8)% do tempo e 1 (50 - 2,3e-8)% do tempo. A menos que você esteja construindo o RGN de ​​um cassino (para o qual provavelmente usaria um RGN de ​​alcance muito maior), qualquer usuário não notará 2,3 e 8% a mais do tempo. Você está falando de números pequenos demais para importar aqui.
bobobobo
7
Looping é a melhor solução. Não é "insanamente ineficiente"; exigindo menos que o dobro das iterações no pior caso médio. Usar um RAND_MAXvalor alto diminuirá o viés do módulo, mas não o eliminará. Looping vontade.
Jared Nielsen
5
Se RAND_MAXfor suficientemente maior que o número pelo qual você está modificando, o número de vezes que você precisa regenerar o número aleatório é muito pequeno e não afetará a eficiência. Eu digo para manter o loop, desde que você esteja testando contra o maior múltiplo de, ne não apenas nconforme proposto pela resposta aceita.
Mark Ransom
-3

Acabei de escrever um código para o Método de Moeda Imparcial de Von Neumann, que teoricamente deveria eliminar qualquer viés no processo de geração de números aleatórios. Mais informações podem ser encontradas em ( http://en.wikipedia.org/wiki/Fair_coin )

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}
Yavuz Koroglu
fonte
Isso não resolve o viés do módulo. Esse processo pode ser usado para eliminar o viés em um fluxo de bits. No entanto, para passar de um fluxo de bits para uma distribuição uniforme de 0 a n, em que n não é nem um a menos que uma potência de dois, é necessário corrigir o viés do módulo. Portanto, esta solução não pode eliminar nenhum viés no processo de geração de números aleatórios.
Rick Rick
2
@Rick hmm. A extensão lógica do método de Von Neumann para eliminar o viés do módulo ao gerar um número aleatório entre, digamos, 1 e 100, seria: A) ligar rand() % 100100 vezes. B) se todos os resultados forem diferentes, pegue o primeiro. C) caso contrário, GOTO A. Isso funcionará, mas com um número esperado de iterações de cerca de 10 ^ 42, você precisará ser bastante paciente. E imortal.
Mark Amery
@ MarkAmery De fato, isso deve funcionar. Examinando esse algoritmo, ele não foi implementado corretamente. O primeiro mais deve ser:else if(prev==2) prev= x1; else { if(prev!=x1) return prev; prev=2;}
Rick