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

Question

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

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

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

Answer 1

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

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

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

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

и никогда ничем напоминает

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

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

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

Answer 2

Boost Random Number Library

Answer 3

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

Answer 4

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

Я бы заглянул в boost random number library.

Answer 5

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

Answer 6

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

Answer 7

Быстрая вещь, которая может заставить ваши номера чувствовать себя более случайными, заключается в повторном посеве генератора каждый раз, когда условие if(rand() % 50==0) истинно.

Answer 8

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

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

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

Answer 9

Люди говорят, что младшие разряды не случайны. Так что попробуйте что-нибудь посредине.Это даст вам 28-й бит:

(rand() >> 13) % 2 

Answer 10

Кнут предлагает случайное число поколение методом вычитания. Считается, что он довольно рвадом. Для примера реализации на языке Схемы см. here

Answer 11

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

Что хорошего алгоритма является то, что:

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

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

Answer 12

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

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

х_{п + 1 =}х_н & Мидот; 214013 + 2531011

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

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

Answer 13

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

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

Answer 14

C++ 11 имеет следующий способ реализации Mersenne tittie twister algorothm. От 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'; 
} 

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

Существует также алгоритм Well equidistributed long-period linear; с множеством примеров реализации.