Генерирование случайного целого из диапазона

Мне нужна функция, которая генерирует случайное целое число в заданном диапазоне (включая значения границ). У меня нет необоснованных требований к качеству/случайности, у меня есть четыре требования:

Мне нужно, чтобы это было быстро. Мой проект должен генерировать миллионы (или иногда даже десятки миллионов) случайных чисел, и моя текущая функция генератора оказалась узким местом.
Мне нужно, чтобы он был достаточно однородным (использование rand() отлично подходит).
диапазоны min-max могут быть любыми от < 0, 1 > до < -32727, 32727 > .
он должен быть посеянным.

В настоящее время у меня следующий код на С++:

output = min + (rand() * (int)(max - min) / RAND_MAX)

Проблема заключается в том, что она не является однородной - max возвращается только тогда, когда rand() = RAND_MAX (для Visual С++ это 1/32727). Это основная проблема для небольших диапазонов, таких как < -1, 1 > , где последнее значение почти никогда не возвращается.

Итак, я схватил ручку и бумагу и придумал следующую формулу (которая основывается на (int) (n + 0.5) целочисленном трюке округления):

Но это все равно не дает мне равномерного распределения. Повторные пробеги с 10000 отсчетами дают мне отношение 37:50:13 для значений значений -1, 0. 1.

Не могли бы вы предложить лучшую формулу? (или даже целую функцию генерации псевдослучайных чисел)

Ответ 1

Быстро, несколько лучше, чем ваше, но все еще неравномерно распределенное решение -

output = min + (rand() % static_cast<int>(max - min + 1))

За исключением случаев, когда размер диапазона равен 2, , этот метод производит смещенные неравномерные распределенные номера независимо от качества rand(). Для всестороннего теста качества этого метода, пожалуйста, прочитать это.

Ответ 2

Самый простой (и, следовательно, лучший) С++ (с использованием стандарта 2011) - это

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

Не нужно заново изобретать колесо. Не нужно беспокоиться о предвзятости. Не нужно беспокоиться об использовании времени в качестве случайного семени.

Ответ 3

Если ваш компилятор поддерживает С++ 0x, и использование этого параметра для вас, то новый стандартный заголовок <random>, скорее всего, удовлетворит ваши потребности. Он имеет высокое качество uniform_int_distribution, которое будет принимать минимальные и максимальные ограничения (включительно по мере необходимости), и вы можете выбрать среди различных генераторов случайных чисел для подключения к этому дистрибутиву.

Вот код, который генерирует миллион случайных int, равномерно распределенных в [-57, 365]. Я использовал новые средства std <chrono>, чтобы время, когда вы упомянули о производительности, является для вас серьезной проблемой.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}

Для меня (2,8 ГГц Intel Core i5) это печатает:

2.10268e + 07 случайных чисел в секунду.

Вы можете засеять генератор, передав int его конструктору:

    G g(seed);

Если позже вы обнаружите, что int не охватывает диапазон, который вам нужен для вашего распространения, это можно устранить, изменив uniform_int_distribution так (например, на long long):

    typedef std::uniform_int_distribution<long long> D;

Если позже вы обнаружите, что minstd_rand не является достаточно качественным генератором, который также можно легко поменять. Например:.

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

Имея отдельный контроль над генератором случайных чисел, и случайное распределение может быть довольно освободительным.

Я также вычислил (не показан) первые 4 "момента" этого распределения (используя minstd_rand) и сравнил их с теоретическими значениями в попытке количественно оценить качество распределения:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

(Префикс x_ относится к "ожидаемому" )

Ответ 4

Разделим задачу на две части:

Создайте случайное число n в диапазоне от 0 до (max-min).
Добавьте min к этому номеру

Первая часть, очевидно, самая сложная. Предположим, что возвращаемое значение rand() абсолютно равномерное. Использование modulo добавит смещение к первым номерам (RAND_MAX + 1) % (max-min+1). Поэтому, если бы мы могли магически изменить RAND_MAX на RAND_MAX - (RAND_MAX + 1) % (max-min+1), больше не было бы смещения.

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

