Como gerar um número inteiro aleatório dentro de um intervalo

Esta é uma continuação de uma pergunta postada anteriormente:

Como gerar um número aleatório em C?

Desejo ser capaz de gerar um número aleatório dentro de um determinado intervalo, como 1 a 6, para imitar os lados de um dado.

Como eu faria isso?

Todas as respostas até agora estão matematicamente erradas. Retornar rand() % Nnão fornece uniformemente um número no intervalo, a [0, N)menos que Ndivida a duração do intervalo no qual rand()retorna (ou seja, é uma potência de 2). Além disso, não se tem idéia se os módulos de rand()são independentes: é possível que eles vão 0, 1, 2, ..., o que é uniforme, mas não muito aleatório. A única suposição que parece razoável fazer é que produz rand()uma distribuição de Poisson: quaisquer dois subintervalos não sobrepostos do mesmo tamanho são igualmente prováveis ​​e independentes. Para um conjunto finito de valores, isso implica uma distribuição uniforme e também garante que os valores de rand()sejam bem dispersos.

Isso significa que a única maneira correta de alterar o intervalo de rand()é dividi-lo em caixas; por exemplo, se RAND_MAX == 11você quiser um intervalo de 1..6, deve atribuir {0,1}a 1, {2,3}a 2 e assim por diante. Esses são intervalos separados e de tamanhos iguais e, portanto, são uniformemente e independentemente distribuídos.

A sugestão de usar a divisão de ponto flutuante é matematicamente plausível, mas apresenta problemas de arredondamento em princípio. Talvez doubleseja uma precisão alta o suficiente para fazê-lo funcionar; talvez não. Eu não sei e não quero ter que descobrir; em qualquer caso, a resposta depende do sistema.

A maneira correta é usar aritmética inteira. Ou seja, você deseja algo como o seguinte:

#include <stdlib.h> // For random(), RAND_MAX

// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
  unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;

  long x;
  do {
   x = random();
  }
  // This is carefully written not to overflow
  while (num_rand - defect <= (unsigned long)x);

  // Truncated division is intentional
  return x/bin_size;
}

O loop é necessário para obter uma distribuição perfeitamente uniforme. Por exemplo, se você receber números aleatórios de 0 a 2 e quiser apenas números de 0 a 1, continue puxando até não obter um 2; não é difícil verificar se isso dá 0 ou 1 com probabilidade igual. Esse método também é descrito no link que ns forneceu na resposta, embora codificado de forma diferente. Estou usando em random()vez de rand()porque tem uma distribuição melhor (conforme observado na página do manual para rand()).

Se você quiser obter valores aleatórios fora da faixa padrão [0, RAND_MAX], terá que fazer algo complicado. Talvez o mais expediente seja definir uma função random_extended()que extraia nbits (usando random_at_most()) e retorna [0, 2**n), e então aplicar random_at_most()com random_extended()no lugar de random()(e 2**n - 1no lugar de RAND_MAX) para extrair um valor aleatório menor que 2**n, supondo que você tenha um tipo numérico que pode conter tal um valor. Finalmente, é claro, você pode obter valores em [min, max]uso min + random_at_most(max - min), incluindo valores negativos.

Seguindo a resposta de @Ryan Reich, pensei em oferecer minha versão limpa. A primeira verificação de limites não é necessária devido à segunda verificação de limites, e a tornei iterativa em vez de recursiva. Ele retorna valores no intervalo [min, max], onde max >= mine 1+max-min < RAND_MAX.

