OberonCore

Например, оценка погрешности косвенного измерения без использования производных, вообще получение каких-либо эмпирических распределений. Если minstd или аддитивные генераторы Фибоначчи проваливают простые статистические тесты, выполнимые за одну ночь на IBM PC XT - то значит, они способны и сломаться на любой ерунде.


Да, пора, в т.ч. включать туда хотя бы упоминание теста на следующий бит и поточных шифров. И честного указания на "обычные" генераторы как на компромисс.


Тогда опишите области применимости для ГПСЧ. Я вижу три области:
1) Криптография. Тут нужны уже не ГПСЧ, а сложные программно-аппаратные комплексы, обычно интегрированные в ядро ОС.
2) Некриптографические генераторы для неопределенного круга задач. Минимальные требования - прохождение TestU01 и PracRand и теоретические гарантии периода, максималистские - поточные шифры без обновления ключа в ходе симуляции. Исключения в виде MT19937 возможны, но с четким пониманием, что за тесты он проваливает и чем это грозит.
3) Написание Тетриса. Вот тут можно и minstd, и RANDU, и JSF, и xorwow.


Может быть, раздутые указатели и вызывают незаметные тормоза. Хотя у меня FAR с Colorer что под 32, что под 64 бит работает очень быстро, какие-то ощутимые задержки я ощущал только на файлах в сотни тысяч строк, и то при загрузке (и там, и там - одинаковые примерно). nano тоже очень шустрый. Но при этом большие указатели могут отчасти компенсироваться большими регистрами размером от 64 до 256 бит хотя бы в части задач. Думаю, что основные тормоза - от навороченных многослойных абстракций и злоупотребления интерпретируемыми и полуинтерпретируемыми языками. Кстати, Обероны в некоторых случаях используют более медленные решения для повышения надёжности: например, включенный по умолчанию контроль выхода за границы массива. Или сборку мусора.

отлично. я таких не делаю и не собираюсь, тем более на восьмибиточке. зачем мне тратить время и такты на более сложный prng?

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

а для крипто никакие «сложные программно-аппаратные комплексы» не нужны. я лично вижу, что крипто нормально работает на том, что имеем. и алгоритмы там не такие сложные, чтобы требовать отдельного железа. когда-нибудь ещё глупости с constant time, наконец, прекратят, идиотию со всякими псевдоуязвимостями типа «spectre» — и совсем будет хорошо.

на это я уже ответил.

я имею это без раздутых указателей — в SSE/AVX.

и свой взгляд на причины этого я тоже выше изложил.

zero cost (или почти zero cost) на любом камне с джамп предиктором и спекулятивным исполнением. проверено экспериментально.

исследования (ссылки на которые я традиционно того) показывают, что GC не медленней ручного управления памятью. иногда даже быстрее. проблема в основном в заметных глазами паузах если GC сделан как stop-the-world. это решаемо, если возникнет необходимость. а если немного пропатчить ядро, то GC вообще может быть lightning fast — как сделали в интересной конторе Azul для java, например. copying GC попутно ещё и решает проблемы с фрагментацией хипа.

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


И даже это зачастую легко решается либо аппаратным AES, либо ARX-шифрами. Нужные для них наборы инструкций на x86 уже довольно древние.


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


Думаю, тут многое будет зависеть и от процессора, и от оптимизаций компилятора, и от конкретной задачи. ГПСЧ на основе шифров, кстати, в подавляющем числе случаев даже более "бесплатны", чем проверки границ массивов. А уж просто проходящие BigCrush и PractRand на 32-битных и 64-битных машинах вообще ничего не стоят, и даже быстрее minstd и компактнее генераторов Кнута.


Я довольно легко мог бы представить попытки решать какие-то простейшие статистические задачи на 8-битных компьютерах.

я имел в виду, что constant time нафиг не нужен. это бонус, который можно иметь, но нет смысла ним специально заморачиваться.

эта проблема решается с хвоста: сначала у нас есть задача, а потом мы определяем применимость — исходя из требований задачи. нет конкретной задачи — нет и решения.

zero cost с одним маленьким условием. пара cmp/jnc стоит ничего, потому что cmp исполняется в параллели со следующей инструкцией чтения из памяти (или записи в), а jnc не стоит ничего в случае jump-not-taken (подавляющее большинство случаев) если прыгаем за пределы кэша команд и вперёд (это условие легко соблюдается размещением кода для трапов после основного кода процедуры).

теоретические рассуждения проверены практическими тестами: обмолотом матриц и lz-компрессором. что включай проверки, что выключай — разница в пределах статпогрешности. (не в CP2.) O/Ur не имеет ни DFA, ни VRP, и не в состоянии исключать ненужные проверки диапазонов — так что всё честно: никаких оптимизаций, «что вижу — то и спел.»

мы платим за них более сложным кодом. чем больше кода — тем дольше его писать, и тем больше вероятность ошибки в нём. и потоковые шифры не «более бесплатны» хотя бы за счёт того, что они обычно всё равно блочные, и надо держать в кэше весь блок. или имеют большое состояние.

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

