Генерация случайных чисел или перестановок полного периода / полного цикла Аналогично LCG, но без нечетных / четных
Я хочу генерировать псевдослучайные числа / перестановки, которые «занимают» полный период или полный цикл в пределах диапазона. Обычно «Линейный конгруэнтный генератор» (LCG) может использоваться для генерации таких последовательностей с использованием формулы, такой как:
X = (a*Xs+c) Mod R
Где Xs - начальное число, X - результат, a и c - относительно простые константы, а R - максимум (диапазон).
(По полному периоду / полному циклу, Я имею в виду, что константы могут быть выбраны так, что любой X будет встречаться только один раз в некоторой случайной / перестановочной последовательности и будет находиться в диапазоне от 0 до R-1 или от 1 до R).
LCG почти удовлетворяет всем моим потребностям , Проблема, которую я имею с LCG, заключается в неслучайности нечетного / четного результата, то есть: для начального числа Xn результат X будет чередоваться нечетным / четным.
Вопросы:
Кто-нибудь знает, как создать что-то подобное, что не будет альтернативный нечетный / четный?
Я полагаю, что «составной LCG» может быть построен, но у меня нет подробности. Может кто-нибудь дать Пример этого CLCG?
Есть ли альтернативные формулы, которые может встретиться с деталями выше и ограничения ниже?
Ограничения:
- Я хочу что-то, основанное на простом формула на основе семян. то есть: чтобы получить следующий номер, я предоставляю семя и получить следующее «случайное число» в перестановочная последовательность. В частности, Я не могу использовать предварительно рассчитанные массивы. (См. Следующие пункты)
- Последовательность обязательно должна быть «полный период / полный цикл»
- Диапазон R может составлять несколько миллионов или даже 32 бита / 4 млрд.
Вычисление не должно подвергаться переполнению и должно быть эффективным / быстрым, т. е. без больших показателей или десятков умножений / делений.
Последовательность не должна быть ужасно случайной или безопасной - я так и делаю не нужна криптографическая случайность (но может использовать ее, если она жизнеспособна), просто «хорошая» случайность или кажущаяся случайность, без нечетных / четных последовательностей.
Любые мысли приветствуются - спасибо заранее.
ОБНОВЛЕНИЕ: В идеале переменная Range может не быть точной степенью двойки, но должно работать в любом случае.
2 ответа
Если единственной проблемой является чередование четных и нечетных значений, оставьте вычисление изменения состояния без изменений. Перед использованием каждого выхода вы можете либо сдвинуть младшие биты, либо поменять местами биты.
Редактировать:
В варианте с заменой битов (фиксированный шаблон) вы будете продолжать генерировать целые периоды.
Псевдокод исходного LCG:
function rand
state := update(state)
return state
Псевдокод LCG с заменой:
function rand2
state := update(state) -- unchanged state computation
return swapped(state) -- output swapped state
Другим простым, эффективным и понятным ГПСЧ является регистр сдвига с линейной обратной связью. Полного периода легко достичь, следуя шагам, описанным в статье.
РЕДАКТИРОВАТЬ:
Вы можете рассмотреть некоторые методы, разработанные для шифрования с сохранением формата. Я считаю, что их можно легко адаптировать для создания перестановки.