Романтики.Ру

Интересно узнать, какие бывают генераторы случайных (или псевдослучайных) чисел и на каких принципах они работают. Я пока такие генераторы:
1) Набрать большой массив случайных чисел и перебирать их от первого к последнему, потом снова первое и т.д. Недостаток – эти случайные числа будут повторяться, т.е. это скорее псевдослучайные числа.
Может быть, можно придумать какой-то сложный алгоритм типа перескока по индексам в зависимости от текущего числа, но по-моему это ничего принципиально не измерит и не улучшит.
В данном случае это пример детерминированного ГПСЧ. Как я понял, алгоритм линейного конгруэнтного генератора – это не ГСЧ, а детерминированный ГПСЧ, т.е. разновидность того же самого.

2) Рассчитывать десятичное разложение числа Pi до любого знака. Недостаток – чем дальше считать, тем больше компьютерных ресурсов будет на это требоваться. Мне интересно, по какой формуле будет происходить падение производительности в зависимости от номера цифры, причём в двух вариантах – на классическом компьютере и на квантовом.
В Вики вроде этого ГСЧ нет. Считается что последовательность десятичного разложения Pi абсолютно случайна, значит если считать это число неопределённо далеко, получится настоящий ГСЧ (а не ГПСЧ) – у которого есть недостаток, что он со временем работает всё медленнее и медленнее. Но может быть, на квантовом компьютере это не будет актуальной проблемой?

3) ГСЧ с источником энтропии – это в данном случае мне не очень интересно: конечно, легко получить настоящее случайное число, подкинув монетку, но в данной теме я предлагаю обсуждать чисто математические ГПСЧ. Может ли в мире математики родиться хаос?

4) Я слышал, недавно появились какие-то ГСЧ или ГПСЧ на основе клеточных автоматов, что это такое?

Давным давно я написал генератор на Pi и он работал абсолютно случайно! Тестировал на выводе звезного неба, и если обычные генераторы повторяли небо через некоторое время, то этот за несколько часов не разу не повторился ( специально сидел и как ... ждал ). Падения скорости не заметил - может это Вы алгоритм не правильный какой взяли? подробностей не помню, но поищите. Делал еще на БК-0010, а он похоже работал медленее любого современного калькулятора.

Мне ещё интересен такой вопрос. Как я понял, что для ГПСЧ важно, чтобы он генерировал действительно "почти случайные" числа, иначе могут быть проблемы; где-то был пример, как расчёт методом молекулярной динамики дал неправильные результаты из-за того, что ГПСЧ оказался недостаточно хорош. У меня ощущение, что этот факт так же много значит, как факт эффективности математики в естественных науках.
Предположим, мы используем такой ГПСЧ: взяли случайное 10-значное число, т.е. 10 случайных цифр от 0 до 9, и перебираем их от первого к последнему, потом снова первое и т.д. Мне трудно представить, что такой ГПСЧ будет стабильно вызывать ошибки в расчётах молекулярной динамики, но это ведь действительно так?

На сколько я помню ( но доказать не могу) генератор Pi самый псевдослучайный из всех.