Тогда какой метод выбора ГПСЧ Вы предлагаете для разных задач? И как определяете, что нужно от генератора в задаче или не нужно? И почему не пытаетесь тогда подобрать реализацию синуса или косинуса под задачу (или пытаетесь)?


С моей точки зрения ГПСЧ на основе ARX-шифров - это довольно простые в реализации алгоритмы, особенно с тестовыми векторами. Кросс-платформенную версия PCG со 128-битным состоянием писать было ощутимо сложнее. Хотя я в своей жизни встречал пока только две задачи, где шифры были бы объективно предпочтительнее обычных генераторов:
1) Калибровка статистических тестов для самих ГПСЧ, там использовать некриптографические генераторы было бы безумием.
2) Параллельный генератор для многопоточной программы на C++ на "скорую руку".

ну я же писал уже неоднократно: определить требования задачи к качеству. выбрать наиболее простое из того, что из удовлетворяет. где-то вообще хватит чтения регистра R на Z80 и вычитания его из аккумулятора со сдвигом. или вовсе тыканье пальцем в ROM.

по тому, что указано в ТЗ. если, например, в ТЗ указано: «случайное поведение врагов в аркаде» — я сначала попробую R или ROM и посмотрю, нормально ли с этим играется.

конечно, делал. где-то вообще таблицы с интерполяцией достаточно, например. где-то по Чебышёву, почему да. для фикспоинта кордик делал. много разного было.

В моей классификации это вариант 3 - написание Тетриса, и в этом случае использовать генераторы с грубыми статистическими дефектами можно. Т.к. тут требуется скорее не случайность, а соответствие поведения программы неким эстетическим требованиям. Но как только мы переходим к варианту 2 (математико-статистическим расчётам), сразу происходит качественный скачок в требованиях в виде TestU01 и PractRand на выборках в десятки терабайт и периодах не меньше 2^60, который делает непригодным подавляющее большинство ГПСЧ из TAOCP2. И проблема в том, что ObxRandom из BlackBox и rand() из glibc - это уровень 3 (написание Тетриса), который пытается притворяться уровнем 2.


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

ну вот мы и сошлись, кажется: есть конкретная задача, есть её требования — выбираем подходящий инструмент. я предпочитаю максимально простой инструмент, который удовлетворяет условиям — следуя духу оберона, так сказать.

да не пытается же. ни в манах, ни в доке по obx нет никаких утверждений про качество генераторов. как минимум `man 3 rand` говорит вот что:
The value pointed to by the seedp argument of rand_r() provides only a very small amount of state, so this function will be a weak pseudo-random generator. Try drand48_r(3) instead.
а `man 3 drand48` прямо показывает реализацию (LCG, и псевдокод приводит). где тут попытки чем-то притвориться? обучение свойствам prng ни в задачи obx, ни в задачи мана не входит: предполагается, что читающий в курсе.

В этом абзаце - есть попытка притворяться, всякие "use drand48_r instead". Или на "man 3 rand" пишут вот такое:

The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)

Т.е. они создают обманчивое впечатление о хорошем качестве функций random (не путать с /dev/urandom), rand, drand48, drand48_r, рассуждая о том, что там качественнее, что менее качественно. По идее нужно честно написать в начале man-страниц всех этих функций предупреждения о том, что алгоритмы плохие, оставлены только для совместимости и примера "так жить нельзя", не подчиняются равномерному распределению и годятся только для Тетриса. Безо всяких этих ужимок про биты, периоды и т.п. И нет, тут речь не про криптостойкость, а про провал простейших тестов на равномерность распределения (например, той же SmallCrush), которые на современном ПК проходят за секунды. Единственная нормальная функция из всего этого зоопарка - это getrandom, но она только для выдачи сидов подходит, ибо невоспроизводима. Да, расчётчик должен понимать, что использует. Но адекватная документация - это уже ответственность разработчиков библиотеки, и четко маркировать плохие алгоритмы они по идее должны.


Зачем даже примерами учить плохому, когда можно учить хорошему? И нет, не обязательно шифрам, для начала подойдет любой простой алгоритм, проходящий TestU01 и PractRand. Да и ссылка в документации на книгу "Martin Reiser, Niklaus Wirth, Programming In Oberon, ISBN 0201565439" может создать обманчивое впечатление о том, что minstd - хороший алгоритм, хотя на самом деле нет.


Ну а вот чем xoroshiro-aox не соответствует духу Оберона? Он даже в систему типов без 64 битов и переполнений встраивается прекрасно.

не вижу. «as random as the higher-order bits» говорит только о том, что неважно, какие биты брать. про качество этой рандомизации — ни слова. просто не надо в технических текстах читать то, чего в них не написано. в `man 3 random` даже сказано: «Random-number generation is a complex topic.» и дальше немного ссылок на литературу. а вот про то, проходит ли реализация статистические тесты — не сказано ничего. а раз не сказано — то и нет причины предполагать, что проходит.

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

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

