C Language
Генерация случайных чисел

замечания

Генерация случайных чисел

Функция rand() может использоваться для генерации псевдослучайного целочисленного значения между 0 и RAND_MAX ( RAND_MAX 0 и RAND_MAX ).

srand(int) используется для подсчета генератора псевдослучайных чисел. Каждый раз, когда rand() засевается одним и тем же семенем, он должен вызывать одну и ту же последовательность значений. Он должен быть посеян только один раз перед вызовом rand() . Его не следует многократно посеять или пересаживать каждый раз, когда вы хотите создать новую партию псевдослучайных чисел.

Стандартная практика заключается в использовании результата time(NULL) в качестве семени. Если генератор случайных чисел требует детерминированной последовательности, вы можете засеять генератор с тем же значением при каждом запуске программы. Обычно это не требуется для кода выпуска, но полезно в отладочных запусках, чтобы сделать ошибки воспроизводимыми.

Рекомендуется всегда засевать генератор, если он не посеян, он ведет себя так, как если бы он был засеян с помощью 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;
}

Возможный выход:

Random value between [0, 2147483647]: 823321433

Заметки:

Стандарт C не гарантирует качество созданной случайной последовательности. Раньше некоторые реализации rand() имели серьезные проблемы в распределении и случайности генерируемых чисел. Использование rand() не рекомендуется для серьезных потребностей генерации случайных чисел, таких как криптография.

Преобразованный конгруэнтный генератор

Вот автономный генератор случайных чисел, который не полагается на функции rand() или аналогичные библиотеки.

Зачем вам это нужно? Возможно, вы не доверяете встроенному генератору случайных чисел вашей платформы, или, возможно, вам нужен воспроизводимый источник случайности, не зависящий от какой-либо конкретной реализации библиотеки.

Этот код является PCG32 от pcg-random.org , современного, быстрого, универсального RNG с отличными статистическими свойствами. Это не криптографически безопасно, поэтому не используйте его для криптографии.

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

И вот как это назвать:

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

Ограничить генерацию до заданного диапазона

Обычно при генерации случайных чисел полезно генерировать целые числа в пределах диапазона или значение ap между 0.0 и 1.0. В то время как операция модуляции может использоваться для уменьшения количества семян до низкого целого, это использует низкие биты, которые часто проходят короткий цикл, что приводит к небольшому перекосу распределения, если N велико пропорционально RAND_MAX.

Макрос

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

дает значение ap от 0,0 до 1,0 - epsilon, поэтому

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

будет устанавливать i равномерное случайное число в диапазоне от 0 до N - 1.

К сожалению, существует технический недостаток, поскольку RAND_MAX разрешено быть большим, чем переменная типа double может точно представлять. Это означает, что RAND_MAX + 1.0 оценивается как RAND_MAX, и функция иногда возвращает единицу. Однако это маловероятно.

Поколение Xorshift

Хорошей и простой альтернативой ошибочным процедурам rand() является xorshift , класс генераторов псевдослучайных чисел, открытых Джорджем Марсалья . Генератор xorshift является одним из самых быстрых некриптографически безопасных генераторов случайных чисел. Более подробная информация и другие примеры реализации доступны на странице Wikipedia xorshift

Пример реализации

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