Там “хороший” PRNG генерация значения без скрытого состояния?

Мне нужен некоторый хороший генератор псевдослучайных чисел, который может быть вычислен как чистая функция из ее предыдущего вывода без любого сокрытия состояния. Под "хорошим" я имею в виду:

  1. Я должен смочь параметризовать генератор таким способом который выполнение его для 2^n повторения с любыми параметрами (или с некоторым большим подмножеством их) должны покрыть все или почти все значения между 0 и 2^n - 1, где n число битов в выходном значении.

  2. Вывод комбинированного генератора n + p биты должны покрыть все или почти все значения между 0 и 2^(n + p) - 1 если я выполняю его для 2^n повторения для каждой возможной комбинации его параметров, где p число битов в параметрах.

Например, LCG может быть вычислен как чистая функция, и он может удовлетворить первому условию, но он не может встретить второй. Скажите, у нас есть 32-разрядный LCG, m = 2^32 и это постоянно, наш p = 64 (два 32-разрядных параметра a и c), n + p = 96, таким образом, мы должны посмотреть данные тремя ints от вывода для удовлетворения второму условию. К сожалению, условие не может быть, встречаются из-за строго переменной последовательности четного и нечетного ints в выводе. Для преодоления этого скрытое состояние должно быть представлено, но это делает функцию не чистой и нарушает первое условие (долго скрытый период).

Править: Строго говоря я хочу семейство функций, параметризованных p биты и с полным состоянием n биты, каждый генерирующий все возможные двоичные строки p + n биты уникальным "randomish" способом, не просто непрерывно увеличивая (p + n)- разрядная международная Параметризация, требуемая выбрать тот уникальный путь.

Я желаю слишком много?

7
задан actual 21 May 2010 в 05:51
поделиться

2 ответа

Вы можете использовать любой блочный шифр с фиксированным ключом. Чтобы сгенерировать следующее число, расшифруйте текущее, увеличьте его и снова зашифруйте. Поскольку блочные шифры относятся к числу 1:1, они обязательно переберут все числа в выходной области перед повторением.

2
ответ дан 7 December 2019 в 16:39
поделиться

Попробуйте LFSR
Все, что вам нужно, это список примитивных многочленов.
Период генерации конечного поля таким образом генерирует поле размером 2 ^ n-1. Но вы можете обобщить эту процедуру, чтобы сгенерировать что-нибудь с периодом k ^ n-1.

Я не видел, чтобы это реализовано, но все, что вам нужно реализовать, - это сдвиг чисел на малое число s> n, где gcd (s, 2 ^ n-1) == 1. gcd обозначает наибольший общий делитель

1
ответ дан 7 December 2019 в 16:39
поделиться
Другие вопросы по тегам:

Похожие вопросы: