C Language
Generazione di numeri casuali

Osservazioni

Generazione di numeri casuali di base

La funzione rand() può essere utilizzata per generare un valore intero pseudo-casuale compreso tra 0 e RAND_MAX (incluso 0 e RAND_MAX ).

srand(int) viene utilizzato per seminare il generatore di numeri pseudo-casuali. Ogni volta che rand() viene seminato con lo stesso seme, deve produrre la stessa sequenza di valori. Dovrebbe essere seminato solo una volta prima di chiamare rand() . Non dovrebbe essere ripetutamente seminato o risettato ogni volta che si desidera generare una nuova serie di numeri pseudocasuali.

La pratica standard consiste nell'usare il risultato del time(NULL) come seme. Se il generatore di numeri casuali richiede una sequenza deterministica, è possibile inizializzare il generatore con lo stesso valore all'inizio di ciascun programma. Generalmente non è richiesto per il codice di rilascio, ma è utile nelle esecuzioni di debug per rendere riproducibili i bug.

Si consiglia di seminare il generatore sempre, se non seminato, si comporta come se fosse seminato con srand(1) .

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

int main(void) {
    int i;
    srand(time(NULL));
    i = rand();

    printf("Random value between [0, %d]: %d\n", RAND_MAX, i);
    return 0;
}

Uscita possibile:

Random value between [0, 2147483647]: 823321433

Gli appunti:

Lo standard C non garantisce la qualità della sequenza casuale prodotta. In passato, alcune implementazioni di rand() avevano gravi problemi nella distribuzione e casualità dei numeri generati. L'uso di rand() non è raccomandato per esigenze serie di generazione di numeri casuali, come la crittografia.

Generatore Congruenziale Permutato

Ecco un generatore di numeri casuali standalone che non si basa su rand() o funzioni di libreria simili.

Perché vorresti una cosa del genere? Forse non ti fidi del generatore di numeri casuali incorporato della tua piattaforma, o forse vuoi una fonte riproducibile di casualità indipendente da una particolare implementazione di libreria.

Questo codice è PCG32 da pcg-random.org , un RNG moderno, veloce e generico con eccellenti proprietà statistiche. Non è crittograficamente sicuro, quindi non usarlo per la crittografia.

#include <stdint.h>

/* *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
 * Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) */

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng) {
    uint64_t oldstate = rng->state;
    /* Advance internal state */
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc | 1);
    /* Calculate output function (XSH RR), uses old state for max ILP */
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq) {
    rng->state = 0U;
    rng->inc = (initseq << 1u) | 1u;
    pcg32_random_r(rng);
    rng->state += initstate;
    pcg32_random_r(rng);
}

Ed ecco come chiamarlo:

#include <stdio.h>
int main(void) {
    pcg32_random_t rng; /* RNG state */
    int i;

    /* Seed the RNG */
    pcg32_srandom_r(&rng, 42u, 54u);

    /* Print some random 32-bit integers */
    for (i = 0; i < 6; i++)
        printf("0x%08x\n", pcg32_random_r(&rng));
    
    return 0;
}

Limita la generazione a un determinato intervallo

Di solito quando si generano numeri casuali è utile generare numeri interi all'interno di un intervallo, o un valore di ap compreso tra 0.0 e 1.0. Mentre l'operazione di modulo può essere utilizzata per ridurre il seme a un numero intero basso utilizza i bit bassi, che spesso passano attraverso un ciclo breve, risultando in una leggera distorsione della distribuzione se N è grande in proporzione a RAND_MAX.

La macro

#define uniform() (rand() / (RAND_MAX + 1.0))

produce un valore di ap su 0.0 a 1.0 - epsilon, quindi

i = (int)(uniform() * N)

imposterà i a un numero casuale uniforme compreso tra 0 e N - 1.

Sfortunatamente c'è un difetto tecnico, nel senso che RAND_MAX può essere più grande di una variabile di tipo double può rappresentare con precisione. Ciò significa che RAND_MAX + 1.0 restituisce RAND_MAX e la funzione restituisce occasionalmente unità. Questo è improbabile comunque.

Generazione Xorshift

Un'alternativa buona e facile alle procedure rand() imperfette, è xorshift , una classe di generatori di numeri pseudo-casuali scoperti da George Marsaglia . Il generatore di xorshift è tra i più veloci generatori di numeri casuali non crittograficamente sicuri. Ulteriori informazioni e altre implementazioni di esempio sono disponibili sulla pagina xorshift di Wikipedia

Esempio di implementazione

#include <stdint.h>

/* These state variables must be initialised so that they are not all zero. */
uint32_t w, x, y, z;

uint32_t xorshift128(void) 
{
    uint32_t t = x;
    t ^= t << 11U;
    t ^= t >> 8U;
    x = y; y = z; z = w;
    w ^= w >> 19U;
    w ^= t;
    return w;
}