Я пытался решить проблему хобби, которая требовала генерации миллиона случайных чисел. Но я быстро понял, что становится сложно сделать их уникальными. Я взял Руководство по разработке алгоритмов, чтобы прочитать о генерации случайных чисел.
У него есть следующий абзац, который я полностью не в состоянии понять.
К сожалению, генерация случайных чисел выглядит намного проще, чем есть на самом деле. Действительно, на самом деле невозможно произвести действительно случайные числа на любом детерминированном устройстве. Фон Нейман [Neu63] сказал это лучше всего: «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Лучшее, на что мы можем надеяться, это псевдослучайные числа, поток чисел, который выглядит как если они были созданы случайным образом.
Почему невозможно создать действительно случайные числа в любом детерминированном устройстве? Что означает это предложение?
источник
Ответы:
Нужно искать криптографически безопасный генератор псевдослучайных чисел . Большинство PRNG являются генераторами линейной конгруэнции (
next number
как и линейная функцияprevious number
), поэтому, если выnext number
строите график против,previous number
вы получите график параллельных линий. CSPRNG не будет этого делать. Компромисс в том, что они медленные.Я группирую генераторы случайных чисел на 3 категории :
Детерминированное устройство всегда будет выдавать один и тот же выходной сигнал при одинаковых начальных условиях и входных данных - вот что значит быть
deterministic
. «Поистине случайное число» - это скорее философская точка зрения, поскольку смыслrandom
философского пупка в том, что он означает (люди даже не уверены, является ли атомный распад случайным или следует некоторому шаблону, который мы просто не можем понять все же). Криптографически безопасный генератор случайных чисел собирается использовать некоторый внешний источник энтропии, чтобы сделать устройство недетерминированным.источник
Истинная случайность подразумевает недетерминизм. Если это детерминистический, он может быть точно предсказан (это то, что означает детерминизм); если это можно предсказать, это не случайно.
Лучшее, что вы можете получить от детерминированного генератора псевдослучайных чисел, - это поток чисел с очень длинным циклом (неповторение невозможно, если ваше устройство RNG не имеет неограниченного хранилища), которое на протяжении цикла производит номера потоков, соответствующие всем другим свойствам случайной последовательности (наиболее интересным является равномерное распределение значений).
Чтобы решить эту проблему, многие современные UNIX и Unix-подобные имеют ядра RNG, которые используют физические источники шума для генерации истинной случайности.
Другой распространенный подход - взять текущее время в качестве начального числа для детерминированного ГСЧ (
srand(time(NULL));
на С); Криптографически говоря, это бесполезно, так как текущее время не секрет, но для таких вещей, как физическое моделирование или видеоигры, это достаточно хорошо.источник
Вторая глава книги « Моделирование дискретных событий: первый курс » Лоуренса Лимиса дает фантастическое введение в генераторы случайных чисел (или, точнее, генераторы псевдослучайных чисел).
Отрывок из его книги хорошо объясняет это, на мой взгляд:
Таким образом, хотя можно использовать генератор белого шума для получения «лучших» случайных чисел, они не получили признания, поскольку они не соответствуют большинству критериев, приведенных выше.
Я бы порекомендовал вам взять в руки копию этой книги (или что-то подобное). Понимание того, как именно работа PRNG определенно поможет вам в ваших усилиях.
источник
Потому что Вам нужно код записи , чтобы генерирует случайные числа и код является НЕ случаен. (Это детерминировано)
Таким образом, вы начинаете со значения «Seed value (s)», которое выбирается как «Random» (обычно текущая отметка времени), а затем используете его в алгоритме, чтобы начать генерировать числа. Но весь набор основан на оригинальной стоимости Seed!
Так что, если вы снова запустите свой код с точно такими же значениями Seed, вы получите ТОЧНЫЙ набор данных! Как любой разумный человек может назвать это случайным? Но он уверен , делает LOOK случайным.
Что касается того, чтобы сделать их уникальными, после генерации номера просто проверьте, есть ли у вас этот номер, если он есть, выбросьте его и сгенерируйте новый.
источник
Поскольку вы генерируете случайные числа, вы должны ожидать, что сгенерированные значения будут неуникальными. Это свойство случайности - вы не можете сказать, что последовательность действительно случайных (или даже псевдослучайных) чисел уникальна, потому что это требование позволило бы предсказать окончательное значение в диапазоне, а также изменить вероятность все невыбранные номера каждый раз, когда выбирается новый.
источник
У меня есть очень простое определение псевдослучайного :
Слишком много неизвестных переменных для прогнозирования.
У меня также есть простое определение True Random :
Бесконечные неизвестные переменные.
Проблема с компьютером в том, что он всегда знает ВСЕ переменные. Случайное число - это просто математическая функция некоторого начального значения .
Лучшее, что мы можем сделать, - это дать компьютеру псевдослучайное начальное значение, которое обычно основывается на переменной, которую мы не можем предсказать (например, точное время).
Даже если компьютер абсолютно не может создать случайное число, он хорош для того, чтобы вводить слишком много переменных для предсказания!
источник
Генерация действительно случайных чисел в программном обеспечении действительно невозможна, как отмечали другие, однако с помощью оборудования можно создать устройство, которое может генерировать действительно случайные числа *. В Интернете есть немало примеров этого, и используются различные методы: от считывания времени между тиками на счетчике Гейгера до выборки белого шума (в основном фонового излучения из вселенной) ненастроенного приемника. Я сам построил несколько, используя несколько доступных методов.
* Любой хороший физик-фанат укажет, что, учитывая то, как работает Вселенная, ни один из них не является гипер-технически истинно случайным, но нет никакого разумного способа предсказать результаты, поэтому ради этого обсуждения они достаточны.
источник
Невозможно произвести случайное число без специального оборудования. На первом курсе пара одноклассников и я предложили генератор случайных чисел, который имеет в основном AM-приемник и настроен на 4 разных канала, получает входной сигнал в аналого-цифровой преобразователь и добавляет их все (по модулю вашего максимального числа). Поскольку комбинация аналогового ввода с любого произвольного числа станций является случайной, и мы можем получить большое количество случайных чисел из A2D-преобразователя, мы предложили, что это может быть хорошим генератором. Конечно, даже это не является действительно случайным в философском смысле, хотя для большинства практических целей это может сработать.
источник
Детерминизм по сути является функцией. Из алгебры помните, что функция - это соответствие между доменом и диапазоном, так что каждый член домена соответствует ровно одному члену диапазона.
Поэтому, если f (x) = z, f (x)! = Y, если y не равно z. Это функция. Представьте себе JavaScript:
Независимо от того, сколько раз вы вызываете,
Add(2,3)
он всегда вернет 5. Другими словами, Add () является детерминированной функцией.Внешние факторы могут заставить Add вести себя недетерминированным образом. Например, если вы введете многопоточность в уравнение. Вклад человека также вызывает недетерминизм.
Теперь здесь все становится интересно.
Заметьте, что фон Нейман утверждает, что «арифметические методы получения [...]». Речь не идет о человеческом входе, параллельности, выборочных скоростях ветра, считываемых с точного прибора, или о других неалгоритмических способах получения случайного ввода для детерминированной функции.
Это просто говорит о том, что функция или система функций не станет внезапно недетерминированной. Другими словами, Add (2,3) не будет каким-либо образом возвращать 6 или что-либо, кроме 5, при тех же входных данных . Это невозможно.
Автор цитирования делает еще один шаг вперед.
Контекст предварительно определен как «на любом детерминированном устройстве». Я мог бы закончить спор здесь. Но что, если мы изменим контекст, введя новый элемент в систему? Недетерминированный элемент, добавленный в качестве входных данных, делает систему недетерминированной системой. Хотя, удаляя недетерминированный элемент, мы возвращаемся к детерминированной системе. Если мы можем каким-то образом отследить или иным образом воспроизвести входные данные, мы можем воспроизвести результат. Но весь этот абзац тангениален тому, что говорит автор. Помните контекст.
Можно спорить о значении недетерминизма. Еще раз загар. Помните контекст.
Так что он прав. На любом детерминированном устройстве для детерминированной системы невозможно получить истинный случайный результат.
источник