Время выполнения теперь геометрически распределено с ожидаемым значением 1/p, где p - вероятность получения небольшого количества с первой попытки. Так как RAND_MAX - (RAND_MAX + 1) % (max-min+1) всегда меньше (RAND_MAX + 1) / 2, мы знаем, что p > 1/2, поэтому ожидаемое число итераций всегда будет меньше двух для любого диапазона. Должна быть возможность генерировать десятки миллионов случайных чисел менее чем за секунду на стандартном процессоре с помощью этой техники.

EDIT:

Хотя вышеописанное технически правильно, ответ DSimon, вероятно, более полезен на практике. Вы не должны реализовывать этот материал самостоятельно. Я видел много реализаций выборки отбраковки, и часто бывает очень сложно понять, правильно ли это или нет.

Ответ 5

Как насчет Mersenne Twister? Реализация ускорения довольно проста в использовании и хорошо протестирована во многих реальных приложениях. Я сам использовал его в нескольких академических проектах, таких как искусственный интеллект и эволюционные алгоритмы.

Вот их пример, где они делают простую функцию, чтобы свернуть шестигранную матрицу:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

О, и вот еще несколько сутенерств этого генератора на всякий случай, если вы не уверены, что вам следует использовать его на гораздо более низком rand():

The Mersenne Twister - это "случайный номер", изобретенный Макото Мацумото и Такуджи Нишимура; их сайт включает многочисленные реализации алгоритма.

По существу, Mersenne Twister - это очень большой сдвиг линейной обратной связи регистр. Алгоритм работает на 19 937 бит, хранящихся в 624-элементный массив 32-разрядных беззнаковых целые числа. Значение 2 ^ 19937-1 является Mersenne prime; техника для манипулирование семенем основывается на более старый алгоритм "скручивания" - следовательно имя "Мерсенн Твистер".

Апелляционный аспект Мерсенны Twister - это использование двоичных операции - в отличие от трудоемкое умножение - для генерирующие числа. Алгоритм также имеет очень длительный период, и зернистость. Это быстро и быстро эффективный для некриптографических приложений.

Ответ 6

int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

Это сопоставление целых чисел 32768 с целыми числами (nMax-nMin + 1). Отображение будет неплохим, если (nMax-nMin + 1) мало (как в вашем требовании). Обратите внимание, что если (nMax-nMin + 1) велико, сопоставление не будет работать (например, вы не можете сопоставить 32768 значений с 30000 значений с равной вероятностью). Если такие диапазоны необходимы - вы должны использовать 32-разрядный или 64-разрядный случайный источник вместо 15-разрядных rand() или игнорировать результаты rand(), которые находятся вне диапазона.

Ответ 7

Вот беспристрастная версия, которая генерирует числа в [low, high]:

int r;
do {
  r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

Если ваш диапазон достаточно мал, нет причин кэшировать правую часть сравнения в цикле do.

Ответ 8

Я рекомендую Boost.Random library, он очень подробный и хорошо документированный, позволяет явно указать, какой дистрибутив вы хотите, -криптографические сценарии на самом деле превосходят типичную реализацию библиотеки r-библиотеки.

Ответ 9

предположим, что min и max - значения int, [и] означает, что это значение, (и) означает не включать это значение, используя выше, чтобы получить правильное значение, используя С++ rand()

ссылка: for() [] определить, посетите:

https://en.wikipedia.org/wiki/Interval_(mathematics)

для функции rand и srand или RAND_MAX определите, посетите:

http://en.cppreference.com/w/cpp/numeric/random/rand

[мин, макс.]

int randNum = rand() % (max - min + 1) + min

(min, max]

int randNum = rand() % (max - min) + min + 1

[min, max)

int randNum = rand() % (max - min) + min

(min, max)

int randNum = rand() % (max - min - 1) + min + 1

Ответ 10

Следующее выражение должно быть беспристрастным, если я не ошибаюсь:

std::floor( ( max - min + 1.0 ) * rand() ) + min;

Я предполагаю здесь, что rand() дает вам случайное значение в диапазоне от 0,0 до 1,0 НЕ, включая 1.0, и что max и min являются целыми числами с условием, что min < Максимум.

Ответ 11

Формула для этого очень проста, поэтому попробуйте это выражение,

 int num = (int) rand() % (max - min) + min;  
 //Where rand() returns a random number between 0.0 and 1.0