Блог

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

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

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

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

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

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

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

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 строк кода с нуля требует больших умственных усилий и изучения PRNGS. Обычно самые известные алгоритмы разрабатываются профессором или профессионалом отрасли, который десятилетиями изучал PRNGS.

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

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

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

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

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

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

• Создайте большой одномерный массив, заполненный «реальными» случайными значениями.
• «затравите» ваш псевдослучайный генератор, вычисляя начальный индекс с учетом системного времени.
• Выполните итерацию по массиву и возвращайте значение для каждого вызова вашей функции.
• Завершите, когда он дойдет до конца.