OberonCore

вот только в CP2 нет ассемблера.

вот только в CP2 нет таких интринсиков.

а про mersenne twister давно пора забыть. это был не самый удачный опыт.

Ну на счёт этого согласен.

Всё, как всегда, зависит от задачи.

Какой именно компилятор имеется в виду? И под какую архитектуру? Идёт ли речь о компиляции под 32-битные платформы, где сравнительная производительность алгоритмов может сильно отличаться от 64-битных?


Насколько я знаю, там раз CSPRNG используют с инициализацией из каких-то внешних источников энтропии.

CP2, однако.

падла… падла… падлавил! ;-)

Нашел весьма примитивный и при этом относительно приличный алгоритм для генерации псевдослучайных чисел - MWC64X:

https://cas.ee.ic.ac.uk/people/dt10/res ... wc64x.html

Единственный недостаток - операции с беззнаковыми целыми, в т.ч. сдвиги и побитовые XOR. Также есть два недопустимых сида. Можно избавиться от проблемы с беззнаковыми целыми, подобрав множитель. Например, a = 1073100393, для которого m = a*2^32 - 1 и (m - 1) / 2 - простые числа. Без скремблера с XOR использовать генератор нельзя - он даёт грубые артефакты.


Очень много плохих генераторов: Cray, Knuth, Minstd, Mwc (без скремблера), PboxRandom, R250, Randu, Slatec, Zufall, Vax. При этом предупреждение "really horrible" есть только у RANDU, хотя по идее оно тут нужно много где ещё. Вообще такая коллекция нужна скорее для историков и испытателей ГПСЧ. В реальности в стандартной библиотеке языка было бы достаточно двух алгоритмов для случайных чисел, не связанных с безопасностью: один - используемый по умолчанию на основе поточного шифра с инициализацией от /dev/urandom или от сида пользователя. И какой-нибудь очень быстрый и хорошо проходящий эмпирические тесты типа xoroshiro++ и поддерживающий функции перехода для потоков.

Вообще я считаю, что полезно придерживаться следующей философии при выборе ГПСЧ для любых задач:
1) Речь про обычный компьютер и скорости 1 ГиБ/с достаточно? Надо брать поточный шифр типа AES или ChaCha12 и не мучиться.
2) Нужна какое-то запредельное быстродействие, работа на GPU, на микроконтроллерах и шифр тормозит? Или, может, шифр долго подключать и его нет под рукой? Тогда можно выбрать что-то проходящее BigCrush и PractRand.
3) Используемый генератор провалил Birthday Spacings test, Gap test, побайтный частотный тест? Немедленно выбросить, не рассуждая: он не подчиняется равномерному распределению.
4) Доказанный период меньше 2^60 или его вовсе нет? Немедленно выбросить, не рассуждая: это игрушка.
5) Генератор провалил что-то ещё? Тогда необходим анализ того, повлияют ли обнаруженные дефекты на симуляцию или нет. А лучше по возможности переходить к п.1., не особо раздумывая.

Может быть, для мигания светодиодом на микроконтроллере это будет и избыточным. Но надо честно тогда говорить, что мы используем не нормальный ГПСЧ, а низкопробный

P.S. Под Windows есть аналоги /dev/urandom, просто названия функций другие.

всё ещё интересно, чем не устраивают bjprng и pcg32.

надо брать не «поточный шифр», а наиболее простой код, который удовлетворяет требованиям. и bj, и pcg тривиально пишутся на ассемблере, потом оформляются как inline. быстро, дёшево, сердито. генератор Боба Дженкинса вообще не требует ничего кроме циклических сдвигов, xor, да сложений-вычитаний. очень быстрый на любой архитектуре, где есть barrel shifter. размер внутреннего состояния — 16 байт, как и у pcg32. в принципе, bj можно даже без ассемблера, чисто средствами SYSTEM из CP2 (хоть будет и не оптимально).

впрочем, большинство людей мгновенно портят любой prng, делая генерацию чисел в заданом диапазоне через mod.

