Посоветуйте статьи про построение хороших псевдослучайных последовательностей с зерном.
И примеры, если есть.
Штатная CTR-шная функция вообще линейная, как оказалось
Здравствуйте, netch80, Вы писали:
N>Там многие линейные, и это не так плохо, как кажется.
У меня с ним возникла такая проблема: есть "линейка" объектов, каждый раз обращаясь к определённому элементу мне нужно вычислить для него один и тот же рандом в зависимости от seed-а. Попытался написать свою функцию, просто из головы, большими числами, xor-ами, остатками и так далее. Заметил, что если по линейке к зерну прибавлять единицу (т.е. зерно для каждого элемента: индекс + базовое_зерно), то часто получаются повторения или схожести. Грешил на функцию (и правильно делал), игрался с числами, игрался со сдвигами между индексом элемента и зерном(умножал зерно на число), а потом просто подставил штатный rand и удивился... там, если зерно подставлять 0, 1, 2, 3... числа у меня после отсечения по модулю идут примерно как x*k + c.
Здравствуйте, Pzz, Вы писали:
CEM>>Посоветуйте статьи про построение хороших псевдослучайных последовательностей с зерном.
Pzz>Я бы взял какой-нибудь из стандартных криптографических генераторов.
Но у них же слишком хороший рандом? Или есть рандомы, основанные на зерне? Можно какой-нибудь пример?
Здравствуйте, CEMb, Вы писали:
N>>Там многие линейные, и это не так плохо, как кажется.
CEM>У меня с ним возникла такая проблема: есть "линейка" объектов, каждый раз обращаясь к определённому элементу мне нужно вычислить для него один и тот же рандом в зависимости от seed-а. Попытался написать свою функцию, просто из головы, большими числами, xor-ами, остатками и так далее. Заметил, что если по линейке к зерну прибавлять единицу (т.е. зерно для каждого элемента: индекс + базовое_зерно), то часто получаются повторения или схожести. Грешил на функцию (и правильно делал), игрался с числами, игрался со сдвигами между индексом элемента и зерном(умножал зерно на число), а потом просто подставил штатный rand и удивился... там, если зерно подставлять 0, 1, 2, 3... числа у меня после отсечения по модулю идут примерно как x*k + c.
Верно, они так и пойдут. Более того, это свойственно чуть ли не всем подобным алгоритмам предсказуемых ГПСЧ, даже самым продвинутым. Но после первых нескольких значений, сгенерированных без смены зерна, видимая предсказуемость теряется.
Попробуйте применить какой-то иной подход. Например, можно взять один такой генератор для фиксированного стартового зерна, пропустить значений 10 и последующие брать уже как целевые зёрна.
Или представления ряда последовательных чисел пропустить через что-то вроде md5 и уже его выход использовать для инициализации целевого генератора.
Здравствуйте, CEMb, Вы писали:
Pzz>>Я бы взял какой-нибудь из стандартных криптографических генераторов.
CEM>Но у них же слишком хороший рандом? Или есть рандомы, основанные на зерне? Можно какой-нибудь пример?
Здравствуйте, Pzz, Вы писали:
CEM>>Но у них же слишком хороший рандом? Или есть рандомы, основанные на зерне? Можно какой-нибудь пример? Pzz>А что значит, слишком хороший?
Возможно, ТС под «слишком хороший» имел в виду «недетерминированный», последовательность бит которого нельзя воспроизвести при последующем запуске.
Crypto-PRNG в общем случае использовать, конечно, не нужно. Они медленнее, чем обычные PRNG, так как должны предоставить несколько дополнительных гарантий, которые в обычной жизни не нужны.
Здравствуйте, Qbit86, Вы писали:
Q>Возможно, ТС под «слишком хороший» имел в виду «недетерминированный», последовательность бит которого нельзя воспроизвести при последующем запуске.
Ну его завсегда можно проинициализировать фиксированным сидом.
Q>Crypto-PRNG в общем случае использовать, конечно, не нужно. Они медленнее, чем обычные PRNG, так как должны предоставить несколько дополнительных гарантий, которые в обычной жизни не нужны.
Они не настолько уж медленные, с учетом развития железа за последние годы. А какой-нибудь RC4 в качестве генератора случайных чисел, поди, побыстрее стандарных "математических" будет.
Здравствуйте, CEMb, Вы писали:
CEM>У меня с ним возникла такая проблема: есть "линейка" объектов, каждый раз обращаясь к определённому элементу мне нужно вычислить для него один и тот же рандом в зависимости от seed-а. Попытался написать свою функцию, просто из головы, большими числами, xor-ами, остатками и так далее. Заметил, что если по линейке к зерну прибавлять единицу (т.е. зерно для каждого элемента: индекс + базовое_зерно), то часто получаются повторения или схожести. Грешил на функцию (и правильно делал), игрался с числами, игрался со сдвигами между индексом элемента и зерном(умножал зерно на число), а потом просто подставил штатный rand и удивился... там, если зерно подставлять 0, 1, 2, 3... числа у меня после отсечения по модулю идут примерно как x*k + c.
Ну берем, например, какой-нибудь блочный шифр. Seed используем в качестве ключа. Номер объекта, дополнив его нулями до размера блока, подаем шифру на вход. Из выхода берем нужное количество бит.
Получающиеся псевдослучайные числа будут равномерно распределены и малопредсказуемы. Но они будут в диапазоне от 0 до 2^N — 1, где N — выбраное количество бит. Загнать их в произвольный диапазон, не теряя равномерного распределения, существенно сложнее.
Я бы взял AES-128, он на большинстве современных машинок считается довольно быстро, благодаря аппаратной поддержке.
Здравствуйте, netch80, Pzz, Вы писали:
Pzz>Я бы взял AES-128, он на большинстве современных машинок считается довольно быстро, благодаря аппаратной поддержке.
Насколько быстро? Мне, кроме всего прочего, нужен реал-тайм. Чем быстрее, тем лучше. Примерно как выводить рандомную картинку на весь экран без тормозов.
Думал ещё попробовать Crypto++.
Здравствуйте, CEMb, Вы писали:
CEM>Думал ещё попробовать Crypto++.
Если у тебя C++, попробуй стандартный Mersenne Twisterstd::mt19937, прежде чем заморачиваться самопальной реализацией.
CEM>Штатная CTR-шная функция вообще линейная, как оказалось
Здравствуйте, CEMb, Вы писали:
CEM>Насколько быстро? Мне, кроме всего прочего, нужен реал-тайм. Чем быстрее, тем лучше. Примерно как выводить рандомную картинку на весь экран без тормозов. CEM>Думал ещё попробовать Crypto++.
Ну, моя машинка шифрует AES'ом ~5 миллионов блоков в секунду, причем делает это софтверно, в моем процессоре еще нет AES'овского ускорителя.
