Новое изобретение колеса: генератор случайных чисел

Итак, я новичок в C++ и пытаюсь кое-что узнать. Таким образом, я пытаюсь создать генератор случайных чисел (RNG или PRNG, если хотите). У меня есть базовые знания о ГСЧ, например, вы должны начать с начального числа, а затем отправить начальное число через алгоритм. На чем я застрял, так это на том, как люди придумывают указанные алгоритмы.

Вот код, который мне нужно получить.

int getSeed()
{
    time_t randSeed;
    randSeed = time(NULL);
    return randSeed;
}

Теперь я знаю, что в С++ есть готовые ГСЧ, но я хочу научиться не просто копировать работу других людей и пытаться понять это.

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


c++ random algorithm seed numbers
person Cistoran    schedule 01.05.2011    source источник
comment
Вы читали эту статью? gnu.org/software/gsl/manual/html_node/   -  person Seth Carnegie    schedule 02.05.2011
comment
Дизайн PRNG не зависит от языка и больше связан с теорией чисел и алгеброй, чем с программированием. Если ваша цель — изучить C++ на нескольких примерах, вам следует поискать что-то другое. Если вы хотите понять дизайн PRNG, вы должны удалить части, в которых упоминается C++.   -  person blubb    schedule 02.05.2011
comment
@ Сет Карнеги Я прочитал эту статью, но я не мог понять, что она пытается сказать.   -  person Cistoran    schedule 02.05.2011
comment
@Simon Stelling Ну, это работает в обоих направлениях, я думаю, я должен был упомянуть об этом в первом посте. Я пытаюсь изучить не только C++, но и концепции базового программирования. Генерация случайных чисел является одной из этих основных концепций.   -  person Cistoran    schedule 02.05.2011
comment
@Cistoran: Понимание того, что делает хороший ГСЧ, требует больших знаний математики; статистика, теория чисел, теория групп и т. д. (большинство из которых выходит за рамки моих знаний и терпения). Это не то, чем я бы порекомендовал вам случайно заняться. Есть гораздо больше полезных вещей, которым нужно научиться, учитывая, что, как вы говорите, это было бы изобретением велосипеда.   -  person Oliver Charlesworth    schedule 02.05.2011
comment
Вы читали страницу Википедии на эту тему?   -  person fredoverflow    schedule 02.05.2011
comment
@Oli Charlesworth: Дело принято, на данный момент я не ищу ничего фантастического, такого как Mersenne Twister или тому подобное, просто простой алгоритм, в который я мог бы вставить семя (как показано выше) и получить (довольно) случайное число снаружи.   -  person Cistoran    schedule 02.05.2011
comment
@FredOverflow: Да, но, как я сказал Сету, я не очень далеко продвинулся в плане образования и не могу понять, что я должен делать, когда читаю все это.   -  person Cistoran    schedule 02.05.2011
comment
как я вижу из вашего кода, вы думаете об использовании времени в качестве источника случайных данных. вы можете использовать функции в sys/time.h и выполнять любые вычисления, которые объединяют поля меток времени вместе для получения случайного числа, которое не будет равномерно распределенным числом.   -  person Ahmed Khalaf    schedule 02.05.2011
comment
Несколько человек немного обескуражили эту погоню. Я говорю давай. Какая бы область вас ни интересовала, следуйте ей. Не позволяйте людям, говорящим, что это непрактично, беспокоить вас — это может быть непрактично, но это должно быть познавательно. Случайные числа приведут вас к областям, которые многие программисты никогда не посещают — битовая игра, теория чисел, статистика — обо всем этом стоит узнать.   -  person phkahler    schedule 28.06.2011

Ответы (4)


arrow_upward
5
arrow_downward

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

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

http://www.fourmilab.ch/hotbits/

http://www.random.org/

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

http://www.lavarnd.org/

http://www.idquantique.com/true-random-number-generator/products-overview.html

http://www.araneus.fi/products-alea-eng.html

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

