Как сгенерировать случайное целое число из диапазона
Это продолжение ранее опубликованного вопроса:
Как сгенерировать случайное число в C?
Я хотел бы иметь возможность генерировать случайное число из определенного диапазона, например, от 1 до 6, чтобы имитировать стороны кубика.
Как бы я поступил так?
11 ответов
Все ответы пока математически неверны. возврате rand() % N не дает однозначного числа в диапазоне [0, N) если N делит длину интервала, на который rand() возвращает (т.е. является степенью 2). Кроме того, никто не знает, являются ли модули rand() независимы: возможно, что они идут 0, 1, 2, ..., который является равномерным, но не очень случайным. Единственное предположение, которое кажется разумным, состоит в том, что rand() выдает распределение Пуассона: любые два непересекающихся подинтервала одинакового размера одинаково вероятны и независимы. Для конечного набора значений это подразумевает равномерное распределение, а также гарантирует, что значения rand() красиво разбросаны.
Это означает, что единственный правильный способ изменения диапазона rand() это разделить его на коробки; например, если RAND_MAX == 11 и вы хотите диапазон 1..6, вы должны назначить {0,1} до 1, {2,3} до 2 и так далее. Это непересекающиеся интервалы одинакового размера, и поэтому они равномерно и независимо распределены.
Предложение использовать деление с плавающей точкой математически правдоподобно, но в принципе страдает от проблем округления. возможно double достаточно высокая точность, чтобы заставить его работать; возможно нет. Я не знаю, и я не хочу выяснять это; в любом случае ответ зависит от системы.
Правильный способ - использовать целочисленную арифметику. То есть вы хотите что-то вроде следующего:
#include <stdlib.h> // For random(), RAND_MAX
// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
unsigned long
// max <= RAND_MAX < ULONG_MAX, so this is okay.
num_bins = (unsigned long) max + 1,
num_rand = (unsigned long) RAND_MAX + 1,
bin_size = num_rand / num_bins,
defect = num_rand % num_bins;
long x;
do {
x = random();
}
// This is carefully written not to overflow
while (num_rand - defect <= (unsigned long)x);
// Truncated division is intentional
return x/bin_size;
}
Цикл необходим для получения идеально равномерного распределения. Например, если вам даны случайные числа от 0 до 2, и вы хотите только те от 0 до 1, вы просто продолжаете тянуть, пока не получите 2; нетрудно проверить, что это дает 0 или 1 с равной вероятностью. Этот метод также описан в ссылке, которую nos дал в своем ответе, хотя кодируется по-другому. я использую random() скорее, чем rand() как это имеет лучшее распространение (как отмечено на странице руководства для rand()).
Если вы хотите получить случайные значения за пределами диапазона по умолчанию [0, RAND_MAX], тогда вы должны сделать что-то хитрое. Возможно, наиболее целесообразно определить функцию random_extended() это тянет n биты (используя random_at_most()) и возвращается в [0, 2**n), а затем применить random_at_most() с random_extended() на месте random() (а также 2**n - 1 на месте RAND_MAX) вытащить случайное значение меньше 2**nпри условии, что у вас есть числовой тип, который может содержать такое значение. Наконец, конечно, вы можете получить значения в [min, max] с помощью min + random_at_most(max - min)в том числе отрицательные значения.
Исходя из ответа @Ryan Reich, я подумал, что предложу свою очищенную версию. Первая проверка границ не требуется, учитывая вторую проверку границ, и я сделал ее итеративной, а не рекурсивной. Возвращает значения в диапазоне [min, max], где max >= min а также 1+max-min < RAND_MAX,
unsigned int rand_interval(unsigned int min, unsigned int max)
{
int r;
const unsigned int range = 1 + max - min;
const unsigned int buckets = RAND_MAX / range;
const unsigned int limit = buckets * range;
/* Create equal size buckets all in a row, then fire randomly towards
* the buckets until you land in one of them. All buckets are equally
* likely. If you land off the end of the line of buckets, try again. */
do
{
r = rand();
} while (r >= limit);
return min + (r / buckets);
}
Вот формула, если вам известны значения max и min диапазона, и вы хотите сгенерировать числа включительно между диапазонами:
r = (rand() % (max + 1 - min)) + min
unsigned int
randr(unsigned int min, unsigned int max)
{
double scaled = (double)rand()/RAND_MAX;
return (max - min +1)*scaled + min;
}
Смотрите здесь для других вариантов.
Не могли бы вы просто сделать:
srand(time(NULL));
int r = ( rand() % 6 ) + 1;
% является оператором модуля. По сути это просто разделит на 6 и вернет остаток... от 0 до 5
Для тех, кто понимает проблему смещения, но не выдерживает непредсказуемого времени выполнения методов, основанных на отклонении, этот ряд производит постепенно уменьшающееся смещенное случайное целое число в [0, n-1] интервал:
r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...
Это достигается путем синтеза высокоточного случайного числа с фиксированной точкой i * log_2(RAND_MAX + 1) биты (где i число итераций) и выполнение длинного умножения на n,
Когда количество битов достаточно велико по сравнению с nСмещение становится неизмеримо малым.
Не имеет значения, если RAND_MAX + 1 меньше чем n (как в этом вопросе), или если это не степень двойки, но следует позаботиться о том, чтобы избежать целочисленного переполнения, если RAND_MAX * n большой.
Вот немного более простой алгоритм, чем решение Райана Райха:
/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
uint32_t range = (end - begin) + 1;
uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);
/* Imagine range-sized buckets all in a row, then fire randomly towards
* the buckets until you land in one of them. All buckets are equally
* likely. If you land off the end of the line of buckets, try again. */
uint32_t randVal = rand();
while (randVal >= limit) randVal = rand();
/// Return the position you hit in the bucket + begin as random number
return (randVal % range) + begin;
}
Example (RAND_MAX := 16, begin := 2, end := 7)
=> range := 6 (1 + end - begin)
=> limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)
The limit is always a multiple of the range,
so we can split it into range-sized buckets:
Possible-rand-output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Buckets: [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
Buckets + begin: [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]
1st call to rand() => 13
→ 13 is not in the bucket-range anymore (>= limit), while-condition is true
→ retry...
2nd call to rand() => 7
→ 7 is in the bucket-range (< limit), while-condition is false
→ Get the corresponding bucket-value 1 (randVal % range) and add begin
=> 3
Хотя Райан и прав, решение может быть намного проще, основываясь на том, что известно об источнике случайности. Чтобы переформулировать проблему:
- Есть источник случайности, выводящий целые числа в диапазоне
[0, MAX)с равномерным распределением. - Цель состоит в том, чтобы получить равномерно распределенные случайные целые числа в диапазоне
[rmin, rmax]где0 <= rmin < rmax < MAX,
По моему опыту, если количество бинов (или "блоков") значительно меньше диапазона исходных чисел, а исходный источник криптографически силен - нет необходимости проходить через все это ригамароле, и простое деление по модулю достаточно (как output = rnd.next() % (rmax+1), если rmin == 0) и производят случайные числа, которые распределены равномерно "достаточно" и без потери скорости. Ключевым фактором является источник случайности (то есть дети, не пытайтесь делать это дома с rand()).
Вот пример / доказательство того, как это работает на практике. Я хотел генерировать случайные числа от 1 до 22, имея криптографически сильный источник, который генерировал случайные байты (на основе Intel RDRAND). Результаты:
Rnd distribution test (22 boxes, numbers of entries in each box): 1: 409443 4.55% 2: 408736 4.54% 3: 408557 4.54% 4: 409125 4.55% 5: 408812 4.54% 6: 409418 4.55% 7: 408365 4.54% 8: 407992 4.53% 9: 409262 4.55% 10: 408112 4.53% 11: 409995 4.56% 12: 409810 4.55% 13: 409638 4.55% 14: 408905 4.54% 15: 408484 4.54% 16: 408211 4.54% 17: 409773 4.55% 18: 409597 4.55% 19: 409727 4.55% 20: 409062 4.55% 21: 409634 4.55% 22: 409342 4.55% total: 100.00%
Это настолько близко к униформе, сколько мне нужно для моих целей (честное выбрасывание кубиков, создание криптографически надежных кодовых книг для машин шифрования Второй мировой войны, таких как http://users.telenet.be/d.rijmenants/en/kl-7sim.htm и т. Д.). Вывод не показывает заметного смещения.
Вот источник криптографически сильного (истинного) генератора случайных чисел: Intel Digital Random Random Generator и пример кода, который генерирует 64-битные (без знака) случайные числа.
int rdrand64_step(unsigned long long int *therand)
{
unsigned long long int foo;
int cf_error_status;
asm("rdrand %%rax; \
mov $1,%%edx; \
cmovae %%rax,%%rdx; \
mov %%edx,%1; \
mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
*therand = foo;
return cf_error_status;
}
Я скомпилировал его в Mac OS X с помощью clang-6.0.1 (прямой) и с помощью gcc-4.8.3 с использованием флага "-Wa,q" (поскольку GAS не поддерживает эти новые инструкции).
Чтобы избежать смещения по модулю (предлагается в других ответах), вы всегда можете использовать:
arc4random_uniform(MAX-MIN)+MIN
Где "MAX" - верхняя граница, а "MIN" - нижняя граница. Например, для чисел от 10 до 20:
arc4random_uniform(20-10)+10
arc4random_uniform(10)+10
Простое решение и лучше, чем использование "rand() % N".
Как уже говорилось, по модулю недостаточно, потому что это искажает распределение. Вот мой код, который маскирует биты и использует их, чтобы гарантировать, что распределение не искажено.
static uint32_t randomInRange(uint32_t a,uint32_t b) {
uint32_t v;
uint32_t range;
uint32_t upper;
uint32_t lower;
uint32_t mask;
if(a == b) {
return a;
}
if(a > b) {
upper = a;
lower = b;
} else {
upper = b;
lower = a;
}
range = upper - lower;
mask = 0;
//XXX calculate range with log and mask? nah, too lazy :).
while(1) {
if(mask >= range) {
break;
}
mask = (mask << 1) | 1;
}
while(1) {
v = rand() & mask;
if(v <= range) {
return lower + v;
}
}
}
Следующий простой код позволяет взглянуть на распределение:
int main() {
unsigned long long int i;
unsigned int n = 10;
unsigned int numbers[n];
for (i = 0; i < n; i++) {
numbers[i] = 0;
}
for (i = 0 ; i < 10000000 ; i++){
uint32_t rand = random_in_range(0,n - 1);
if(rand >= n){
printf("bug: rand out of range %u\n",(unsigned int)rand);
return 1;
}
numbers[rand] += 1;
}
for(i = 0; i < n; i++) {
printf("%u: %u\n",i,numbers[i]);
}
}
Вернет число с плавающей запятой в диапазоне [0,1]:
#define rand01() (((double)random())/((double)(RAND_MAX)))