unsigned int rand_interval(unsigned int min, unsigned int max)
{
    int r;
    const unsigned int range = 1 + max - min;
    const unsigned int buckets = RAND_MAX / range;
    const unsigned int limit = buckets * range;

    /* Create equal size buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    do
    {
        r = rand();
    } while (r >= limit);

    return min + (r / buckets);
}

Esta é uma fórmula se você souber os valores máximos e mínimos de um intervalo e quiser gerar números inclusivos entre o intervalo:

r = (rand() % (max + 1 - min)) + min

unsigned int
randr(unsigned int min, unsigned int max)
{
       double scaled = (double)rand()/RAND_MAX;

       return (max - min +1)*scaled + min;
}

Veja aqui outras opções.

Você não faria apenas:

srand(time(NULL));
int r = ( rand() % 6 ) + 1;

%é o operador de módulo. Essencialmente, ele vai apenas dividir por 6 e retornar o restante ... de 0 - 5

Para aqueles que entendem o problema de polarização, mas não suportam o tempo de execução imprevisível de métodos baseados em rejeição, esta série produz um número inteiro aleatório progressivamente menos polarizado no [0, n-1]intervalo:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

Ele faz isso sintetizando um número aleatório de i * log_2(RAND_MAX + 1)bits de ponto fixo de alta precisão (onde ié o número de iterações) e realizando uma longa multiplicação por n.

Quando o número de bits é suficientemente grande em comparação com n, a tendência torna-se incomensuravelmente pequena.

Não importa se RAND_MAX + 1é menor que n(como nesta questão ), ou se não é uma potência de dois, mas deve-se tomar cuidado para evitar estouro de inteiro se RAND_MAX * nfor grande.

Para evitar o viés do módulo (sugerido em outras respostas), você sempre pode usar:

arc4random_uniform(MAX-MIN)+MIN

Onde "MAX" é o limite superior e "MIN" é o limite inferior. Por exemplo, para números entre 10 e 20:

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Solução simples e melhor do que usar "rand ()% N".

Aqui está um algoritmo ligeiramente mais simples do que a solução de Ryan Reich:

/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
    uint32_t range = (end - begin) + 1;
    uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);

    /* Imagine range-sized buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    uint32_t randVal = rand();
    while (randVal >= limit) randVal = rand();

    /// Return the position you hit in the bucket + begin as random number
    return (randVal % range) + begin;
}

Example (RAND_MAX := 16, begin := 2, end := 7)
    => range := 6  (1 + end - begin)
    => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)

The limit is always a multiple of the range,
so we can split it into range-sized buckets:
    Possible-rand-output: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    Buckets:             [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
    Buckets + begin:     [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]

1st call to rand() => 13
    → 13 is not in the bucket-range anymore (>= limit), while-condition is true
        → retry...
2nd call to rand() => 7
    → 7 is in the bucket-range (< limit), while-condition is false
        → Get the corresponding bucket-value 1 (randVal % range) and add begin
    => 3

Embora Ryan esteja correto, a solução pode ser muito mais simples com base no que se sabe sobre a origem da aleatoriedade. Para reafirmar o problema:

• Existe uma fonte de aleatoriedade, produzindo números inteiros em uma faixa [0, MAX)com distribuição uniforme.
• O objetivo é produzir números inteiros aleatórios uniformemente distribuídos no intervalo [rmin, rmax]onde 0 <= rmin < rmax < MAX.

Na minha experiência, se o número de caixas (ou "caixas") for significativamente menor do que o intervalo dos números originais, e a fonte original for criptograficamente forte - não há necessidade de passar por todo aquele rigamarole, e a divisão simples do módulo faria são suficientes (como output = rnd.next() % (rmax+1), se rmin == 0) e produzem números aleatórios que são distribuídos uniformemente "o suficiente" e sem qualquer perda de velocidade. O fator chave é a fonte de aleatoriedade (ou seja, crianças, não tente fazer isso em casa com rand()).

Aqui está um exemplo / prova de como funciona na prática. Eu queria gerar números aleatórios de 1 a 22, tendo uma fonte criptograficamente forte que produzisse bytes aleatórios (com base em Intel RDRAND). Os resultados são:

Rnd distribution test (22 boxes, numbers of entries in each box):     
 1: 409443    4.55%
 2: 408736    4.54%
 3: 408557    4.54%
 4: 409125    4.55%
 5: 408812    4.54%
 6: 409418    4.55%
 7: 408365    4.54%
 8: 407992    4.53%
 9: 409262    4.55%
10: 408112    4.53%
11: 409995    4.56%
12: 409810    4.55%
13: 409638    4.55%
14: 408905    4.54%
15: 408484    4.54%
16: 408211    4.54%
17: 409773    4.55%
18: 409597    4.55%
19: 409727    4.55%
20: 409062    4.55%
21: 409634    4.55%
22: 409342    4.55%   
total: 100.00%

Isso é o mais uniforme que preciso para o meu propósito (lançamento de dados justo, geração de livros de código criptograficamente fortes para máquinas de criptografia da Segunda Guerra Mundial, como http://users.telenet.be/d.rijmenants/en/kl-7sim.htm , etc. ) A saída não mostra qualquer tendência apreciável.

Aqui está a fonte do gerador de números aleatórios criptograficamente forte (verdadeiro): Intel Digital Random Number Generator e um código de amostra que produz números aleatórios de 64 bits (sem sinal).

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

  asm("rdrand %%rax; \
        mov $1,%%edx; \
        cmovae %%rax,%%rdx; \
        mov %%edx,%1; \
        mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
        *therand = foo;
  return cf_error_status;
}

Compilei-o no Mac OS X com clang-6.0.1 (direto) e com gcc-4.8.3 usando o sinalizador "-Wa, q" (porque o GAS não suporta essas novas instruções).

Como dito antes, o módulo não é suficiente porque distorce a distribuição. Aqui está o meu código que mascara os bits e os usa para garantir que a distribuição não seja distorcida.

static uint32_t randomInRange(uint32_t a,uint32_t b) {
    uint32_t v;
    uint32_t range;
    uint32_t upper;
    uint32_t lower;
    uint32_t mask;

    if(a == b) {
        return a;
    }

    if(a > b) {
        upper = a;
        lower = b;
    } else {
        upper = b;
        lower = a; 
    }

    range = upper - lower;

    mask = 0;
    //XXX calculate range with log and mask? nah, too lazy :).
    while(1) {
        if(mask >= range) {
            break;
        }
        mask = (mask << 1) | 1;
    }


    while(1) {
        v = rand() & mask;
        if(v <= range) {
            return lower + v;
        }
    }

}

O código simples a seguir permite que você observe a distribuição:

int main() {

    unsigned long long int i;


    unsigned int n = 10;
    unsigned int numbers[n];


    for (i = 0; i < n; i++) {
        numbers[i] = 0;
    }

    for (i = 0 ; i < 10000000 ; i++){
        uint32_t rand = random_in_range(0,n - 1);
        if(rand >= n){
            printf("bug: rand out of range %u\n",(unsigned int)rand);
            return 1;
        }
        numbers[rand] += 1;
    }

    for(i = 0; i < n; i++) {
        printf("%u: %u\n",i,numbers[i]);
    }

}

Retornará um número de ponto flutuante no intervalo [0,1]:

#define rand01() (((double)random())/((double)(RAND_MAX)))