О gjf64: никогда не слышал такого названия. Интересно, где именно Вы его встретили? Этот алгоритм, похоже, больше известен под названием xorshift128+ и взят отсюда: https://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
О Tyche: то, что публиковалось под этим названием (https://link.springer.com/chapter/10.1007/978-3-642-31464-3_10) - это не LFSR, а нелинейный генератор на основе преобразования из ChaCha. У Вас же действительно какая-то модификация xorshift. Но откуда именно тогда были взяты параметры?
Для Counter-Based PRNG их сложно подбирать, для LFSR - чуть проще, но всё равно сложновато, тестировать надо. И проверять межпоточные корреляции. А многопоточный генератор с состоянием короче 128 бит вряд ли вообще имеет смысл. 128-битный генератор - вообще может в регистры процессора поместиться. Даже несколько копий ChaCha - и то помещается. Вообще к вызову ГПСЧ надо относиться скорее как к вызову спецфункции вроде гамма-функции или функции ошибок, т.е. как к полноценному численному методу, где корректность может быть важнее скорости. Тем более ГПСЧ со 128 битами состояния и так бывают очень быстрые.
Какие именно константы, алгоритма или seed? Константы алгоритма далеко не всегда можно менять. Если же свои seed, то перекрытие будет выглядеть как появление одинаковых и длинных последовательностей в разных потоках. Если у ГПСЧ состояние хотя бы 128 бит, то в разных неперекрывающихся потоках вполне возможны одинаковые 64-битные значения (случайные коллизии).
Да, второй проще, и если нужно очень быстро - то AVX2-версия ThreeFry легко разгоняется до 0.4-0.5 cpb. AES, кстати, тоже можно использовать как счётчиковй ГПСЧ.Но xoroshiro с матрицами перехода раза в 2 быстрее, хотя такая экстремальная производительность нужна редко.
Они позволяют мгновенно "промотать" состояние генератора наили дажеитераций вперёд и получить гарантированно неперекрывающиеся потоки псевдослучайных чисел в параллельных программах. Альтернативный подход - Counter Based PRNG (т.е. счётчиковые ГПСЧ) вроде Philox или ChaCha, которые дают прямой доступ к любому члену последовательности по его номеру за.
Эти всптроенные в процессор генераторы могут быть в разы медленнее хорошо оптимизированной под SIMD ChaCha и уж тем более xoroshiro++. Также результат невоспроизводим, и были случаи отказов этой инструкции на каких-то процессорах, хотя и лет 10-15 назад. Для std::random_device индетерминизм стандартом языка не гарантируется. Думаю, что системный криптогенератор ( /dev/urandomи его аналоги под Windows) - это намного проще и надёжнее. В SmokeRand я для инициализации ГПСЧ при возможности использую rdseed, но только для подачи вместе с выходом криптогенератора, текущим временем и т.п. в хеш-функцию Blake2s, 256-битный хеш - это ключ для ChaCha20.
И в C++ "под капотом" тех же mt19937 или mt19937_64 очень даже понятно, что. Там алгоритмы специфицированы в стандарте.
Если использовать 8-битный алгоритм, то начиная с 10-16 объектов начнутся коллизии идентификаторов. Ведь такой ГПСЧ не может выдать больше 256 уникальных многобайтных идентификаторов.
Дискретный аналог логистического отображения - это скорее функция Климова-Шамира, ГПСЧ на её основе имеет полный период, математически доказанный. У младших бит малый период как у линейного конгруэнтного генератора с. Можно легко в этом убедиться экспериментально с помощью такого кода:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint8_t x = 0;
for (int i = 0; i < 256 + 16; i++) {
x += x*x | 0x5;
if (i % 16 == 0) {
printf("\n");
}
printf("%3u ", (unsigned int) x);
}
return 0;
}
Вообще если нужен игрушечный генератор размером 8-16 бит - то проще всего использовать xorshift Марсальи. Там низкопериодичных бит нет вообще, период для правильно подобранных параметров для 8 и 16 бит будет 255 и 65535 соответственно.
Имел в виду то, что существуют простые способы выявить статистические аномалии в выдаваемой вихрем Мерсенна последовательности. Этот ГПСЧ сводится к умножению двоичного вектора длиной около 2 КиБ на двоичную матрицу, вместо умножения - операция AND, вместо сложения - XOR (насколько я знаю, эти операции - из поля GF(2)). И матрица там весьма разреженная. Если взять выходную последовательность из 32-битных членов и выбрать какой-то отдельный бит из каждого из них, то эти биты - продукт LFSR длиной 19937. Что и выявляет алгоритм Берлекэмпа-Месси, похожий на оптимизированный под конкретную задачу метод Гаусса. Можно ещё генерировать случайные двоичные матрицы и их ранги считать, но это значительно дольше. Про другие выявленные дефекты вихря Мерсенна написано в этой статье: https://arxiv.org/abs/2512.21678 .
Тест linear complexity из TestU01 и SmokeRand основан на алгоритме Берлекэмпа-Месси. Вихрь Мерсенна этот тест проваливает.
Тест Matrix Rank (или BRank) из TestU01, PractRand и SmokeRand - это расчёт ранга двоичной матрицы. Только в PractRand матрицы достаточно большие для провала теста вихрем Мерсенна.
Какие преимущества у подхода с синтаксическим деревом по сравнению с наивным подходом с дуальными числами, в котором граф или дерево не строятся, но все арифметические операции над числами с плавающей запятой превращаются в операции над их векторами?
О формуле: она верная и легко выводится "на бумажке", но на практике не очень удобная из-за появления квадратов элементов из матрицы плана эксперимента. Проще напрямую применить преобразование Гивенса или Хаусхолдера (QR-разложение) к переопределенной системе, оно медленнее, но численно устойчивее, т.к. там нет явного обращения матрицы.
У F-теста есть хитрая особенность: он может показывать значимость регрессии даже при незначимости всех её коэффициентов. Речь про переобучение модели.
Всё это очень легко обобщается на полиномиальную или логистическую регрессию.
Обязательно ли наличие в регрессии константы для корректности формулы?
Для малых выборок это может сработать, но если симуляция потребляет терабайты, то место на диске кончится. Да и читать с диска медленнее, чем генерировать на ходу в памяти. Также аккуратно реализованные AES или ChaCha на стороне пользователя в несколько раз быстрее /dev/urandom, и их удобно параллелить.
Если речь про C++ (C++11 и выше) - то использовать вместо неё стандартную библиотеку языка, там есть вихрь Мерсенна, хотя он и не очень удобен для параллельных программ (для них удобнее Philox или ChaCha). Если чистый Си - то написать свою функцию rand. Помимо генераторов из статьи ещё хороши xoroshiro++/**, образцовые реализации с матрицами перехода опубликованы на сайте автора. Матрицы перехода нужны для многопоточности.
С логистическим отображением есть проблема: оно требует вещественных чисел, с которыми компьютер работать не может. И вместо логистического отображения в программе будет какое-то необратимое преобразование 64-битного целого числа (с точки зрения типов данных языка программирования это будет тип double, но в памяти машины оно всё равно выглядит как последовательность бит). Если преобразование необратимое - то средний период генератора будетс возможностью попадания в очень короткие циклы. Т.е. пользоваться таким ГПСЧ для расчётов нельзя, даже функция rand() из glibc будет и то приличнее, у неё хотя бы доказанный (и большой) период есть и она скорее всего пройдет хотя бы простейший тест Колмогорова-Смирнова на равномерность распределения. Если надо восстанавливать состояние ГПСЧ по его выходу - всегда есть SplitMix64, там при фиксированном инкременте оно безо всякого ИИ восстанавливается по одному 64-битному целому. При неизвестном - по двум. Если взять AES-128 с известным фиксированным ключом, то 128-битный счётчик будет однозначно восстановлен по 128-битному блоку.
ГПСЧ на основе MurMur3 перестает проходить многие статистические тесты, если на входе поменять seed и counter местами. Это означает, что если разным потокам дать разные сиды, то между ними возможны скрытые корреляции. 128-битный линейный конгруэнтный генератор в таком виде неплох, но проваливает два теста - TMFn из PractRand >= 0.94 и Birthday Spacings with Decimation из SmokeRand.
Здорово, было бы интересно прочитать, особенно если получится про "ненормальное программирование" и трюки. Правда, у меня после плотной работы с ГПСЧ возникло весьма странное их понимание: я стал считать трюкачеством любые некриптографические генераторы.
Dieharder не очень чувствителен, комбинация из TestU01 и PractRand хотя бы на 2 ТиБ куда лучше. И то иногда они порой пропускают игрушечные генераторы. Ещё важной характеристикой ГПСЧ я считаю то, во сколько раз он быстрее ChaCha8 и AES128 на данной платформе.
О генераторах из статьи: RanQ1 ещё встречается под другим названием - xorshift64*, и с немного другими константами. У всех его версий есть статистические дефекты в младших битах, хотя в зависимости от их констант выраженность может различаться. TinyMT32 и даже RC4 тоже PractRand не пройдут. Кстати, на RC4 похожи ISAAC и ISAAC64, и они раз в 5 быстрее его и ощутимо качественнее.
Среди ГПСЧ есть ещё очень интересная разновидность линейного конгруэнтного генератора - MWC, Multiply With Carry. Они с помощью некоторых арифметических трюков эмулируют деление на большой простой делитель. Генераторы из них получаются быстрые и довольно приличные. Вот хорошие примеры:
Портабельные реализации шифров помедленнее, у меня ChaCha8 на C99 работает со скоростью где-то 2 cpb (1 ГиБ/с). Измерял собственную реализацию для своего бенчмарка:
Большинство алгоритмов из Вашего бенчмарка у меня тоже есть, правда, xorshift64, lehmer64, ranq1 и mulberry32 мои статистические тесты не пройдут.
Вообще при подробном знакомстве с темой ГПСЧ у меня сложилось довольно странное впечатление: необъяснимое игнорирование симметричных шифров в этой роли, хотя они уже давно довольно быстрые. Если бы к ГПСЧ подходили бы столь же строго, как к реализации sin или cos, то некриптографические алгоритмы были бы аналогом inverse square root из Quake III, а шифры были бы в учебниках по статистике и численным методам.
Обратил внимание на то, что в бенчмарках нет таких ГПСЧ, как ChaCha8, AES и Speck. При аккуратной реализации с использованием интринсик компилятора они на x86 разгоняются до примерно 1 cpb, что вообще поднимает философский вопрос о целесообразности некриптографических ГПСЧ в большинстве ситуаций.
О gjf64: никогда не слышал такого названия. Интересно, где именно Вы его встретили? Этот алгоритм, похоже, больше известен под названием xorshift128+ и взят отсюда: https://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
О Tyche: то, что публиковалось под этим названием (https://link.springer.com/chapter/10.1007/978-3-642-31464-3_10) - это не LFSR, а нелинейный генератор на основе преобразования из ChaCha. У Вас же действительно какая-то модификация xorshift. Но откуда именно тогда были взяты параметры?
Для Counter-Based PRNG их сложно подбирать, для LFSR - чуть проще, но всё равно сложновато, тестировать надо. И проверять межпоточные корреляции. А многопоточный генератор с состоянием короче 128 бит вряд ли вообще имеет смысл. 128-битный генератор - вообще может в регистры процессора поместиться. Даже несколько копий ChaCha - и то помещается. Вообще к вызову ГПСЧ надо относиться скорее как к вызову спецфункции вроде гамма-функции или функции ошибок, т.е. как к полноценному численному методу, где корректность может быть важнее скорости. Тем более ГПСЧ со 128 битами состояния и так бывают очень быстрые.
Какие именно константы, алгоритма или seed? Константы алгоритма далеко не всегда можно менять. Если же свои seed, то перекрытие будет выглядеть как появление одинаковых и длинных последовательностей в разных потоках. Если у ГПСЧ состояние хотя бы 128 бит, то в разных неперекрывающихся потоках вполне возможны одинаковые 64-битные значения (случайные коллизии).
Да, второй проще, и если нужно очень быстро - то AVX2-версия ThreeFry легко разгоняется до 0.4-0.5 cpb. AES, кстати, тоже можно использовать как счётчиковй ГПСЧ.Но xoroshiro с матрицами перехода раза в 2 быстрее, хотя такая экстремальная производительность нужна редко.
Они позволяют мгновенно "промотать" состояние генератора на
или даже
итераций вперёд и получить гарантированно неперекрывающиеся потоки псевдослучайных чисел в параллельных программах. Альтернативный подход - Counter Based PRNG (т.е. счётчиковые ГПСЧ) вроде Philox или ChaCha, которые дают прямой доступ к любому члену последовательности по его номеру за
.
Эти всптроенные в процессор генераторы могут быть в разы медленнее хорошо оптимизированной под SIMD ChaCha и уж тем более xoroshiro++. Также результат невоспроизводим, и были случаи отказов этой инструкции на каких-то процессорах, хотя и лет 10-15 назад. Для
std::random_deviceиндетерминизм стандартом языка не гарантируется. Думаю, что системный криптогенератор (/dev/urandomи его аналоги под Windows) - это намного проще и надёжнее. В SmokeRand я для инициализации ГПСЧ при возможности используюrdseed, но только для подачи вместе с выходом криптогенератора, текущим временем и т.п. в хеш-функцию Blake2s, 256-битный хеш - это ключ для ChaCha20.И в C++ "под капотом" тех же
mt19937илиmt19937_64очень даже понятно, что. Там алгоритмы специфицированы в стандарте.Если использовать 8-битный алгоритм, то начиная с 10-16 объектов начнутся коллизии идентификаторов. Ведь такой ГПСЧ не может выдать больше 256 уникальных многобайтных идентификаторов.
Дискретный аналог логистического отображения - это скорее функция Климова-Шамира, ГПСЧ на её основе имеет полный период, математически доказанный. У младших бит малый период как у линейного конгруэнтного генератора с
. Можно легко в этом убедиться экспериментально с помощью такого кода:
Вообще если нужен игрушечный генератор размером 8-16 бит - то проще всего использовать xorshift Марсальи. Там низкопериодичных бит нет вообще, период для правильно подобранных параметров для 8 и 16 бит будет 255 и 65535 соответственно.
Имел в виду то, что существуют простые способы выявить статистические аномалии в выдаваемой вихрем Мерсенна последовательности. Этот ГПСЧ сводится к умножению двоичного вектора длиной около 2 КиБ на двоичную матрицу, вместо умножения - операция AND, вместо сложения - XOR (насколько я знаю, эти операции - из поля GF(2)). И матрица там весьма разреженная. Если взять выходную последовательность из 32-битных членов и выбрать какой-то отдельный бит из каждого из них, то эти биты - продукт LFSR длиной 19937. Что и выявляет алгоритм Берлекэмпа-Месси, похожий на оптимизированный под конкретную задачу метод Гаусса. Можно ещё генерировать случайные двоичные матрицы и их ранги считать, но это значительно дольше. Про другие выявленные дефекты вихря Мерсенна написано в этой статье: https://arxiv.org/abs/2512.21678 .
Тест linear complexity из TestU01 и SmokeRand основан на алгоритме Берлекэмпа-Месси. Вихрь Мерсенна этот тест проваливает.
Тест Matrix Rank (или BRank) из TestU01, PractRand и SmokeRand - это расчёт ранга двоичной матрицы. Только в PractRand матрицы достаточно большие для провала теста вихрем Мерсенна.
Какие преимущества у подхода с синтаксическим деревом по сравнению с наивным подходом с дуальными числами, в котором граф или дерево не строятся, но все арифметические операции над числами с плавающей запятой превращаются в операции над их векторами?
О формуле
: она верная и легко выводится "на бумажке", но на практике не очень удобная из-за появления квадратов элементов из матрицы плана эксперимента
. Проще напрямую применить преобразование Гивенса или Хаусхолдера (QR-разложение) к переопределенной системе
, оно медленнее, но численно устойчивее, т.к. там нет явного обращения матрицы
.
У F-теста есть хитрая особенность: он может показывать значимость регрессии даже при незначимости всех её коэффициентов. Речь про переобучение модели.
Всё это очень легко обобщается на полиномиальную или логистическую регрессию.
Обязательно ли наличие в регрессии константы для корректности формулы
?
Для малых выборок это может сработать, но если симуляция потребляет терабайты, то место на диске кончится. Да и читать с диска медленнее, чем генерировать на ходу в памяти. Также аккуратно реализованные AES или ChaCha на стороне пользователя в несколько раз быстрее
/dev/urandom, и их удобно параллелить.Если речь про C++ (C++11 и выше) - то использовать вместо неё стандартную библиотеку языка, там есть вихрь Мерсенна, хотя он и не очень удобен для параллельных программ (для них удобнее Philox или ChaCha). Если чистый Си - то написать свою функцию rand. Помимо генераторов из статьи ещё хороши xoroshiro++/**, образцовые реализации с матрицами перехода опубликованы на сайте автора. Матрицы перехода нужны для многопоточности.
С логистическим отображением есть проблема: оно требует вещественных чисел, с которыми компьютер работать не может. И вместо логистического отображения в программе будет какое-то необратимое преобразование 64-битного целого числа (с точки зрения типов данных языка программирования это будет тип double, но в памяти машины оно всё равно выглядит как последовательность бит). Если преобразование необратимое - то средний период генератора будет
с возможностью попадания в очень короткие циклы. Т.е. пользоваться таким ГПСЧ для расчётов нельзя, даже функция rand() из glibc будет и то приличнее, у неё хотя бы доказанный (и большой) период есть и она скорее всего пройдет хотя бы простейший тест Колмогорова-Смирнова на равномерность распределения. Если надо восстанавливать состояние ГПСЧ по его выходу - всегда есть SplitMix64, там при фиксированном инкременте оно безо всякого ИИ восстанавливается по одному 64-битному целому. При неизвестном - по двум. Если взять AES-128 с известным фиксированным ключом, то 128-битный счётчик будет однозначно восстановлен по 128-битному блоку.
ГПСЧ на основе MurMur3 перестает проходить многие статистические тесты, если на входе поменять seed и counter местами. Это означает, что если разным потокам дать разные сиды, то между ними возможны скрытые корреляции. 128-битный линейный конгруэнтный генератор в таком виде неплох, но проваливает два теста - TMFn из PractRand >= 0.94 и Birthday Spacings with Decimation из SmokeRand.
Здорово, было бы интересно прочитать, особенно если получится про "ненормальное программирование" и трюки. Правда, у меня после плотной работы с ГПСЧ возникло весьма странное их понимание: я стал считать трюкачеством любые некриптографические генераторы.
Dieharder не очень чувствителен, комбинация из TestU01 и PractRand хотя бы на 2 ТиБ куда лучше. И то иногда они порой пропускают игрушечные генераторы. Ещё важной характеристикой ГПСЧ я считаю то, во сколько раз он быстрее ChaCha8 и AES128 на данной платформе.
О генераторах из статьи: RanQ1 ещё встречается под другим названием - xorshift64*, и с немного другими константами. У всех его версий есть статистические дефекты в младших битах, хотя в зависимости от их констант выраженность может различаться. TinyMT32 и даже RC4 тоже PractRand не пройдут. Кстати, на RC4 похожи ISAAC и ISAAC64, и они раз в 5 быстрее его и ощутимо качественнее.
Среди ГПСЧ есть ещё очень интересная разновидность линейного конгруэнтного генератора - MWC, Multiply With Carry. Они с помощью некоторых арифметических трюков эмулируют деление на большой простой делитель. Генераторы из них получаются быстрые и довольно приличные. Вот хорошие примеры:
https://cas.ee.ic.ac.uk/people/dt10/research/rngs-gpu-mwc64x.html
https://prng.di.unimi.it/MWC128.c (в нем предлагаемый авторами скремблер лучше включить)
Портабельные реализации шифров помедленнее, у меня ChaCha8 на C99 работает со скоростью где-то 2 cpb (1 ГиБ/с). Измерял собственную реализацию для своего бенчмарка:
https://github.com/alvoskov/SmokeRand/blob/main/generators/chacha.c
Большинство алгоритмов из Вашего бенчмарка у меня тоже есть, правда, xorshift64, lehmer64, ranq1 и mulberry32 мои статистические тесты не пройдут.
Вообще при подробном знакомстве с темой ГПСЧ у меня сложилось довольно странное впечатление: необъяснимое игнорирование симметричных шифров в этой роли, хотя они уже давно довольно быстрые. Если бы к ГПСЧ подходили бы столь же строго, как к реализации sin или cos, то некриптографические алгоритмы были бы аналогом inverse square root из Quake III, а шифры были бы в учебниках по статистике и численным методам.
Обратил внимание на то, что в бенчмарках нет таких ГПСЧ, как ChaCha8, AES и Speck. При аккуратной реализации с использованием интринсик компилятора они на x86 разгоняются до примерно 1 cpb, что вообще поднимает философский вопрос о целесообразности некриптографических ГПСЧ в большинстве ситуаций.