Что такое простая формула для последовательности без итераций случайных чисел?

Question

Я хотел бы иметь функцию f (x), которая дает хорошие псевдослучайные числа в равномерном распределении по значению x. Я знаю линейные конгруэнтные генераторы, однако они работают в итерациях, то есть я предоставляю начальное семя, а затем получаю последовательность случайных значений один за другим. Это не то, что я хочу, потому что, если вы хотите получить, допустим, 200000-е число в последовательности, я должен вычислить числа 1 ... 199999. Мне нужна функция, которая задается одной простой формулой, которая использует основные операции, такие как + , *, mod и т. д. Я также знаю о хэш-функциях, но я не нашел того, что соответствует этим потребностям. Я мог бы придумать какую-то функцию самостоятельно, но я бы хотел использовать что-то, что было проверено, чтобы дать достойные псевдослучайные значения. Используется ли что-нибудь подобное?

Answer 1

Вы можете рассматривать мультипликативные конгруэнтные генераторы. Это линейные конгруэнции без аддитивной константы: X _{i + 1} = aX _i% c для подходящих констант a и c. Расширение этого в течение нескольких итераций будет убедить вас, что X _к = а ^к X % С, где X является вашим начальным значением. Это можно рассчитать по времени O (log (k)), используя fast modular exponentiation. Не нужно вычислять первые 199,999, чтобы получить значение 200 000 ^th, вы можете найти его в чем-то пропорциональном примерно 18 шагам.

Answer 2

На самом деле, для LCG с константой добавки он также работает. Существует статья Ф. Брауна «Генерация случайных чисел с произвольным шагом», Trans. Am. Nucl. Soc. (Ноябрь 1994 г.). Основываясь на этом документе, существует разумный LCG с достойным качеством и функцией log2 (N), используемой известным пакетом MCNP5 в Монте-Карло. Сообщение C++ здесь https://github.com/Iwan-Zotow/LCG-PLE63/. Дальнейшее развитие, если эта идея (RNG с логарифмическим пропуском) является довольно приличным семейством генераторов на http://www.pcg-random.org/

Answer 3

Вы можете использовать простой алгоритм шифрования, который может шифровать числа 1, 2, 3, ... Так как шифрование является обратимым , каждый номер входа будет иметь уникальный выход. 200000-й номер в вашей последовательности - encrypt(key, 200000). Используйте DES для 64-битных номеров, AES для 128-битных номеров, и вы можете катить свой собственный простой Feistel cipher для 32-битных или 16-разрядных номеров.