Адекватность генератора псевдослучайных чисел?

Question

[vldkr]

Здравствуйте, Хабравчане!


Буквально на днях задался вопросом какой арифметический алгоритм использовать для генератора псевдослучайных чисел (далее — ГПСЧ). В силу того, что на AVR ATmega8 нет нормально работающего ГПСЧ, а также сильного желания поглубже изучить эту тему, прошу у вас помощи.


Будьте добры, подскажите работающие «из коробки» тесты на определение близости ГПСЧ к случайным числам. Так же, если вас заинтересовала эта тема, в ближайшем будущем планирую написать статью для Хабра, и, если вы считаете, что какой-то аспект заслуживает внимания, смело пишите!


В приложении комикс на данную тему.

Answer 1

[jcmvbkbc]

работающие «из коробки» тесты на определение близости ГПСЛ к случайным числам

Dieharder

Answer 2

[gribozavr]

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

Возьмите, например, из [1] реализацию mt19937 и забудьте.

[1] llvm.org/viewvc/llvm-project/libcxx/trunk/include/random?view=markup

Comments

[vldkr]

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

[gribozavr]

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

[vldkr]

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

[gribozavr]

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

[vldkr]

Не занижайте свою самооценку. При должном желании любому человеку под силу всё. Терпение и труд всё перетрут!

[mayorovp]

Речь идет не о занижении самооценки, а о том, что ГПСЧ обладают одним нехорошим свойством — любое случайное «улучшение» готового алгоритма ухудшает его свойства. Поэтому перед тем, как взяться за написание велосипеда, обычный программист должен внимательно изучить теорию (и перестать быть обычным программистом).

Answer 3

[Arsen]

2-й том Искусства программирования Дональда Кнута
Там первая половина книги про Случайные числа
Исчерпывающие выкладки по сабжу

Comments

[mayorovp]

Ну, не то чтобы выкладки исчерпывающие, все-таки с тех пор много воды утекло, но как введение вполне подойдет.

Answer 4

[Владимир Мартьянов]

Судя по тегу «криптография» вы собираетесь использовать ГПСЧ для генерации некоторого криптографического ключа? Тогда нужно еще задуматься над тем, чтобы энтропии было достаточно.
А генератор, например, делается так: Xn=X_{n-1}*C+1 где C — некоторое число. Дополнительно — циклический сдвиг на 13 бит, к примеру.

Answer 5

[Maxim Kuzovlev]

Был уже похожий вопрос, может найдете что-то интересное для себя.