OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 03 Февраль, 2026 20:49

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2
Автор Сообщение
СообщениеДобавлено: Среда, 07 Январь, 2026 14:57 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
каких? ответ «любых» я не смогу принять: не знаю, что такое «любые расчёты».

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

Цитата:
повод чинить учебники

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

Цитата:
указывается область применимости, например.

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

Цитата:
будет разбазаривание кэша и тормоза, которых могло бы не быть. да, возможно очень маленькие, незаметные тормоза.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 19:33 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
Например, оценка погрешности косвенного измерения без использования производных, вообще получение каких-либо эмпирических распределений.
отлично. я таких не делаю и не собираюсь, тем более на восьмибиточке. зачем мне тратить время и такты на более сложный prng?

ScrollLock писал(а):
Тогда опишите области применимости для ГПСЧ.
где появляется «неопределённый круг задач» — там ни про какие области применения речь идти уже не может. как можно решать, применимо ли что-то для того не знаю чего?

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

ScrollLock писал(а):
Может быть, раздутые указатели и вызывают незаметные тормоза.
на это я уже ответил.

ScrollLock писал(а):
Но при этом большие указатели могут отчасти компенсироваться большими регистрами размером от 64 до 256 бит хотя бы в части задач.
я имею это без раздутых указателей — в SSE/AVX.

ScrollLock писал(а):
Думаю, что основные тормоза - от навороченных многослойных абстракций и злоупотребления интерпретируемыми и полуинтерпретируемыми языками.
и свой взгляд на причины этого я тоже выше изложил.

ScrollLock писал(а):
Кстати, Обероны в некоторых случаях используют более медленные решения для повышения надёжности: например, включенный по умолчанию контроль выхода за границы массива.
zero cost (или почти zero cost) на любом камне с джамп предиктором и спекулятивным исполнением. проверено экспериментально.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 19:54 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
а для крипто никакие «сложные программно-аппаратные комплексы» не нужны.

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

Цитата:
глупости с constant time

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

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

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

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

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

Цитата:
тем более на восьмибиточке.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 20:35 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
Цитата:
глупости с constant time
И даже это зачастую легко решается либо аппаратным AES, либо ARX-шифрами.
я имел в виду, что constant time нафиг не нужен. это бонус, который можно иметь, но нет смысла ним специально заморачиваться.

ScrollLock писал(а):
Тогда определите круг задач, в которых применимы те или иные виды ГПСЧ.
эта проблема решается с хвоста: сначала у нас есть задача, а потом мы определяем применимость — исходя из требований задачи. нет конкретной задачи — нет и решения.

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

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

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

ScrollLock писал(а):
Я довольно легко мог бы представить попытки решать какие-то простейшие статистические задачи на 8-битных компьютерах.
представить я тоже могу. но не стану — потому что привык решать конкретные задачи, а не воображаемые.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 22:01 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
эта проблема решается с хвоста: сначала у нас есть задача, а потом мы определяем применимость — исходя из требований задачи. нет конкретной задачи — нет и решения.

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

Цитата:
мы платим за них более сложным кодом. чем больше кода — тем дольше его писать

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 22:27 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
Тогда какой метод выбора ГПСЧ Вы предлагаете для разных задач?
ну я же писал уже неоднократно: определить требования задачи к качеству. выбрать наиболее простое из того, что из удовлетворяет. где-то вообще хватит чтения регистра R на Z80 и вычитания его из аккумулятора со сдвигом. или вовсе тыканье пальцем в ROM.

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

ScrollLock писал(а):
И почему не пытаетесь тогда подобрать реализацию синуса или косинуса под задачу (или пытаетесь)?
конечно, делал. где-то вообще таблицы с интерполяцией достаточно, например. где-то по Чебышёву, почему да. для фикспоинта кордик делал. много разного было.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 22:47 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
в ТЗ указано: «случайное поведение врагов в аркаде»

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 07 Январь, 2026 23:10 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
В моей классификации это вариант 3 - написание Тетриса, и в этом случае использовать генераторы с грубыми статистическими дефектами можно. Т.к. тут требуется скорее не случайность, а соответствие поведения программы неким эстетическим требованиям. Но как только мы переходим к варианту 2 (математико-статистическим расчётам), сразу происходит качественный скачок в требованиях в виде TestU01 и PractRand на выборках в десятки терабайт и периодах не меньше 2^60
ну вот мы и сошлись, кажется: есть конкретная задача, есть её требования — выбираем подходящий инструмент. я предпочитаю максимально простой инструмент, который удовлетворяет условиям — следуя духу оберона, так сказать.

ScrollLock писал(а):
И проблема в том, что 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, ни в задачи мана не входит: предполагается, что читающий в курсе.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 00:21 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
где тут попытки чем-то притвориться?

В этом абзаце - есть попытка притворяться, всякие "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, но она только для выдачи сидов подходит, ибо невоспроизводима. Да, расчётчик должен понимать, что использует. Но адекватная документация - это уже ответственность разработчиков библиотеки, и четко маркировать плохие алгоритмы они по идее должны.

