Изобретая Колесо: Генератор Случайных Чисел - PullRequest
Новая
       61

Изобретая Колесо: Генератор Случайных Чисел

9 голосов
/ 02 мая 2011

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

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

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

Теперь я знаю, что в C ++ есть встроенные RNG, но я хочу научиться не просто копировать чужие работыи попытаться понять это.

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

Ответы [ 4 ]

5 голосов
/ 02 мая 2011

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

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

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

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

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

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

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

Я надеюсь, что вы изучаете PRNG и пробуете свои собственные (попробуйте Knuth's Art of Computer Programming или Численные рецептыстартовое место), но я просто хотел изложить все это так, чтобы в конце дня (если PRNG не будут делом вашей жизни), гораздо лучше просто использовать что-то, что придумал кто-то другой.Кроме того, я хотел бы отметить, что исторически компиляторы, электронные таблицы и т. Д. Не используют то, что большинство математиков считают хорошими PRNG, поэтому, если вам нужна высококачественная PRNG, не используйте стандартную библиотеку.в C ++, Excel, .NET, Java и т. д., пока вы не исследуете, с чем они его реализуют.

3 голосов
/ 02 мая 2011

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

Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха.1007 * Глава 3 Случайные числа книги Кнута «Искусство компьютерного программирования», которая должна быть наиболее исчерпывающим обзором предмета.И как только вы прочитаете это, вы будете измотаны.Вы также узнаете, почему вы не хотите писать собственный генератор случайных чисел.

3 голосов
/ 02 мая 2011

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

0 голосов
/ 28 июня 2011

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

  • Создать большой одномерный массив, заполненный "реальными" случайными значениями.
  • "затравить" ваш псевдослучайный генератор путем вычисленияначальный индекс с системным временем.
  • Итерация по массиву и возврат значения для каждого вызова вашей функции.
  • Обтекание, когда оно достигает конца.
...