В поисках источника алгоритма

Question

Просматривая мои 3 тома TAOCP, я не могу найти источник короткой случайной последовательности:

// Seed always in 1..0x10000
Seed = (Seed * const) % 0x10001

Был также алгоритм и, возможно, программа MIX для проверки const, так что будут возвращены все 2^16 значений. По крайней мере, это то, что я помню. Также в той же самой общей области был факт, что вышеупомянутая рекурсия работает, потому что (2^16)+1 является простым, но увы, ни (2^32)+1, ни (2^64)-1 не являются простыми числами.

FWIW, замена const на iconst = 1/const (mod 0x10001) создает последовательность в обратном порядке. Т.е. const*iconst%0x10001 = 1

Answer 1

Алгоритм представляет собой вариант линейных конгруэнтных генераторов(LCG), известный как мультипликативный линейный конгруэнтный генератор с основным модулем (PMMLCG - см. "Имитационное моделирование и анализ, 5e", стр.400), который также иногда называют генератором Лемера. Обе ссылки, которые я предоставил, дают общие параметры, первая ссылка дает правила для выбора параметров, которые дадут полный цикл. Однако наличие полного цикла не является достаточным условием для того, чтобы иметь хороший генератор, как IBM безропотно обнаружил в печально известной RANDU.

Я настоятельно призываю вас использовать только те алгоритмы, которые были хорошо протестированы, и это поразительно сложно сделать правильно. В настоящее время широко доступны хорошо изученные и легко доступные алгоритмы, которые намного лучше, чем любой LCG.