Лучший случайный алгоритм?

Question

Я делаю игру на C ++, и она включает в себя заполнение тайлов случайными логическими значениями (да или нет), независимо от того, "да" или нет, определяется rand() % 1 Это не кажется очень случайным.

Я использую srand с ctime при запуске, но похоже, что появляются те же шаблоны.

Существуют ли алгоритмы, которые будут создавать очень случайные числа? Или какие-либо предложения о том, как я мог бы улучшить rand()?

Answer 1

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

Но по крайней мере одна непосредственная вещь, которую вы можете сделать, - это избегать использования бита самого младшего порядка. Цитировать числовые рецепты в C:

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

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

и никогда ничем не напоминающим

j = 1 + (rand() % 10);

(который использует младшие биты).

Кроме того, вы можете рассмотреть возможность использования другой ГСЧ с лучшими свойствами. Алгоритм Xorshift является хорошей альтернативой. Он быстрый и компактный всего за несколько строк кода C, и статистически должен быть достаточно хорош практически для любой игры.

Answer 2

Младшие биты не очень случайны.
Используя% 2, вы проверяете только нижний бит случайного числа.

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

bool  tile = rand() > (RAND_MAX / 2);

Answer 3

Самое простое, что вы можете сделать, кроме написания другого PRNG или использования библиотеки, - это просто использовать все биты, которые дает вам один вызов rand(). Большинство генераторов случайных чисел можно разбить на поток битов, который имеет определенные случайные и статистические свойства. Отдельные биты, расположенные равномерно в этом потоке, не обязательно должны иметь одинаковые свойства. По сути, вы отбрасываете от 14 до 31 бита псевдослучайности здесь.

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

x _{n + 1} = x _n & middot; 214013 + 2531011

, а затем сдвигает 16 младших битов этого результата и ограничивает его 15 битами. Так что никаких младших битов от генератора нет. Это в основном справедливо для генераторов, где RAND_MAX достигает 2 ³¹ , но иногда вы не можете рассчитывать на это (поэтому, возможно, ограничитесь 16 или 24 битами, взятыми из старшего уровня) ).

Так, обычно, просто кешируйте результат вызова rand() и используйте биты этого числа последовательно для вашего приложения вместо rand() % 2.

Answer 4

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

Answer 5

Я успешно использовал генератор случайных чисел Мерсенна Твистера в течение многих лет. Его исходный код доступен в математическом отделе Университета Хиросимы здесь . (Прямая ссылка, чтобы вам не приходилось читать по-японски!)

Что хорошего в этом алгоритме, так это:

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

Я бы порекомендовал взглянуть на вашу игру.

Answer 6

Увеличение библиотеки случайных чисел

Answer 7

C ++ 11 имеет следующий способ реализации алгоритма сисечки Мерсенна. От cppreference.com :

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

Это дает случайные числа, пригодные для моделирования, без недостатков многих других генераторов случайных чисел. Это не подходит для криптографии; но криптографические генераторы случайных чисел требуют больших вычислительных ресурсов.

Существует также хорошо равнораспределенный длиннопериодный линейный алгоритм; со многими примерами реализации.

Answer 8

Младшие биты стандартных генераторов случайных чисел не очень случайны, это хорошо известная проблема.

Я бы заглянул в ускоренную библиотеку случайных чисел .

Answer 9

Идеальный способ Да или Нет как случайного - это переключать их. Вам может не потребоваться случайная функция.

Answer 10

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

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