Некоторые рекомендации по определению того, что является хорошим PRNG, включают:

  1. Периодичность (каков диапазон доступных чисел?)
  2. Последовательные числа (какова вероятность того, что одно и то же число будет повторяться дважды подряд)
  3. Единообразие (выбирается ли число из определенного поддиапазона с такой же вероятностью, как и из другого поддиапазона)
  4. Сложность его обратного проектирования (если он близок к действительно случайному, то кто-то не сможет вычислить следующее число, которое оно сгенерирует, на основе нескольких последних сгенерированных чисел)
  5. Скорость (насколько быстро я могу сгенерировать новый номер? Требуется 5 или 500 арифметических операций)
  6. Я уверен, что есть другие, которых мне не хватает

Одним из самых популярных сейчас, который считается хорошим в большинстве приложений (т.е. не в криптографии), является Mersenne Twister< /а>. Как видно из ссылки, это простой алгоритм, возможно, всего 30 строк кода. Однако попытка придумать эти 20 или 30 строк кода с нуля требует большого ума и изучения PRNG. Обычно самые известные алгоритмы разрабатываются профессором или профессионалом отрасли, который десятилетиями изучал PRNG.

Я надеюсь, что вы изучите ГПСЧ и попробуете создать свой собственный (попробуйте для начала «Искусство компьютерного программирования» или «Численные рецепты») Кнута, но я просто хотел изложить все это, чтобы в конце дня (если только ГПСЧ не станут вашими работа всей жизни) гораздо лучше просто использовать то, что придумал кто-то другой. Кроме того, я хотел бы отметить, что исторически компиляторы, электронные таблицы и т. д. не используют то, что большинство математиков считают хорошими ГПСЧ, поэтому, если вам нужны высококачественные ГПСЧ, не используйте стандартную библиотеку. в C++, Excel, .NET, Java и т. д., пока вы не изучите, с чем они это реализуют.

person Jason Moore    schedule 02.05.2011
comment
Re Сложность обратного проектирования: это проблема для криптографически безопасных PRNG, но не для PRNG в целом. Типичное использование PRNG — это добавление случайности в компьютерную игру или в симуляцию Монте-Карло. Здесь нет необходимости в безопасном PRNG для таких приложений. OTOH, если вы используете PRNG для шифрования сообщения или цифровой подписи, то на первый план выходят опасения по поводу обратного проектирования. - person David Hammen; 28.06.2011

arrow_upward
3
arrow_downward

Обычно используется линейный конгруэнтный генератор, и в Вики-статье он довольно хорошо объясняется.

person Jacob    schedule 01.05.2011
comment
Не совсем. В частности, в нем говорится, что наиболее эффективные LCG имеют m, равное степени 2, чаще всего m = 2 ^ 32 или m = 2 ^ 64. Было доказано, что вы не можете получить хороший генератор, когда m является степенью двойки; m должно быть простым. Справочник по линейным конгруэнтным генераторам: «Генераторы случайных чисел: хорошие генераторы найти трудно», Парк и Миллер, CACM, октябрь 1988 г. - person James Kanze; 02.05.2011
comment
@James Самое замечательное в Википедии то, что такие пользователи, как вы, могут редактировать и улучшать ее. Также обратите внимание, что здесь написано «эффективно», а не «хорошо». Если вам нужен хороший PRNG, вам вообще не следует использовать LCG. - person Nick Johnson; 02.05.2011

arrow_upward
3
arrow_downward

Цитируя Джона фон Неймана:

Всякий, кто рассматривает арифметические методы получения случайных чисел, конечно, в состоянии греха.

Это взято из главы 3 "Случайные числа" книги Кнута "Искусство компьютерного программирования", которая должна быть наиболее исчерпывающим обзором предмета. И как только вы это прочитаете, вы будете измотаны. Вы также узнаете, почему не хотите писать свой собственный генератор случайных чисел.

person Community    schedule 01.05.2011

arrow_upward
0
arrow_downward

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

  • Создайте большой одномерный массив, заполненный «настоящими» случайными значениями.
  • «запустите» ваш генератор псевдослучайных чисел, рассчитав начальный индекс с системным временем.
  • Перебирайте массив и возвращайте значение для каждого вызова вашей функции.
  • Оберните вокруг, когда он достигнет конца.
person Martin    schedule 28.06.2011