Генератор Дженкинса не имеет доказанного минимального периода. PCG32 - уже неплох, хотя и проваливает PractRand 0.94 на 64 ТиБ. И, кстати, Дженкинс выпускал другой ГПСЧ, WOB2M, у которого период не может быть меньше 2^64. Там есть линейная часть, которая исключает короткие циклы:

https://burtleburtle.net/bob/rand/wob.html


Каким требованиям? Если они не сформулированы явно, то следует считать, что минимальные требования - это "тест на следующий бит", т.е. поточный шифр. Я считаю, что минимальные требования к некриптографическому ГПСЧ - это период не меньше 2^60, прохождение BigCrush и PractRand 0.94 на 32 ТиБ. JSF (bjprng) им не удовлетворяет (хорошо проходит тесты, но не знаем минимальный период), PCG32 - почти что удовлетворяет (на 32 ТиБ бывают плохие P-значения). Для любых многопоточных применений среди требований должны быть строгие гарантии того, что потоки не будут перекрываться. Если выбирать между MT19937 и JSF, то MT19937 предпочтительнее: да, у него есть статистические дефекты, но они обычно не мешают, и у него есть доказанный период.

Также криптографические генераторы полезны как образцовые ГПСЧ для проверки статистических тестов и симуляций. DES и RC4 не в счёт: у них есть легко обнаружимые артефакты.

И если уж спускаться на уровень ассемблера, то есть семейства xoroshiro++ и xoshiro++: они очень быстрые, у них нет плохих бит, и поддерживается многопоточность.

как минимум 2^20 при использовании указаного на странице сидирования.

почему это важно?

код использует 64-битные умножения. без ассемблера в CP2 не лезет.

требованиям задачи. если задачи нет, то `return 42;` — отличный prng.

если так уж важна скорость и криптостойкость — то есть ISAAC от того же Дженкинса, например.

я останусь при мнении, что заводить cprng для большинства практических задач — перебор, вполне хватит bjprng. который тривиально инлайнится, очень быстрый, имеет вполне удовлетворительный практически доказаный период, хороший теоретический, и его всегда можно ресиднуть, чтобы период увеличить (хоть это и не самая лучшая практика). уступает pcg только в том, что не имеет возможности перемотки.

p.s.: кстати замечу, что для качественного сидирования cprng желательно уже иметь cprng. а если уже есть — то зачем дальше-то? читать из /dev/urandom блоками, например.

Это - крошечный период. Я понимаю, что на практике нарваться на период меньше 2^60 для JSF32 маловероятно, но зачем это надо, если есть очень быстрые и простые алгоритмы с возможностью перемотки и гарантированным периодом?


В большинстве задач - наверное, не очень важно.


А какой вообще набор операций для CP2 удобно реализовывать без ассемблера и оптимально?


Да, он высококачественный. Но у него огромное состояние и нет возможности перемотки. У ChaCha, LEA и Speck128/128 состояние намного меньше, есть возможность произвольного доступа к любому члену последовательности. Правда, для разгона их до уровня ISAAC (а иногда и быстрее) нужна ручная оптимизация под AVX2. Без таких ручных оптимизаций скорость ChaCha12 сопоставима с minstd. Но уж если писать на ассемблере - почему не под AVX2?


Может быть, и перебор. Но зато снимающий любую головную боль про периоды, статистическое качество, и обладающий приемлемой сложностью и производительностью. И если речь про стандартные библиотеки языков программирование, то там использование криптогенераторов было бы как раз логично. Там можно позволить себе немного дополнительной сложности, и только историческая инерция мешает это принять. Тащить туда некриптографические алгоритмы, особенно плохие - это всё равно что тащить в функцию sqrt хак inverse square root из Quake III. Я вижу историю ГПСЧ так:
1) Первые ГПСЧ разработали около 75 лет назад как хакерские трюки для ламповых машин.
2) В 1970-е появляются первые качественные генераторы, разработанные при участии АНБ (DES-CBC) и КГБ (Магма-CBC).
3) В 1980-е формулируют теоретический критерий качества ГПСЧ под названием "тест на следующий бит". Но шифры тогда были слишком медленными.
4) Первый быстрый высококачественный ГПСЧ - ISAAC. Чуть позже появляется быстрый MT19937, проваливающий отдельные тесты, но всё же неплохой по качеству.
5) 2010-е гг. - ARX-шифры, AVX2 и аппаратный AES переводят некриптографические генераторы в разряд "битовых хаков" для тех, кто знает что делает.

