Por que rand () repete números com muito mais frequência no Linux que no Mac?

Eu estava implementando um hashmap em C como parte de um projeto no qual estou trabalhando e usando inserções aleatórias para testá-lo quando notei que rand()no Linux parece repetir números com muito mais frequência do que no Mac. RAND_MAXé 2147483647 / 0x7FFFFFFF nas duas plataformas. Eu o reduzi a este programa de teste que faz com que uma matriz de bytes seja RAND_MAX+1longa, gere RAND_MAXnúmeros aleatórios, anote se cada uma é uma duplicata e verifique a lista como visto.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main() {
    size_t size = ((size_t)RAND_MAX) + 1;
    char *randoms = calloc(size, sizeof(char));
    int dups = 0;
    srand(time(0));
    for (int i = 0; i < RAND_MAX; i++) {
        int r = rand();
        if (randoms[r]) {
            // printf("duplicate at %d\n", r);
            dups++;
        }
        randoms[r] = 1;
    }
    printf("duplicates: %d\n", dups);
}

O Linux gera consistentemente cerca de 790 milhões de duplicatas. O Mac sempre gera apenas um, de modo que percorre todos os números aleatórios que pode gerar quase sem repetir. Alguém pode me explicar como isso funciona? Não sei dizer nada diferente das páginas de manual, não sei qual RNG está usando e não consigo encontrar nada online. Obrigado!

Embora a princípio pareça que o macOS rand()é de alguma forma melhor por não repetir nenhum número, observe-se que, com essa quantidade de números gerados, espera -se que haja muitas duplicatas (na verdade, cerca de 790 milhões, ou (2 ³¹ -1 ) / e ). Da mesma forma, a iteração pelos números em sequência também não produziria duplicatas, mas não seria considerada muito aleatória. Portanto, a rand()implementação do Linux é indistinguível neste teste de uma verdadeira fonte aleatória, enquanto o macOS rand()não é.

Outra coisa que parece surpreendente à primeira vista é como o macOS rand()pode gerenciar para evitar duplicatas tão bem. Observando seu código fonte , achamos que a implementação é a seguinte:

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

Isso realmente resulta em todos os números entre 1 e RAND_MAX, inclusive, exatamente uma vez, antes que a sequência se repita novamente. Como o próximo estado é baseado na multiplicação, o estado nunca pode ser zero (ou todos os estados futuros também seriam zero). Assim, o número repetido que você vê é o primeiro e zero é o que nunca é retornado.

A Apple promove o uso de geradores de números aleatórios melhores em sua documentação e exemplos há pelo menos enquanto o macOS (ou OS X) existir, portanto a qualidade de rand()provavelmente não é considerada importante e eles apenas seguiram um os geradores pseudo-aleatórios mais simples disponíveis. (Como você observou, eles rand()são comentados com uma recomendação de uso arc4random().)

Em uma nota relacionada, o gerador de números pseudoaleatórios mais simples que eu achei que produz resultados decentes nesses (e em muitos outros) testes de aleatoriedade é xorshift * :

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Essa implementação resulta em quase exatamente 790 milhões de duplicatas em seu teste.

O MacOS fornece uma função rand () não documentada no stdlib. Se você não for observado, os primeiros valores gerados serão 16807, 282475249, 1622650073, 984943658 e 1144108930. Uma pesquisa rápida mostrará que essa sequência corresponde a um gerador de números aleatórios LCG muito básico que itera a seguinte fórmula:

x _{n + 1} = 7 ⁵ · x _n (MOD 2 ^{31 de} - 1)

Como o estado desse RNG é descrito inteiramente pelo valor de um único inteiro de 32 bits, seu período não é muito longo. Para ser mais preciso, ele se repete a cada 2 ³¹ - 2 iterações, produzindo todos os valores de 1 a 2 ³¹ - 2.

Eu não acho que exista uma implementação padrão do rand () para todas as versões do Linux, mas há uma função glibc rand () que é frequentemente usada. Em vez de uma única variável de estado de 32 bits, ela usa um pool de mais de 1000 bits, que, para todos os efeitos, nunca produzirá uma sequência totalmente repetida. Novamente, você provavelmente pode descobrir qual versão possui imprimindo as primeiras saídas desse RNG sem propagá-lo primeiro. (A função glibc rand () produz os números 1804289383, 846930886, 1681692777, 1714636915 e 1957747793.)

Portanto, a razão pela qual você está tendo mais colisões no Linux (e quase nenhuma no MacOS) é que a versão do rand () para Linux é basicamente mais aleatória.

rand()é definido pelo padrão C, e o padrão C não especifica qual algoritmo usar. Obviamente, a Apple está usando um algoritmo inferior à sua implementação GNU / Linux: o Linux é indistinguível de uma verdadeira fonte aleatória em seu teste, enquanto a implementação da Apple apenas embaralha os números.

Se você quiser números aleatórios de qualquer qualidade, use um PRNG melhor que ofereça pelo menos algumas garantias sobre a qualidade dos números retornados ou simplesmente leia /dev/urandomou similar. O último fornece números de qualidade criptográfica, mas é lento. Mesmo que seja muito lento por si só, /dev/urandompode fornecer algumas sementes excelentes para outro PRNG mais rápido.

Em geral, o par rand / srand foi considerado como obsoleto por um longo tempo devido aos bits de ordem inferior exibirem menos aleatoriedade do que os bits de ordem superior nos resultados. Isso pode ou não ter algo a ver com seus resultados, mas acho que ainda é uma boa oportunidade para lembrar que, embora algumas implementações de rand / srand estejam agora mais atualizadas, as implementações mais antigas persistem e é melhor usar aleatoriamente (3 ) Na minha caixa do Arch Linux, a seguinte nota ainda está na página de manual do rand (3):

  The versions of rand() and srand() in the Linux C Library use the  same
   random number generator as random(3) and srandom(3), so the lower-order
   bits should be as random as the higher-order bits.  However,  on  older
   rand()  implementations,  and  on  current implementations on different
   systems, the lower-order bits are much less random than the  higher-or-
   der bits.  Do not use this function in applications intended to be por-
   table when good randomness is needed.  (Use random(3) instead.)

Logo abaixo, a página de manual fornece exemplos de implementações rand e srand muito curtos e simples, que são sobre os RNGs de LC mais simples que você já viu e possui um pequeno RAND_MAX. Eu não acho que eles correspondam ao que está na biblioteca padrão C, se é que o fizeram. Ou pelo menos espero que não.

Em geral, se você usar algo da biblioteca padrão, use aleatoriamente, se puder (a página de manual o lista como padrão POSIX no POSIX.1-2001, mas rand é o padrão antes de C ser padronizado) . Ou melhor ainda, abra as Receitas numéricas (ou procure on-line) ou Knuth e implemente uma. Eles são realmente fáceis e você só precisa fazer isso uma vez para ter um RNG de uso geral com os atributos que você mais precisa e que são de qualidade conhecida.