C Language
Generowanie liczb losowych

Uwagi

Podstawowe generowanie liczb losowych

Funkcja rand() może być użyta do wygenerowania pseudolosowej liczby całkowitej z zakresu od 0 do RAND_MAX ( RAND_MAX 0 i RAND_MAX ).

srand(int) służy do inicjowania generatora liczb pseudolosowych. Za każdym razem, gdy rand() jest inicjowany z tym samym ziarnem, musi generować tę samą sekwencję wartości. Powinien zostać zaszczepiony tylko raz przed wywołaniem rand() . Nie należy go ponownie wysiać ani ponownie wysyłać za każdym razem, gdy chcesz wygenerować nową partię liczb pseudolosowych.

Standardową praktyką jest wykorzystanie wyniku time(NULL) jako nasionka. Jeśli generator liczb losowych wymaga sekwencji deterministycznej, możesz zaszczepić generator tą samą wartością przy każdym uruchomieniu programu. Zasadniczo nie jest to wymagane w przypadku kodu wersji, ale jest użyteczne w uruchomieniach debugowania, aby umożliwić powtarzalność błędów.

Zaleca się, aby zawsze zaszczepić generator, jeśli nie zostanie zaszczepiony, zachowuje się tak, jakby został zaszczepiony przez 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;
}

Możliwe wyjście:

Random value between [0, 2147483647]: 823321433

Uwagi:

Standard C nie gwarantuje jakości losowej sekwencji. W przeszłości niektóre implementacje rand() miały poważne problemy z rozkładem i losowością generowanych liczb. Użycie rand() nie jest zalecane do poważnych potrzeb generowania liczb losowych, takich jak kryptografia.

Permutowany przystający generator

Oto samodzielny generator liczb losowych, który nie opiera się na rand() ani podobnych funkcjach biblioteki.

Dlaczego miałbyś chcieć czegoś takiego? Może nie ufasz wbudowanemu generatorowi liczb losowych na swojej platformie, a może chcesz odtwarzalnego źródła losowości niezależnego od konkretnej implementacji biblioteki.

Ten kod to PCG32 z pcg-random.org , nowoczesnego, szybkiego, ogólnego przeznaczenia RNG o doskonałych właściwościach statystycznych. Nie jest kryptograficznie bezpieczny, więc nie używaj go do kryptografii.

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

A oto jak to nazwać:

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

Ogranicz generowanie do określonego zakresu

Zwykle przy generowaniu liczb losowych przydatne jest generowanie liczb całkowitych w zakresie lub wartości ap między 0,0 a 1,0. Podczas gdy można zastosować operację modułu w celu zmniejszenia liczby nasion do niskiej liczby całkowitej, wykorzystuje się małe bity, które często przechodzą przez krótki cykl, co powoduje niewielkie wypaczenie rozkładu, jeśli N jest duże w stosunku do RAND_MAX.

Makro

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

daje wartość ap w zakresie od 0,0 do 1,0 - epsilon, więc

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

ustawi i na jednolitą liczbę losową w zakresie od 0 do N - 1.

Niestety istnieje wada techniczna polegająca na tym, że RAND_MAX może być większy niż zmienna typu double może dokładnie reprezentować. Oznacza to, że RAND_MAX + 1.0 przekształca się w RAND_MAX, a funkcja czasami zwraca jedność. Jest to jednak mało prawdopodobne.

Generacja Xorshift

Dobrą i łatwą alternatywą dla wadliwych procedur rand() jest xorshift , klasa generatorów liczb pseudolosowych odkryta przez George'a Marsaglia . Generator xorshift jest jednym z najszybszych niechronionych kryptograficznie generatorów liczb losowych. Więcej informacji i inne przykładowe implementacje są dostępne na stronie Wikipedii xorshift

Przykładowa implementacja

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