Также в Windows и Linux есть системные криптогенераторы, и сиды следовало бы брать оттуда.

Для возможности воспроизвести результаты симуляции по сиду. Реализованный на стороне пользователя поточный шифр дает воспроизводимые по сиду последовательности, /dev/urandom невоспроизводим. Также шифр на стороне пользователя будет в несколько раз быстрее /dev/urandom.

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

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

поэтому я и топлю за качественный и простой в кодировании prng. а необходимость более сложных алгоритмов надо доказывать, что невозможно без постановки конкретных задач. во многих случаях, на самом деле, хватит даже простейшего кнутовского генератора — хоть он и не удовлетворяет строгим тестам. и — повторюсь — все отчего-то игнорируют bias от попытки получить случайное число в заданом диапазоне: толку-то с хорошего cprng, если его потом кастрируют mod'ом, например?

Вот как раз в ChaCha20 сделать ошибку куда сложнее, чем в каком-нибудь xoroshiro, MWC или даже JSF: в описании алгоритма (RFC 7539) есть тестовые вектора. Единственная проблема в RFC - счетчик 32-битный, в ГПСЧ для симуляций надо 64-битный. И если реализация ChaCha20 воспроизводит тестовые вектора и проходит PractRand хотя бы до 1 ТиБ - то с ней почти наверняка всё в порядке. И заодно получаем "из коробки" возможность "перемотки" куда угодно. И Speck128/128 и LEA тоже поставляют с тестовыми векторами. Когда мне понадобился ГПСЧ для параллельных расчётов, а в стандартной библиотеке языка его не было - то шифры оказались самым примитивным вариантом.


Какого именно? Если x_{n} = x_{n-54} + x_{n-24} mod 2^{32} без децимации, то это - игрушка для написания Тетриса, любую симуляцию с ним следует по умолчанию считать ошибочной. В литературе описаны случаи, когда подобные ГПСЧ приводили к ошибкам. Введение же децимации, устраняющее почти все дефекты, делает его медленнее ChaCha8. А если так - то зачем он нужен? Если с использованием PCG, SFC или xoroshiro++ я ещё могу согласиться, то с аддитивными/субтрактивными генераторами Фибоначчи без децимации - уже нет. И в glibc нужно честно написать про функцию rand() "Осторожно, используемый алгоритм - мусор!" Или выкинуть хлам и поставить AES, ChaCha или хотя бы xoroshiro++ или PCG.


Реализация ChaCha без агрессивных ассемблерных оптимизаций сопоставима по размеру и сложности с реализацией косинуса или функции ошибок. Более того, она в чём-то проще кода на Си из "Искусства программирования" для генераторов Фибоначчи. Использование криптогенератора по умолчанию, кстати, похоже на другие аспекты обероновской философии - приоритет надежности и корректности над скоростью. Например, включенные проверки границ массивов, сборка мусора, необходимость модуля SYSTEM для арифметики указателей.


Тут получается ненужная когнитивная сложность: думать над какими-то техническими деталями реализации, при условии относительной простоты наилучшей реализации.

[/quote]
Это уже отдельная проблема, которая тоже заслуживает внимания.

я не очень понял, когда мы переместились в задачу симуляции (чего, кстати?).

salsa/chacha имеют хотя бы тот недостаток, что у них состояние больше bjprng/pcg, например. опять же: в коде bjprng и pcg очень сложно ошибиться, потому что это тупо несколько строчек, которые на любом языке выглядят более-менее одинаково. тестовые векторы делаются путём генерации их эталонной реализацией.

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

