Здорово, было бы интересно прочитать, особенно если получится про "ненормальное программирование" и трюки. Правда, у меня после плотной работы с ГПСЧ возникло весьма странное их понимание: я стал считать трюкачеством любые некриптографические генераторы.
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, что вообще поднимает философский вопрос о целесообразности некриптографических ГПСЧ в большинстве ситуаций.
std::mt19937 - несомненно, достаточно почти для всего, кроме параллельного программирования и случаев, где критичны провалы тестов "линейная сложность" и "ранг матрицы". А вот в rand() в большинстве случаев находятся жуткие алгоритмы из категории "выкрасить и выбросить". И в man-страницу glibc следовало бы добавить предупреждение о том, что алгоритм плохой и не подчиняется равномерному распределению.
Со специфичностью криптографии не согласен: поточные шифры следовало бы, наверное, использовать как ГПСЧ по умолчанию почти всегда и везде, и включить в учебники по теорверу, матстату и численным методам. Ну, может, PCG, SFC и xoroshiro++ оставить для случаев, где реально надо такты считать.
У SFC и JSF есть 64-битные версии, они обычно в 1.5-2 раза быстрее. У упрощённого ГПСЧ на основе SHA1, JSF и особенно у Romu есть неочевидное свойство: нет математически доказанного периода, теоретически возможны короткие циклы. И, кстати, не может ли этот ГПСЧ из SHA1 вообще в Counter-Mode работать, т.е. скремблировать банальные номера блоков от 0 до 2^64 - 1 и отдавать сразу все внутреннее состояние, что ускорило бы его? Но тут надо уже в PractRand проверять, т.к. число раундов урезано.
А не проще ли представить это иначе: результаты измерений - это случайные величины, подчиняющиеся какому-то распределению? И доверительные интервалы - это эмпирические оценки параметров этого распределения. Недаром же сейчас вместо понятия "погрешность" всё чаще используют понятие "неопределённость".
Это в общем-то философские, а не научные вопросы, на которые нет однозначного ответа. В прикладном плане случайная последовательность - это то, что мы не можем аппроксимировать какой-то формулой, т.е. предсказать следующий бит с вероятностью выше 50%. А вот с псевдослучайностью ситуация интереснее: у многих генераторов из стандартных библиотек их seed можно достаточно быстро определить по выходу каким-то алгоритмом. Но у наиболее качественных ГПСЧ человечество не знает способа это сделать без полного перебора seeds, и такие генераторы называются поточными шифрами. Само существование поточных шифров показывает то, что отличить случайность от детерминизма для стороннего наблюдателя может быть очень сложно.
Здорово, было бы интересно прочитать, особенно если получится про "ненормальное программирование" и трюки. Правда, у меня после плотной работы с ГПСЧ возникло весьма странное их понимание: я стал считать трюкачеством любые некриптографические генераторы.
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, что вообще поднимает философский вопрос о целесообразности некриптографических ГПСЧ в большинстве ситуаций.
std::mt19937 - несомненно, достаточно почти для всего, кроме параллельного программирования и случаев, где критичны провалы тестов "линейная сложность" и "ранг матрицы". А вот в rand() в большинстве случаев находятся жуткие алгоритмы из категории "выкрасить и выбросить". И в man-страницу glibc следовало бы добавить предупреждение о том, что алгоритм плохой и не подчиняется равномерному распределению.
Со специфичностью криптографии не согласен: поточные шифры следовало бы, наверное, использовать как ГПСЧ по умолчанию почти всегда и везде, и включить в учебники по теорверу, матстату и численным методам. Ну, может, PCG, SFC и xoroshiro++ оставить для случаев, где реально надо такты считать.
У SFC и JSF есть 64-битные версии, они обычно в 1.5-2 раза быстрее. У упрощённого ГПСЧ на основе SHA1, JSF и особенно у Romu есть неочевидное свойство: нет математически доказанного периода, теоретически возможны короткие циклы. И, кстати, не может ли этот ГПСЧ из SHA1 вообще в Counter-Mode работать, т.е. скремблировать банальные номера блоков от 0 до 2^64 - 1 и отдавать сразу все внутреннее состояние, что ускорило бы его? Но тут надо уже в PractRand проверять, т.к. число раундов урезано.
А не проще ли представить это иначе: результаты измерений - это случайные величины, подчиняющиеся какому-то распределению? И доверительные интервалы - это эмпирические оценки параметров этого распределения. Недаром же сейчас вместо понятия "погрешность" всё чаще используют понятие "неопределённость".
Это в общем-то философские, а не научные вопросы, на которые нет однозначного ответа. В прикладном плане случайная последовательность - это то, что мы не можем аппроксимировать какой-то формулой, т.е. предсказать следующий бит с вероятностью выше 50%. А вот с псевдослучайностью ситуация интереснее: у многих генераторов из стандартных библиотек их seed можно достаточно быстро определить по выходу каким-то алгоритмом. Но у наиболее качественных ГПСЧ человечество не знает способа это сделать без полного перебора seeds, и такие генераторы называются поточными шифрами. Само существование поточных шифров показывает то, что отличить случайность от детерминизма для стороннего наблюдателя может быть очень сложно.