Мне нужен некоторый хороший генератор псевдослучайных чисел, который может быть вычислен как чистая функция из ее предыдущего вывода без любого сокрытия состояния. Под "хорошим" я имею в виду:
Я должен смочь параметризовать генератор таким способом который выполнение его для 2^n
повторения с любыми параметрами (или с некоторым большим подмножеством их) должны покрыть все или почти все значения между 0
и 2^n - 1
, где n
число битов в выходном значении.
Вывод комбинированного генератора 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)
- разрядная международная Параметризация, требуемая выбрать тот уникальный путь.
Я желаю слишком много?
Вы можете использовать любой блочный шифр с фиксированным ключом. Чтобы сгенерировать следующее число, расшифруйте текущее, увеличьте его и снова зашифруйте. Поскольку блочные шифры относятся к числу 1:1, они обязательно переберут все числа в выходной области перед повторением.
Попробуйте LFSR
Все, что вам нужно, это список примитивных многочленов.
Период генерации конечного поля таким образом генерирует поле размером 2 ^ n-1. Но вы можете обобщить эту процедуру, чтобы сгенерировать что-нибудь с периодом k ^ n-1.
Я не видел, чтобы это реализовано, но все, что вам нужно реализовать, - это сдвиг чисел на малое число s> n, где gcd (s, 2 ^ n-1) == 1. gcd обозначает наибольший общий делитель