опять задам вопрос: у меня twin-stick shooter. зачем мне там cprng? зачем мне там вообще Офигенно Качественный prng с периодом овердофигилиард? ладно, кнутовский генератор — это уж совсем неприлично, пацаны во дворе засмеют. но зачем мне там что-то сложнее bjprng? ой, да ладно, у меня рогалик, где всё — один сплошной рандом. после замены mersenne twister на bjprng — играется всё ещё отлично, никакой деградации не замечено. зато код стал проще и быстрее. зачем мне туда чачу засовывать, если `next()` у bjprng тупо инлайнится?

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

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

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

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


Но реализовывать его без ошибок сложнее ChaCha, т.к. там кольцевой буфер. И состояние у него больше, чем в ChaCha. Также его реализацию от самого Кнута читать сложнее, чем наивную реализацию ChaCha. PCG запомнить проще, кстати. Для LCG есть мнемонические множители 69069 (для 32 бит), 6906969069 (для 64 бит), 18000690696906969069 (для 128 бит), а выходная функция для 128-битной версии легко запоминается. Правда, даже на Си портабельно ее написать - уже сопоставимо по сложности с ChaCha. Есть ещё легко запоминающийся Widynski middle squares.


В самом Обероне, может, и нет. А вот в стандартных библиотеках BlackBox и FreeOberon до сих пор используется minstd без четких предупреждений. И его следовало бы заменить если не на ChaCha, то на PCG или xoroshiro++ уж точно. Кстати, отсутствие в Оберонах беззнаковых целых в сочетании с тем, что многие реализации сделаны как трансляторы в C, вызывает вопросы. Ведь в C переполнение знакового целого, в т.ч. при умножении - неопределенное поведение. ChaCha, PCG, xoroshiro, JSF - все используют переполнение, но насколько хорошо оно определено в реализациях Оберона? Компиляторы Си тут коварны, особенно при -O3, тем, что тестовые вектора могут нормально отработать. А при инлайнинге получится нечто неожиданное.


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

Также весьма загадочным выглядит то, что шифров обычно нет в курсах математической статистики и численных методов.

о! задача появилась! (я ни слова не понял, правда. %-)

на самом-то деле я с вами в общем согласен. я тут буяню просто потому, что у нас два обсуждения получилось: про качество prng, и про применимость/достаточность алгоритмов.

в BBCB это не стандартная библиотека, а так, пример. для примера нормально.

ну, в LC я запихал, конечно, pcg32. в основном по привычке.

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

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

современные компиляторы си просто неюзабельное гуано. современная сишечка попросту непригодна для написания программ. по крайней мере пока компилятор не разминировать обратно в sane mode, отключив дурацкие идеи идиотов-стандартизаторов.

тоже дискусионный вопрос. на самом деле стандарт де-факто — то, что реализует libm. если я верно помню, там нет никаких особых гарантий точности.

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

academia вообще довольно консервативное сообщество. там вон в курсе компиляторов Sea of Nodes до сих пор нет, например.

Насколько это учитывает Ofront+ и вообще транслятор Oberon в Си, есть ли там чёткие рекомендации по отключению конкретных "бзиков" компиляторов Си? Или, может, напротив, возможность генерировать код в духе истинных параноиков, которые рассчитывают на то, что при компиляции врубят -O3 в GCC 15? При прямой работе с C99 по крайней мере понятно, что это - не академичный, низкоуровневый язык, полный хаков и измученный оптимизаторами. При работе с ним я обычно иду немного другим путём: включаю много достаточно строгих предупреждений, в т.ч. -Wvla, -Werror, -Wconversion, -Wstrict-aliasing=1. А уж без -Wall -Wextra -Werror вообще работать нельзя.


Получается, что в Обероне нельзя написать архитектурно независимую версию PCG32 или JSF: либо будет аварийное завершение работы при переполнении, либо всё будет работать как надо, либо можно вообще нарваться на неопределённое поведение компилятора Си. Аддитивный генератор Фибоначчи также потребует "плясок с бубном" в виде битовых масок или их аналога. На ANSI C, кстати, PCG32 написать нельзя, т.к. там нет 64-битных целых. И очень мало качественных ГПСЧ можно легко реализовать в таких условиях. Мне приходит в голову разве что комбинации нескольких генераторов Multiply With Carry, особенно если есть знаковые 64-битные целые. Там прекрасно можно работать без переполнений. Может, для 31-32 битных целых тоже можно сделать хороший MWC.


Но их реальная точность весьма близка к машинному эпсилону.


Просто оно выглядит слишком похоже на стандартную библиотеку. И, насколько я знаю, идёт из старой книги, в которой один из соавторов - Вирт. Но 40 лет назад не было таких выборок и таких скоростей. Сейчас пример с minstd следовало бы снабдить предупреждением о том, что это - плохой генератор. И да, у него для Оберона есть редкая крутая особенность: его можно реализовать без переполнений.


Во многих случаях изучение применимости/достаточности плохого ГПСЧ потребует научного исследования с использованием в т.ч. криптогенераторов. Проще сразу брать хорошее. Мне для квантилей распределения ChaCha не обязательна, там и PCG и xoroshiro++ хватит. Но, скажем, для калибровки статистических тестов для самих ГПСЧ подходят только криптографические генераторы.

признаться, совершенно не знаю. в силу профдеформации «компиляцию в си» презираю, и такими инструментами не пользуюсь.

нельзя без -fwrapv и -fno-strict-aliasing. это минимум, без которого современная сишечка абсолютно бесполезна.

нельзя. как и многие другие низкоуровневые штуки. а зачем? я считаю, что переносим должен быть высокоуровневый код; а эффективная реализация примитивов по определению не переносима. так что IMPORT SYSTEM — и вперёд, занимаемся экстримом.

на анси си вообще ничего написать нельзя. поскольку переполнение не определено, то компилятор вправе заменить `a * b` на noop — а вдруг там переполнение? и всю программу свести к noop. анси си — прямая антитеза к тому, чем си изначально задумывался. именно поэтому gcc надо тщательно разминировать (я этот набор ключей называю unfuckup). я бы сделал свой компилятор, но именно сишечки — не хочу.

но вообще-то long long — это обычно оно. стандартом, впрочем, не гарантируется.

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

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


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


Избежать -fwrapv можно достаточно легко, вовремя проставляя unsigned, а также не позволяя всяких вольностей с неявным преобразованием целочисленных типов, в идеале вообще неявные сужающие преобразования не должны позволять скомпилировать программу на Си. И надо чётко понимать, что strlen возвращает не int. И со строгими ключами попытка использовать int для длины строк или участков памяти должна вести к тому, что программа просто не компилируется. Вот strict aliasing - да, более коварная штука, в каких-то случаях его отключение я прекрасно понимаю. Но чаще всё же проще сделать через union или memcpy, чтобы у кого-то с другими ключами компиляции оно бы заработало.

я не совсем про это. я про прикидывание качества prng для конкретной задачи. типа: «а надо ли нам тут такое крутое, или можно обойтись чем попроще, даже если оно biased?»

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

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

а можно просто отучить компилятор предполагать глупости. я смею утверждать, что абсолютно весь реально используемый си-код более-менее высокой сложности так или иначе полагается на то, что целые — 2-complement. unsigned же лучше вообще использовать как можно меньше: это хак, и оно запросто может вылезти боком. например, так: `for (unsigned f = len - 1; f >= 0; f -= 1) { … }`. ну да, компилятор может предупредить, что такое сравнение бессмысленно — и код придётся переделывать в менее очевидный. в общем, лишние пляски для того, чтобы удовлетворить идиотский стандарт, который намного разумней просто игнорировать.

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

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