Цитата:
обучение свойствам prng ни в задачи obx, ни в задачи мана не входит: предполагается, что читающий в курсе.

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 01:06 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
В этом абзаце - есть попытка притворяться, всякие "use drand48_r instead". Или на "man 3 rand" пишут вот такое:…
не вижу. «as random as the higher-order bits» говорит только о том, что неважно, какие биты брать. про качество этой рандомизации — ни слова. просто не надо в технических текстах читать то, чего в них не написано. в `man 3 random` даже сказано: «Random-number generation is a complex topic.» и дальше немного ссылок на литературу. а вот про то, проходит ли реализация статистические тесты — не сказано ничего. а раз не сказано — то и нет причины предполагать, что проходит.

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

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

ScrollLock писал(а):
Ну а вот чем xoroshiro-aox не соответствует духу Оберона?
а мне просто автор не нравится. имею право на личные антипатии.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 01:39 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
про качество этой рандомизации — ни слова. просто не надо в технических текстах читать то, чего в них не написано.

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

Цитата:
В `man 3 random` даже сказано: «Random-number generation is a complex topic.»

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

Цитата:
понадобился какой-нибудь генератор.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 01:58 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
ScrollLock писал(а):
Если они сравнивают разные генераторы, и говорят про что-то "Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)", то уже делают какие-то утверждения о качестве, причем не вполне соответствующие действительности.
утверждение «random() лучше rand()» скорее всего соответствует действительности (в мане описано, почему). единственное, к чему можно придраться — это, пожалуй, к слову «good».

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

ScrollLock писал(а):
И он остался в BlackBox просто как устаревший хлам
он остался в BBCB как пример. никто не должен ожидать от подсистемы Obx чего-то кроме простейшей демонстрации принципов. кто ожидает — сам виноват.

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

ScrollLock писал(а):
в конце XXI века
я не доживу, мне всё равно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 02:12 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
однако обучать подобному — не задача манов. они сказали, что Всё Сложно, предложили книжек. дальше кому интересно — идёт и разбирается в теме.

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

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

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

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

Цитата:
что в оригинальном libc было, и оттуда эту чушь затащили в позикс.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 02:19 

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 02:26 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1673
p.p.s.: вообще, с состоянием в 32 бита было бы наивно ожидать хороший генератор. даже состояние в 48 как-то не вселяет энтузиазма.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 08 Январь, 2026 02:29 

Зарегистрирован: Среда, 01 Август, 2007 00:13
Сообщения: 207
arisu писал(а):
это ж такая вонь поднимется! сразу начнётся заруба по поводу того, что предложить взамен, как именно сформулировать «он плохой» и прочая, прочая.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Рассуждения о разных PRNG
СообщениеДобавлено: Вторник, 03 Февраль, 2026 14:04 

Зарегистрирован: Вторник, 30 Сентябрь, 2025 21:13
Сообщения: 89
Потребовалась функция для вычисления SHA-1. Стал искать. Просмотрел в архивах Oberon. Не нашел. Нашел в официальных реализациях FreePascale и Lazarus. Посмотрел и закрыл. Это ж надо так любить программирование и следовать канонам чистоты кода, что простую функцию обернуть в объект, основной код размазать по десятку однострочных методов и разнести по двум или вроде даже трём модулям (((.

Решил не страдать дальше, реализовал алгоритм из Wikipedia. Заодно и adler32. Тоже нужна. Единственно не понятно - в правильном ли порядке записал результат в итоговую строку. А так, протестировал работает ))).

Код:
(* adler32 - хеш функция Марко Адлера. Вычи
             сляет значение контрольной сум
             мы в соответствии с RFC 1950
             для массива из байт          *)

PROCEDURE adler32*(buf : PtrCHAR;
                   len : INTEGER) : INTEGER;
   VAR s1,s2, ii  : INTEGER;
BEGIN
   s1 := 1;
   s2 := 0;
   FOR ii := 0 TO len-1 DO
       s1 := (s1 + ORD(buf[ii]) ) MOD 65521;
       s2 := (s1 + s2) MOD 65521;
   END;
   RETURN s1 + LSH(s2, 16);
END adler32;


(* sha_1  -  алгоритм криптографического хе
             ширования в соответствии с RFC
             3174 для массива из байт     *)

PROCEDURE sha_1   (buf : PtrCHAR;
                   len : INTEGER) : shaCHAR;
   VAR h0,h1,h2,h3,h4  : INTEGER;
       r0,r1,r2,r3,r4  : INTEGER;
       nm,cn,ii,ff,kk  : INTEGER;
       ws : ARRAY 080 OF INTEGER;
   VAR rs : shaCHAR;