а мне просто автор не нравится. имею право на личные антипатии.

Если они сравнивают разные генераторы, и говорят про что-то "Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)", то уже делают какие-то утверждения о качестве, причем не вполне соответствующие действительности. Хотя в этой функции - тот самый не подчиняющийся равномерному распределению аддитивный генератор Фибоначчи. Т.е. на man-странице говорится, что алгоритм из random() хороший - это то ли устаревшая документация, то ли некомпетентность её авторов. Возможно, просто таскают всякий древний хлам, и никому нет дела.


Само по себе это правильно. Но современное состояние этого "complex topic" таково, что random(), rand() и drand48() - это плохие генераторы, не так далеко ушедшие от RANDU.


Я понимаю, почему там оказался minstd, т.к. он взят из книги 1980-х. Естественно, в книге Programming In Oberon о нем говорят как о высококачественном, т.к. в 1980-е выборки были намного меньше, а тесты не такими строгими. Сейчас же этот ГПСЧ уже игрушка. И он остался в BlackBox просто как устаревший хлам, примерно как в glibc остался аддитивный генератор Фибоначчи. И нет, он не лучше современных альтернатив (не обязательно xoroshiro ), там есть дорогая операция деления.

Кстати, первые в истории ГПСЧ, проходящие современные тесты, это DES и Магма. Да, они тяжёлые, но тот факт, что устаревшие шифры 50-летней давности проходят TestU01 и PractRand, говорит о том, какой в них колоссальный запас прочности был заложен. И есть хорошие шансы, что и в конце XXI века AES и ChaCha будут считать хорошими генераторами, насчет xoroshiro или PCG я бы не был бы так уверен.

утверждение «random() лучше rand()» скорее всего соответствует действительности (в мане описано, почему). единственное, к чему можно придраться — это, пожалуй, к слову «good».

однако обучать подобному — не задача манов. они сказали, что Всё Сложно, предложили книжек. дальше кому интересно — идёт и разбирается в теме.

он остался в BBCB как пример. никто не должен ожидать от подсистемы Obx чего-то кроме простейшей демонстрации принципов. кто ожидает — сам виноват.

и мы снова возвращаемся к тому, что «стандартные библиотеки» не нужны. Obx вообще таковой не является, а glibc вынуждена иметь хоть какой-то `rand()`, потому что в оригинальном libc было, и оттуда эту чушь затащили в позикс. ну, надо вам хоть какой-то — вот он. позикс большего не требует. мы compliant — и всё, отстаньте.

я не доживу, мне всё равно.

Конкретно в этом случае нет абсолютно ничего сложного в том, чтобы в начале каждой man-страницы написать внятное предупреждение о низком качестве этих функций, т.е. качество тут не "всё сложно", а "плохо". И опять мы имеем дело с двойными стандартами: если вызвать sin из libc без чтения Демидовича и Марона, то скорее всего всё будет нормально. А вот с rand() почему-то возможны проблемы.

Судя по комментариям в исходниках glibc, эти алгоритмы взяты из какой-то BSD 1980-х. И, похоже, мне удалось найти оригинал:

https://github.com/dank101/4.2BSD/blob/ ... n/random.c

Интересно, что в 1983 году Gap Test, который эти движки проваливают, уже был известен, и даже описан в TAOCP2. Тест Birthday Spacings тогда ещё то ли не был опубликован, то ли только-только появился. Т.е. он уже тогда был не очень хорошим. А уж сейчас то, что такие алгоритмы находятся в стандартной библиотеке языка Си - это глубоко патологично.


Судя по содержимому man-страницы, они уже меняли генератор. С линейного конгруэнтного на генератор Фибоначчи из BSD. Т.е. заменили полный ужас на просто ужас.

да, с тем, что в маны стоило бы большими буквами дописать: «ЕСЛИ ВАМ ДОРОГИ ЖИЗНЬ И РАЗУМ — НЕ ИСПОЛЬЗУЙТЕ ЭТОТ ГЕНЕРАТОР» — я согласен. но я также понимаю, почему не трогают: это ж такая вонь поднимется! сразу начнётся заруба по поводу того, что предложить взамен, как именно сформулировать «он плохой» и прочая, прочая.

а вот слово «good» можно было бы втихую убрать.

p.s.: кстати, мы мощно загадили топик. Борис, может отрезать кусочек с нашей весёлой беседой?

p.p.s.: вообще, с состоянием в 32 бита было бы наивно ожидать хороший генератор. даже состояние в 48 как-то не вселяет энтузиазма.

Да так и сформулировать, просто и однозначно - грубые статистические дефекты, низкокачественный алгоритм. Думаю, что для random() из glibc проблему вообще можно решить "малой кровью", добавив туда простой нелинейный скремблер на 3 строчки. Примерно как сделали в PCG, только тут даже проще будет.


У random() из lfib состояние большое, как бы не больше, чем у ChaCha20. Насчёт состояния 48 бит: мне как-то удалось сделать генератор, который с таким состоянием проходил BigCrush и в PractRand разваливался только на 16 ТиБ.