генерирование случайного числа в диапазоне от 0 до n, где n может быть> RAND_MAX

Question

Как создать случайное число в диапазоне от 0 до n, где n может быть> RAND_MAX в c, c ++?

Спасибо.

Answer 1

разбить генерацию на две фазы, затем объединить полученные числа.

Answer 2

Случайные числа - это очень специализированный предмет, который, если вы не математик, очень легко ошибиться. Так что я бы посоветовал не создавать случайное число из нескольких источников, вы должны использовать хорошую библиотеку.

Я бы сначала посмотрел на boost :: Random

Если этого недостаточно, попробуйте эту группу sci.crypt.random-numbers Задайте вопрос там, где они смогут помочь.

Answer 3

предположим, что вы хотите сгенерировать 64-битное случайное число, вы можете сделать это:

uint64_t n = 0;
for(int i = 0; i < 8; ++i) {
    uint64_t x = generate_8bit_random_num();
    n = (n << (8 * i)) | x;
}

Конечно, вы могли бы делать это также 16/32 бит за раз, но это иллюстрирует концепцию.

Как вы генерируете, что 8/16/32-битные случайные числа зависят от вас. Это может быть просто rand() & 0xff или что-то лучше, в зависимости от того, насколько вы заботитесь о случайности.

Answer 4

Предполагая, что C ++, вы пытались взглянуть на приличную библиотеку случайных чисел, например Boost.Random . В противном случае вам может потребоваться объединить несколько случайных чисел.

Answer 5

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

Конечно, в большинстве случаев вы можете просто загрузить код для чего-то вроде Mersenne Twister или (если вам нужен генератор криптографического качества) Blum-Blum-Shub и забыть о написании своего собственного.

Answer 6

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

Как минимум, вы должны убедиться, что распределение соответствует. Если вы ищете равномерное распределение целых чисел от 0 до M, и у вас есть какой-то равномерный генератор случайных чисел g() для получения выходных данных, меньших M, убедитесь, что вы не выполните одно из следующее:

• сложите k выходных данных g () вместе, пока они не станут достаточно большими ( результат будет неоднородным )
• возьмите r = g () + (g () << 16), затем вычислите r% M (<em>, если диапазон r не кратен даже M, он будет слегка взвешивать определенные значения в диапазоне больше, чем другие, сам сдвиг влево сомнителен, если только g () не выводит диапазон от 0 до степени 2 минус 1 )

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

Read The Art of Programming vol. 2 (Кнут) и / или Численные рецепты и задавайте вопросы, пока не почувствуете себя уверенно.

Answer 7

Рассмотрим случайную переменную, которая может принимать значения {0, 1} с P(0) = P(1) = 0.5. Если вы хотите создать случайные значения от 0 до 2 путем суммирования двух независимых розыгрышей, у вас будет P(0) = 0.25, P(1) = 0.5 и P(2) = 0.25.

Поэтому используйте соответствующую библиотеку, если вас не волнует PDF-файл ГСЧ.

См. Также главу 7 в Числовые рецепты . (Это ссылка на более старую версию, но я все равно ее изучил; -)

Answer 8

Есть много способов сделать это.

Если у вас все в порядке с меньшей степенью детализации (с большей вероятностью дублирования), то что-то вроде (в псевдокоде) rand() * n / RAND_MAX будет работать для распространения значений по большему диапазону. Уловка в том, что в вашем реальном коде вам нужно избегать переполнения, либо путем приведения rand () или n к типу достаточно большого размера (например, 64-битному int, если RAND_MAX равен 0xFFFFFFFF), чтобы хранить результат умножения без переполнения, или используйте API умножения и деления (например, GNU MulDiv64 или Win32 MulDiv ), оптимизированный для этого сценария.

Если вы хотите получить гранулярность для каждого целого числа, вы можете вызвать rand () несколько раз и добавить результаты. Другой ответ предлагает вызвать rand () для каждого 8-битного / 16-битного / 32-битного блока в зависимости от размера RAND_MAX.

Но, ИМХО, вышеприведенные идеи могут быстро усложниться, неточны или и то, и другое. Генерация случайных чисел является решаемой проблемой в других библиотеках, и, вероятно, гораздо проще заимствовать существующий код (например, из Boost ), чем пытаться свернуть свой собственный. Алгоритм генерации случайных чисел с открытым исходным кодом в C ++? содержит ответы с большим количеством ссылок, если вы хотите что-то кроме Boost.

[РЕДАКТИРОВАТЬ: пересматривая после напряженного дня ... хотел вернуться и очистить мой быстрый ответ сегодня утром, но отстранился и вернулся только сейчас. :-)]

Answer 9

Сделайте x случайных чисел (от 0 до RAND_MAX) и сложите их вместе, где

x = n% RAND_MAX