OberonCore

Как генерировать случайные числа?

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

А разве такое устройство не встроено в каждый современный компьютер?

Я собираюсь написать программу сортировки. Для неё нужно сгенерировать массив чисел.

Можете воспользоваться модулем ypkMathRandom из компонента ypk http://oberoncore.ru/bbcc/subs/ypk/start

Я обычно пользуюсь таким кодом:

Нет, но персональные компьютеры оснащены устройствами, от которых в качестве побочных эффектов можно получить небольшое количество случайных чисел, комбинируя которые с генераторами псевдослучайных чисел можно получить поток чисел, почти всегда достаточно хороший для задач криптографии. Почти.
Для этой задачи полностью подходит простейший линейный конгруэнтный метод, который привёл Рифат. Можно и без WinApi. Плохо то, что допускается арифметическое переполнение, но в BlackBox это будет работать.

Для простых задач обычно достаточно ObxRandom.

Наиболее разнообразная реализация генераторов опубликована у Хельмута.
http://www.zinnamturm.eu/downloadsOS.htm#Rng

Obx это же не библиотечные модули, это модули с примерами. Зачем такое рекомендовать?

Из лекций:

Для такой задачи ObxRandom достаточно.

Только надо инициализировать.

Так твой модуль и не отличается от ObxRandom алгоритмом.

Вот твой код:


Вот ObxRandom:


Для новичка проще использовать то, что есть "из коробки". Хотя с установкой расширений всё равно придется разобраться рано или поздно.

Дело не в том, что код совпадает, а в том, что Obx это набор примеров.

Что такое "простые задачи" - сложно формализовать. Некоторые весьма "злобные" статистические тесты основаны на сортировке массива псевдослучайных чисел. Думаю, что в качестве генераторов общего назначения следует использовать криптографически стойкие генераторы с периодом не менее 2^{64}. Всё равно они по производительности и сложности реализации сопоставимы с вихрем Мерсенна. А отказ от криптостойкости нужно специально обосновывать. Даже если использовать примитивные алгоритмы на 5-10 строчек, непригодные для шифрования, то они:
1) Должны проходить SmallCrush, Crush и BigCrush из TestU01.
2) Должны проходить PractRand 0.94 на выборке 32 терабайта.
Ни minstd из ObxRandom, ни даже вихрь Мерсенна им не удовлетворяют.

Вот заметка с более подробным обоснованием использования криптографических алгоритмов как генераторов псевдослучайных чисел общего назначения:
https://sortingsearching.com/2023/11/25/random.html


Его не так просто реализовать на Обероне, т.к. нужно умножать 128-битное число на 64-битное и возвращать старшие 32 бита результата. А линейные конгруэнтные генераторы с состоянием короче 128 бит - это скорее игрушки, чем рабочие инструменты.

признаться, не нашёл там обоснований, кроме: «а чего, техника быстрая, давайте бездумно тратить циклы без анализа предметной области». это, если что, АНТИрекомендация.

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

Сам по себе анализ предметной области для генераторов псевдослучайных чисел - штука весьма нетривиальная. И над ней много работали такие известные учёные как Дональд Кнут и Джордж Марсалья, и находили всё новые и новые сюрпризы приятные и не очень. Что касается "бездумно тратить циклы", то опасения несколько преувеличены. У меня при попытке самостоятельно померить скорость работы ГПСЧ получилось так:
0) RANLUX++ - 3.82 cpb (старый RANLUX работал ощутимо медленнее). Генератор вполне достоен, но некриптостоек.
1) ChaCha12 при использовании AVX2 - 1.0 cpb (криптостойкий).
2) ISAAC64 - 0.9 cpb (криптостойкий, есть много памяти)
3) minstd, аналогичный ObxRandom - 2.7 cpb (игрушечный генератор).
4) вихрь Мерсенна - около 1.0 cpb (некриптостойкий, ест много памяти, проваливает отдельные тесты)
5) 128-битный линейный конгруэнтный генератор - 0.53 cpb (некриптостойкий, хороший).
6) MWC128X - 0.21 cpb (некриптостойкий, хороший). От классического MWC отличается скрэмблированием выхода.
7) sfc64 - 0.12 cpb (некриптостойкий, хороший)
8) PCG32 - 0.5 cpb (некриптостойкий, хороший)
Измерял для версий на C99, откомпилированных GCC и встроенных в цикл суммирования. cpb - это "тактов процессора на байт".

Т.е. получается, что на современных 64-битных процессорах криптостойкий ChaCha12 обгоняет minstd, 32-битный линейный конгруэнтный генератор, непригодный для реальной работы. Парадокс кажущийся:
1) ChaCha12 выдаёт сразу блок из 16 32-битных псевдослучайных чисел, и это хорошо распараллеливается с помощью SIMD и конвейера.
2) В ChaCha12 нет никаких условных переходов (а циклы легко развернуть), и это любо конвейеру процессора.
3) В ChaCha12 нет операций умножения и деления вообще.

Если же мил сердцу минимализм и не нужно ничего шифровать - то есть генераторы, в 10-30 раз обгоняющие minstd и при этом проходящие BigCrush и PractRand.

Я бы сравнил криптостойкость генератора псевдослучайных чисел как вариант по умолчанию с неотключаемыми проверками границ массива в Обероне.

в данном случае предметная область — это задача, для которой нужен prng. вот у меня twin-stick shooter, например. мне там просто необходим криптостойкий prng, без него никак. у меня ж лишнего времени много, мне не надо ai считать, освещение, и ещё стопицот штук. и кэш бесплатный и бесконечный. поэтому конечно, вместо какого-нибудь bjprng/pcg32 — обязательно криптогенератор. чачу. которая на бенчмарках светится, само собой, ибо внутреннее состояние всегда в кэше процессора. и которую CP2 всенепременно запараллелит, потому что… ну фиг его знает, потому что магия, наверное.

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

собственно, я там дальше по ссылке полистал мощный бред автора про ai — и понял, что не стоило тратить время вообще. очередной сферический астронавт в вакууме. и демагог к тому же.

Тенденция в мире прямо противоположная: в стандартные библиотеки языков программирования норовят запихнуть всякую бяку, даже не способную пройти BigCrush. Подход "пихаем по умолчанию криптостойкий, а дальше как хотите" был бы несравненно адекватнее. Хотя и немного избыточен. Правда, я смотрю на ГПСЧ скорее через призму метода Монте-Карло, и меня удивила простота статистических тестов, способная выявить артефакты многих ГПСЧ. А в компьютерной игре иногда возможен подход из DOOM 1 "берём таблицу из 256 чисел и выдаём её в цикле". Но это не значит, что так можно делать в стандартной библиотеке.


Он как раз вполне нормален, уж точно нормальнее minstd.


Почему магия? Просто нужны ассемблерные вставки или интристики компилятора, и две параллельно работающих "чачи" помещаются в 4 256-битных регистра процессора. И состояние у них куда компактнее, чем у вихря Мерсенна, RANLUX или генератора Фибоначчи с запаздыванием.

Под Линуксом можно читать из /dev/random и /dev/urandom.

из /dev/random не надо никогда вообще. надо забыть, что это существует.

и ещё — это медленно очень. но в принципе можно, да. тем не менее обычно urandom используют чтобы сидировать внутренний cprng.