Не следует использовать rand(), потому что во многих реализациях стандартных библиотек С он довольно слабый.Он вернет псевдослучайное число от 0 до RAND_MAX включительно, но RAND_MAX часто относительно мало;например, 32767.
Использование оператора modulo для получения диапазона целых чисел проблематично, если диапазон является большой долей диапазона значений, которые может возвращать функция генератора, поскольку распределение не является точно равномерным.
Например, скажем, RAND_MAX - это 59999, и мы использовали rand() % 40000.Вероятность того, что результат будет между 0 и 19999, составляет 67%, но только 33% между 20000 и 39999. Это потому, что rand() дает значение в [0,19999] с вероятностью 1/3, [20000,39999]с вероятностью 1/3 и [40000..59999] с вероятностью 1/3;но эта последняя треть сгибается назад, так что она дает [0,19999] после операции по модулю!
Для небольших диапазонов смещение не так заметно.
Лично мне нравится генерировать достаточно случайныхбиты для охвата желаемого диапазона, затем используйте метод исключения, чтобы выбрать значение.
Если нам нужно использовать rand(), мы можем использовать следующую вспомогательную функцию, чтобы сгенерировать псевдослучайное число, диапазон которого по крайней мере atleast (но может быть больше; т.е. может возвращать большее значение):
#include <inttypes.h>
static inline uint64_t rand_atleast(uint64_t atleast)
{
uint64_t result = 0;
do {
result = ((uint64_t)RAND_MAX + 1) * result + (uint64_t)rand();
atleast /= ((uint64_t)RAND_MAX + 1);
} while (atleast > 0);
return result;
}
Чтобы использовать метод исключения для создания int s в желаемом диапазоне, мы можем использовать структуру для хранениявещи, которые нам нужны, вспомогательная функция для инициализации этого диапазона (для описания некоторого определенного диапазона целых чисел) и другая вспомогательная функция для генерации целых чисел в этом диапазоне:
struct range_spec {
uint64_t mask;
uint64_t limit;
int base;
};
static inline void set_range(struct range_spec *spec,
int minimum, int maximum)
{
uint64_t mask;
int base;
if (minimum <= maximum) {
base = minimum;
mask = maximum - minimum;
} else {
base = maximum;
mask = minimum - maximum;
}
spec->base = base;
spec->limit = mask;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
mask |= mask >> 32;
spec->mask = mask;
}
static inline int rand_range(const struct range_spec *spec)
{
const uint64_t mask = spec->mask;
const uint64_t limit = spec->limit;
uint64_t result;
do {
result = rand_atleast(mask) & mask;
} while (result > limit);
return spec->base + result;
}
Тем не менее, это большая работа дляполучить довольно плохие псевдослучайные числа: по моему мнению, оно того не стоит.
Я обычно использую вместо него Xorshift64 *.Он быстрый, довольно случайный (см. мой расширенный комментарий ) и очень прост в реализации.
По сути, вы можете использовать небольшой заголовочный файл, скажем rng64.h:
#ifndef RNG64_H
#define RNG64_H
#include <inttypes.h>
#include <time.h>
typedef struct {
uint64_t limit;
int64_t base;
int shift;
} rng64_intrange_spec;
static uint64_t rng64_state = 1;
static inline uint64_t rng64(void)
{
uint64_t x = rng64_state;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
rng64_state = x;
return x * UINT64_C(2685821657736338717);
}
static inline uint64_t rng64_randomize(void)
{
uint64_t x;
int n = 1000;
x = ((uint64_t)time(NULL) * UINT64_C(19076794157513))
^ ((uint64_t)clock() * UINT64_C(809712647));
if (!x)
x = 1;
while (n-->0) {
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
}
rng64_state = x;
return x;
}
static inline double rng64_one(void)
{
return (double)rng64() / 18446744073709551616.0;
}
static inline int64_t rng64_intrange(rng64_intrange_spec *spec)
{
const uint64_t limit = spec->limit;
const int shift = spec->shift;
uint64_t value;
do {
value = rng64() >> shift;
} while (value > limit);
return spec->base + value;
}
static inline void rng64_set_intrange(rng64_intrange_spec *spec,
int64_t minimum,
int64_t maximum)
{
int64_t base;
uint64_t limit;
int bits = 0;
if (minimum <= maximum) {
base = minimum;
limit = maximum - minimum;
} else {
base = maximum;
limit = minimum - maximum;
}
spec->base = base;
spec->limit = limit;
while (limit >= 32768) {
limit >>= 16;
bits += 16;
}
while (limit >= 8) {
limit >>= 4;
bits += 4;
}
while (limit > 0) {
limit >>= 1;
bits += 1;
}
spec->shift = 64 - bits;
}
#endif /* RNG64_H */
Где-то в начале вашей программы, вызовите rng64_randomize(), чтобы сгенерировать состояние, основанное на текущем времени (настенные часы через time() и время ЦП, используемое для выполнения текущегопроцесс через clock()).Начальное состояние немного изменено, чтобы вы не получили схожие последовательности при быстром выполнении кода.Вы можете установить rng64_state на любое значение, кроме нуля, для генерации определенной последовательности.(Нулевое состояние будет генерировать только нули.) Я рекомендую использовать
printf("Using %" PRIu64 " as the Xorshift64* random number seed.\n", rng64_randomize());
, который печатает как начальное число, так и используемый алгоритм генератора псевдослучайных чисел, в начале программы.Это позволяет кому-то воспроизвести тест (установив rng64_state на это значение вместо вызова rng64_randomize() или переопределив тест, используя собственный эквивалентный код).Воспроизводимость хорошая.
Хотя (uint64_t)time(NULL) не гарантирует работу по стандарту C, он работает во всех современных широко используемых реализациях C, о которых мне известно.
Если вы хотите сравнить с другимгенератор псевдослучайных чисел, просто переопределите другой, используя аналогичный заголовочный файл, и включите его вместо этого.Таким образом, вам не нужно менять код, использующий генератор, только сам код генератора.
rng_one() возвращает одинаковые псевдослучайные числа в диапазоне от 0 до 1,0 включительно.Если вы хотите, чтобы верхний предел был исключительным, используйте, например,
static inline double rng64_one(void)
{
double r;
do {
r = (double)rng64() / 18446744073709551616.0;
} while (r >= 1.0);
return r;
}
, а если оба ограничения исключительны (поэтому он никогда не возвращает 0,0 или 1,0 точно), вместо этого while (r <= 0.0 || r >= 1.0);.
ВотПример использования rng64.h выше:
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
#include <stdio.h>
#include "rng64.h"
int main(int argc, char *argv[])
{
rng64_intrange_spec r;
int minval, maxval, count, i;
char dummy;
if (argc != 4 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
fprintf(stderr, " %s MIN MAX COUNT\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program outputs COUNT pseudorandom integers,\n");
fprintf(stderr, "between MIN and MAX, inclusive.\n");
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &minval, &dummy) != 1) {
fprintf(stderr, "%s: Invalid minimum.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %d %c", &maxval, &dummy) != 1 || maxval < minval) {
fprintf(stderr, "%s: Invalid maximum.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %d %c", &count, &dummy) != 1 || count < 0) {
fprintf(stderr, "%s: Invalid count.\n", argv[3]);
return EXIT_FAILURE;
}
fprintf(stderr, "Generating %d pseudorandom integers in [%d, %d],\n", count, minval, maxval);
fprintf(stderr, "using Xorshift64* with seed %" PRIu64 ".\n", rng64_randomize());
fflush(stderr);
rng64_set_intrange(&r, minval, maxval);
for (i = 0; i < count; i++)
printf("%d\n", (int)rng64_intrange(&r));
return EXIT_SUCCESS;
}
Укажите минимальные и максимальные значения (целые числа) и количество целых чисел для вывода в качестве параметров командной строки.