BEGIN
   (* начальная инициализация             *)
   h0 := 067452301H;
   h1 := 0EFCDAB89H;
   h2 := 098BADCFEH;
   h3 := 010325476H;
   h4 := 0C3D2E1F0H;
   rs := nul;
   cn := len;

   (* дополнение до кратности 512 битам   *)
   buf[cn] := 80X; INC(cn);
   buf[cn] := 00X; INC(cn);
   buf[cn] := 00X; INC(cn);
   buf[cn] := 00X; INC(cn);
   buf[cn] := 00X; INC(cn);
   nm := 64 - cn  MOD 64  ;
   nm := nm + 64* ORD(nm < 4);
   FOR ii := 0 TO nm - 5 DO
                 buf[cn] := 0X; INC(cn) END;

   (* пишем длину в обратном порядке      *)
   len := len * 8;
   buf[cn] := CHR( LSH(len, -24) ); INC(cn);
   buf[cn] := CHR( LSH(len, -16) ); INC(cn);
   buf[cn] := CHR( LSH(len, -08) ); INC(cn);
   buf[cn] := CHR(     len       ); INC(cn);

   (* разбиваем на части по 512 бит       *)
   FOR ii := 0 TO cn DIV 64 - 1 DO

       (* инициализация хеш этой части    *)
       kk := ii * 64;
       r0 := h0;
       r1 := h1;
       r2 := h2;
       r3 := h3;
       r4 := h4;
       FOR nm := 00 TO 15 DO
           ws[nm] := LSH(ORD(buf[kk+0]),24)
                   + LSH(ORD(buf[kk+1]),16)
                   + LSH(ORD(buf[kk+2]),08)
                   +     ORD(buf[kk+3]    );
           kk := kk + 4;
       END;
       FOR nm := 16 TO 79 DO
           ws[nm] := RSH(ORD(BIT(ws[nm-03])
                           / BIT(ws[nm-08])
                           / BIT(ws[nm-14])
                           / BIT(ws[nm-16])
                                    ), 01 );
       END;

       (* цикл вычисления хеш этой части  *)
       FOR nm := 00 TO 79 DO
           IF nm < 20 THEN kk := 05A827999H;
              ff := ORD((BIT(r1) * BIT(r2))
                     + ((
                        -BIT(r1)
                               ) * BIT(r3))
                       );
           EI nm < 40 THEN kk := 06ED9EBA1H;
              ff := ORD(BIT(r1) / BIT(r2)
                                / BIT(r3) );
           EI nm < 60 THEN kk := 08F1BBCDCH;
              ff := ORD((BIT(r1) * BIT(r2))
                     +  (BIT(r1) * BIT(r3))
                     +  (BIT(r2) * BIT(r3))
                       );
                      ELSE kk := 0CA62C1D6H;
              ff := ORD(BIT(r1) / BIT(r2)
                                / BIT(r3) );
           END;

           ff := RSH(r0, 05)
                    + ff + r4 + kk + ws[nm];
           r4 := r3;
           r3 := r2;
           r2 := RSH(r1, 30);
           r1 := r0;
           r0 := ff;
       END;

       (* добавляем хеш части результату  *)
       h0 := h0 + r0;
       h1 := h1 + r1;
       h2 := h2 + r2;
       h3 := h3 + r3;
       h4 := h4 + r4;
   END;

   (* пишем результат big endian -------- *)
   rs[00] := CHR(LSH(h0, -24));
   rs[01] := CHR(LSH(h0, -16));
   rs[02] := CHR(LSH(h0, -08));
   rs[03] := CHR(    h0      );

   rs[04] := CHR(LSH(h1, -24));
   rs[05] := CHR(LSH(h1, -16));
   rs[06] := CHR(LSH(h1, -08));
   rs[07] := CHR(    h1      );

   rs[08] := CHR(LSH(h2, -24));
   rs[09] := CHR(LSH(h2, -16));
   rs[10] := CHR(LSH(h2, -08));
   rs[11] := CHR(    h2      );

   rs[12] := CHR(LSH(h3, -24));
   rs[13] := CHR(LSH(h3, -16));
   rs[14] := CHR(LSH(h3, -08));
   rs[15] := CHR(    h3      );

   rs[16] := CHR(LSH(h4, -24));
   rs[17] := CHR(LSH(h4, -16));
   rs[18] := CHR(LSH(h4, -08));
   rs[19] := CHR(    h4      );   RETURN rs;
END sha_1;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Рассуждения о разных PRNG
СообщениеДобавлено: Вторник, 03 Февраль, 2026 14:11 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4748
Откуда: Россия, Орёл
Михаил писал(а):
Стал искать. Просмотрел в архивах Oberon. Не нашел.

Плохо искали.
https://blackbox.oberon.org/extension/Crypto
Очевидно, что есть в А2, а также есть старая реализация для ETH Oberon.

Да и у arisu тоже есть, скорее всего, свой вариант.

P. S. Тут вроде про случайные числа тема...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Рассуждения о разных PRNG
СообщениеДобавлено: Вторник, 03 Февраль, 2026 19:26 

Зарегистрирован: Вторник, 30 Сентябрь, 2025 21:13
Сообщения: 89
Скачал. Распаковал. Открыл. Закрыл. Честно . . . в качестве компактной, переносимой, встраиваемой функции . . . совсем не подходит (((.

ps: Показалось, что хеш функция тоже имеет ‘случайную’ природу. Если нет, пост лучше удалить. Переносить в отдельную тему не стоит. В криптографии полный ноль.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2026, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB