Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток AI и ML доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 25
А как мигрировать с rand() на современный ГПСЧ в существующем проекте?
Если речь про C++ (C++11 и выше) - то использовать вместо неё стандартную библиотеку языка, там есть вихрь Мерсенна, хотя он и не очень удобен для параллельных программ (для них удобнее Philox или ChaCha). Если чистый Си - то написать свою функцию rand. Помимо генераторов из статьи ещё хороши xoroshiro++/**, образцовые реализации с матрицами перехода опубликованы на сайте автора. Матрицы перехода нужны для многопоточности.
А как эти матрицы помогают в многопоточности?
Они позволяют мгновенно "промотать" состояние генератора на
или даже
итераций вперёд и получить гарантированно неперекрывающиеся потоки псевдослучайных чисел в параллельных программах. Альтернативный подход - Counter Based PRNG (т.е. счётчиковые ГПСЧ) вроде Philox или ChaCha, которые дают прямой доступ к любому члену последовательности по его номеру за
.
Второй вариант выглядит более элегантно.
Да, второй проще, и если нужно очень быстро - то AVX2-версия ThreeFry легко разгоняется до 0.4-0.5 cpb. AES, кстати, тоже можно использовать как счётчиковй ГПСЧ.Но xoroshiro с матрицами перехода раза в 2 быстрее, хотя такая экстремальная производительность нужна редко.
Кстати, если каждый поток будет иметь свои константы, то они смогут работать независимо и с некоторой вероятностью получать конфликты, но не синхронизироваться, что более случайно, чем гарантированное отсутствие повторов за период.
Какие именно константы, алгоритма или seed? Константы алгоритма далеко не всегда можно менять. Если же свои seed, то перекрытие будет выглядеть как появление одинаковых и длинных последовательностей в разных потоках. Если у ГПСЧ состояние хотя бы 128 бит, то в разных неперекрывающихся потоках вполне возможны одинаковые 64-битные значения (случайные коллизии).
Алгоритма, конечно. Думаю достаточно было бы иметь семейство из десятка-другого констант. А вот состояние в 2 кеш-линии как-то совсем уже многовато.
Для Counter-Based PRNG их сложно подбирать, для LFSR - чуть проще, но всё равно сложновато, тестировать надо. И проверять межпоточные корреляции. А многопоточный генератор с состоянием короче 128 бит вряд ли вообще имеет смысл. 128-битный генератор - вообще может в регистры процессора поместиться. Даже несколько копий ChaCha - и то помещается. Вообще к вызову ГПСЧ надо относиться скорее как к вызову спецфункции вроде гамма-функции или функции ошибок, т.е. как к полноценному численному методу, где корректность может быть важнее скорости. Тем более ГПСЧ со 128 битами состояния и так бывают очень быстрые.
/dev/urandom жил, /dev/urandom жив, /dev/urandom будет жить.
Иногда нужна повторяемость результатов ...
pv -s 100M -S /dev/urandom > ./random_for_test1.bin
Для малых выборок это может сработать, но если симуляция потребляет терабайты, то место на диске кончится. Да и читать с диска медленнее, чем генерировать на ходу в памяти. Также аккуратно реализованные AES или ChaCha на стороне пользователя в несколько раз быстрее /dev/urandom, и их удобно параллелить.
Это двоякая проблема. С точки зрения анализа алгоритма плохой генератор случайки - это находка. Когда генератор условно говоря можно скормить ИИ, например, простейший, на логистическом отображении, имеющий бифуркации с островками стабильности и прочие явно не белошумные композиции. В этом случае последовательность предсказуема и с точки зрения решаемой задачи может сильно помочь в отладке, так как каждый раз появляются зависимые новые значения, если без затравки-соли - то постоянно одинаковые. Для криптографии конечно это жесть, но для идентификаторов объектов, различных генерировалок псевдослучайных последовательностей - самое то. Так как ИИ может взять, например, вывод printf и обнаружить в выводе некий шаблон, соответствующий генератору. Для практической задачи - это помогло выловить последовательность объектов где в switch-case необходимо было добавить ещё одну проверку, так как создание одного объекта зависело от другого.
Ничего не понял. Чтобы получать предсказуемые последовательности для отладки, используя при этом аппаратный генератор (который не умеет сидиться фиксированным значением) нужно просто предусмотреть вариант чтения значений из файла вместо генератора.
Зачем для этого использовать заведомо бракованный генератор-то?
для идентификаторов объектов самое то, где "случайность" это имитация жмакания пользователем мышкой. То есть используется псевдо-случайный условно 8-ми битный алгоритм, паттерны которого можно обнаружить в данных для отладки, этакий отпечаток пальцев. Ну как дебаггеры различные делают закладки в памяти а-ля 0x5A5A5A или банальный 0xFFFF. И если имеется несколько таких предсказуемых генераторов объектов, можно отследить их лайфтайм и более-менее разобраться например с их потоками на предмет утечек памяти и др. Интерференция значений прекрасно видна в идентификаторах даже если там используется сумма-разница всего этого дела. Вообщем это одна из эвристик скажем так для отлова гонки данных постфактум, когда они уже испорчены.
С логистическим отображением есть проблема: оно требует вещественных чисел, с которыми компьютер работать не может. И вместо логистического отображения в программе будет какое-то необратимое преобразование 64-битного целого числа (с точки зрения типов данных языка программирования это будет тип double, но в памяти машины оно всё равно выглядит как последовательность бит). Если преобразование необратимое - то средний период генератора будет
с возможностью попадания в очень короткие циклы. Т.е. пользоваться таким ГПСЧ для расчётов нельзя, даже функция rand() из glibc будет и то приличнее, у неё хотя бы доказанный (и большой) период есть и она скорее всего пройдет хотя бы простейший тест Колмогорова-Смирнова на равномерность распределения. Если надо восстанавливать состояние ГПСЧ по его выходу - всегда есть SplitMix64, там при фиксированном инкременте оно безо всякого ИИ восстанавливается по одному 64-битному целому. При неизвестном - по двум. Если взять AES-128 с известным фиксированным ключом, то 128-битный счётчик будет однозначно восстановлен по 128-битному блоку.
именно так и наблюдается на int8. Генератор с логистическим имеет либо пилообразные циклы, либо экспоненты но в конечном итоге всегда выходит на какой-то постоянный установившийся режим островка стабильности (кстати интересный феномен), если int16 то эта же картина только более красивая - генератор всегда застревает на островке или постоянном уровне, до того момента действительно дёргание псевдослучайное. Разумеется картина зависит от начальных условий как в любой нелинейной системе.
Дискретный аналог логистического отображения - это скорее функция Климова-Шамира, ГПСЧ на её основе имеет полный период, математически доказанный. У младших бит малый период как у линейного конгруэнтного генератора с
. Можно легко в этом убедиться экспериментально с помощью такого кода:
#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 матрицы достаточно большие для провала теста вихрем Мерсенна.
Я использую аппаратный ГСЧ типа _rdrand64_step или __builtin_arm_rndr для ARM (поддерживаются всеми современными процами) как асм-вставку или интрисик это прямой физический не псевдо генератор, а не непонятно что под капотом у разных либ. Вроде как std::random_device -тоже это использует.
Эти всптроенные в процессор генераторы могут быть в разы медленнее хорошо оптимизированной под SIMD ChaCha и уж тем более xoroshiro++. Также результат невоспроизводим, и были случаи отказов этой инструкции на каких-то процессорах, хотя и лет 10-15 назад. Для std::random_device индетерминизм стандартом языка не гарантируется. Думаю, что системный криптогенератор ( /dev/urandomи его аналоги под Windows) - это намного проще и надёжнее. В SmokeRand я для инициализации ГПСЧ при возможности использую rdseed, но только для подачи вместе с выходом криптогенератора, текущим временем и т.п. в хеш-функцию Blake2s, 256-битный хеш - это ключ для ChaCha20.
И в C++ "под капотом" тех же mt19937 или mt19937_64 очень даже понятно, что. Там алгоритмы специфицированы в стандарте.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Почему функции rand и lrand48 из glibc годятся только для Тетриса: о случайных числах всерьёз