Может ли генератор случайных чисел когда-либо производить разные выходные данные при одинаковых начальных значениях?

10

Название подводит итог. Мне интересно знать, существует ли алгоритм, способный производить переменные выходные данные при одинаковом вводе, не полагаясь на другие источники случайности, такие как DateTime.Now или число, сгенерированное датчиком освещенности и т. Д. Кроме того, алгоритм не может быть запущен в последовательности, только два отличных, не связанных прогона, которые производят различный результат.

ConditionRacer
источник
То, о чем вы говорите, это генератор псевдослучайных чисел, если быть точным.
Марсель
Большинство языков допускают возможность создания генератора случайных чисел без указания начального числа, чтобы начальное число также было «случайным». Есть причина, по которой семена используются.
Нил
1
@Neil: в этих случаях все еще есть семя, это просто неявное, обычно системное время.
Майкл Боргвардт
@MichaelBorgwardt, я просто сказал, что семя также будет случайным. Конечно, ничто не является действительно случайным, но обычно системное время обеспечивает достойное начальное число, при условии, что вы не часто создаете экземпляр генератора случайных чисел без прохождения начального числа, и в этом случае вы можете получить одно и то же начальное число «случайное» начальное число дважды.
Нил
Есть интересная область исследования неточного оборудования, которое имеет статистически четкую неточность. Потенциальная выгода - более низкое потребление энергии. Простой расчет 2.0 + 2.0по такой системе не даст идентичных результатов. Ему не нужен другой источник случайности.
MSalters

Ответы:

15

Мне интересно знать, существует ли алгоритм, способный производить переменные выходные данные при одинаковом входном сигнале, не полагаясь на другие источники случайности, такие как DateTime.Now или число, генерируемое датчиком освещенности и т. Д.

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

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

Майкл Боргвардт
источник
14

Нет, алгоритм генерации псевдослучайных чисел всегда будет выдавать один и тот же результат при одном и том же начальном числе (следовательно, псевдослучайном ).

Мне интересно, что вы использовали термин «алгоритм», а не «программа». Это исключает определенный класс ответов «да» (программные ошибки в ОЗУ, различные чередования потоков в многопоточном RNG и т. Д.). Если вы принимаете как должное, что каждый прогон вашего алгоритма принимает один и тот же вход на каждой итерации, хорошо заданный без случайности, то он будет генерировать один и тот же вывод при каждом прогоне.

При этом даже такие базовые вещи, как температура процессора, достаточно непредсказуемы, чтобы действовать в качестве источника энтропии, если они нормализованы соответствующим образом. Итак, не думайте, что это подразумевает, что «криптографически безопасный» генератор случайных чисел может быть предсказан, если вы знаете, во сколько он был запущен; многие из них используют генерируемые системой энтропийные потоки.

Брайан
источник
Алгоритм был подходящим словом :) Я специально пытаюсь устранить внешние источники энтропии, ошибки памяти, порядок потоков, непредсказуемый ввод, такой как источник света и т. Д. Я думаю, что мой вопрос проистекает из моего непонимания случайных алгоритмов и, возможно, Я мог бы сделать вопрос более общим. Мне действительно интересно, возможно ли создать какую-либо функцию, которая возвращает разные результаты при одинаковом входе (включая все источники энтропии). Похоже, ответ нет
ConditionRacer
7

Знаете ли вы, что люди работают очень усердно, чтобы гарантировать, что при одном и том же семени каждый раз генерируется одна и та же последовательность случайных чисел? Это желательное свойство для таких вещей, как моделирование по методу Монте-Карло, так как это означает, что результаты полностью воспроизводимы. Если вы не укажете начальное число, будет использовано что-то вроде времени, но эта точная воспроизводимость действительно нужна.

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

Donal Fellows
источник
Да, я понимаю, что вы говорите. Я не пытаюсь реализовать что-то новое, это было любопытство поздней ночи.
ConditionRacer
1

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

TMN
источник