Psuedo-Random-Number-Generator из вычислимого нормального числа - PullRequest
0 голосов
/ 06 марта 2009

Разве не возможно легко построить PRNG таким способом? Почему это не сделано?

То есть, насколько я знаю, мы могли бы просто получить PRNG, который берет семя n. Когда вы запрашиваете случайный бит, он берет n-ю цифру двоичного разложения вычисляемого нормального числа и увеличивает n.

Моей первой мыслью было, что, возможно, мы не нашли вычислимое нормальное число, но у нас есть . Остается мысль, что есть веская причина не - либо есть какое-то свойство PRNG, с которым я не знаком, такого метода не было бы, либо это было бы непрактично, либо иным образом опережало другие методы.

1 Ответ

3 голосов
/ 06 марта 2009

Это сделало бы предсказание результата действительно простым.

Допустим, вы сгенерировали целое число 0x54a30b7f. Если у вас есть 4 ГБ пи (или случайный шум или фактическое нормальное число), есть вероятность, что будет только одно (или, может быть, несколько) вхождение этого конкретного целого числа, и я могу с достаточно высокой вероятностью предсказать все будущие числа. Это серьезная проблема в случае криптографически сильных PRNG. Если вместо простого последовательного сканирования вы используете какую-то функцию, мне просто нужно следовать этой функции, которая, если ее достаточно сложно проследить, превращается в PRNG сама по себе.

Если вас не волнует криптографическая сила вашего генератора, то есть гораздо более компактные способы генерации случайных чисел. Например, Mersenne Twister имеет гораздо больший период, не требуя справочной таблицы 4 ГБ.

...