C Language
Willekeurige nummergeneratie

Opmerkingen

Basis willekeurige nummergeneratie

De functie rand() kan worden gebruikt om een pseudo-willekeurig geheel getal tussen 0 en RAND_MAX (inclusief 0 en RAND_MAX ).

srand(int) wordt gebruikt om de pseudo-willekeurige getallengenerator te zaaien. Telkens wanneer rand() met hetzelfde zaad wordt gezaaid, moet het dezelfde reeks waarden produceren. Het mag slechts eenmaal worden geplaatst voordat rand() . Het moet niet herhaaldelijk worden geplaatst of opnieuw worden ingezaaid elke keer dat u een nieuwe batch pseudo-willekeurige getallen wilt genereren.

Standaardpraktijk is om het resultaat van time(NULL) als zaad te gebruiken. Als uw willekeurige nummergenerator een deterministische reeks moet hebben, kunt u de generator bij elke programmastart met dezelfde waarde zaaien. Dit is over het algemeen niet vereist voor releasecode, maar is handig in debug-runs om bugs reproduceerbaar te maken.

Het is aan te raden om de generator altijd te zaaien, als deze niet wordt gezaaid, gedraagt deze zich alsof deze met srand(1) is gezaaid 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;
}

Mogelijke output:

Random value between [0, 2147483647]: 823321433

Opmerkingen:

De C-standaard biedt geen garantie voor de kwaliteit van de geproduceerde willekeurige volgorde. In het verleden hadden sommige implementaties van rand() ernstige problemen met de distributie en de willekeur van de gegenereerde getallen. Het gebruik van rand() wordt niet aanbevolen voor serieuze behoeften voor het genereren van willekeurige getallen, zoals cryptografie.

Permuted Congruential Generator

Hier is een zelfstandige random number-generator die niet afhankelijk is van rand() of vergelijkbare bibliotheekfuncties.

Waarom zou je zoiets willen? Misschien vertrouw je de ingebouwde random number generator van je platform niet, of wil je een reproduceerbare bron van willekeur, onafhankelijk van een bepaalde bibliotheekimplementatie.

Deze code is PCG32 van pcg-random.org , een moderne, snelle RNG voor algemene doeleinden met uitstekende statistische eigenschappen. Het is niet cryptografisch beveiligd, dus gebruik het niet voor cryptografie.

#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);
}

En hier is hoe het te noemen:

#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;
}

Beperk generatie tot een bepaald bereik

Meestal is het bij het genereren van willekeurige getallen handig om gehele getallen binnen een bereik of ap-waarde tussen 0,0 en 1,0 te genereren. Hoewel de modulusbewerking kan worden gebruikt om het zaad tot een laag geheel getal te reduceren, gebruikt dit de lage bits, die vaak een korte cyclus doorlopen, resulterend in een lichte scheeftrekking van de verdeling als N groot is in verhouding tot RAND_MAX.

De macro

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

produceert een ap-waarde van 0,0 tot 1,0 - epsilon, dus

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

stelt i op een uniform willekeurig getal tussen 0 en N - 1.

Helaas is er een technische fout, omdat RAND_MAX groter mag zijn dan een variabele van het type double nauwkeurig kan weergeven. Dit betekent dat RAND_MAX + 1.0 evalueert naar RAND_MAX en dat de functie af en toe eenheid retourneert. Dit is echter onwaarschijnlijk.

Xorshift-generatie

Een goed en gemakkelijk alternatief voor de gebrekkige rand() -procedures is xorshift , een klasse van pseudo-willekeurige nummergenerators ontdekt door George Marsaglia . De xorshift-generator is een van de snelste niet-cryptografisch veilige generatoren voor willekeurige getallen. Meer informatie en andere voorbeeldimplementaties zijn beschikbaar op de xorshift Wikipedia-pagina

Voorbeeld implementatie

#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;
}