Запись 36 битного генератора случайных чисел с

Question

Я пишу приложение в среде, которая показывает

• 36-битного комплемента целых
• арифметику ограничивается +, -, *, / и остатком
• нет битовых операций, таких как AND или OR. Но из-за своего дополнения XOR эквивалентно вычитанию, а NOT - отрицанию.
• числовое переполнение является фатальным, поэтому не может использоваться для бесшумного усечения
• Да, есть условные обозначения: IF/THEN/ELSEIF/ELSE/IF.

В идеале, я хотел бы получить 35 или 36 бит случайных целых чисел, но 25 бит тоже хватит.

Мои наивные реализации linear congruential generator работают при переполнении, если они основаны на достаточно больших количествах и производят лишь небольшое количество бит при использовании меньших чисел.

Поэтому я ищу либо набор чисел a, c, m, который даст максимальное количество бит в ограничениях, или разумную адаптацию LCG для объединения двух или более чисел.

В качестве отправной точки, вот что я использую до сих пор:

*DEFINE NextRandom . min,max resultVar 
* . This is a very shitty RNG. The numbers were never checked 
* . for suitability for a long-period linear congruential generator. 
* . But it yields numbers that look vaguely random. 
*CLEAR rq 
*CLEAR rr 
*SET RandZ = RandZ * 169687 + 347011  . RandZ is a global var. 
*DIVIDE RandZ BY 131072 GIVING rq, RandZ . Division yields a remainder 
*DIVIDE RandZ BY 4 GIVING rq 
*SET r0 = +[#,[#],1,1]     . r0 = argument 'min' 
*SET r9 = +[#,[#],1,2]     . r9 = 'max' 
*SET rd = r9 - r0 + 1 
*DIVIDE rq BY rd GIVING rq, rr 
*SET [#,[#],2,1] TO r0 + rr    . return in 'resultVar' 
*ENDDEFINE 

---

В случае, если кто заботится, язык сценариев SSG (Символическое Generator Stream) в операционной системе 2200 мэйнфреймов UNISYS под названием EXEC 8.

---

О критичности: приложение, в котором работает этот RNG, генерирует тестовые данные. Это не шифрование государственных секретов или ядерных ракетных кодов. Поэтому мы говорим о том, что «приятно иметь» и «лучше всего», а не «критически важно». Я был бы доволен улучшением, но не искал окончательного решения.

Answer 1

можно написать линейный конгруэнтный генератор случайных чисел, который никогда не может переполнение, как Стивен К. Парк и и Кит У. Миллер demonstrate в своей работе генераторов случайных чисел: Хорошие трудно найти:

function Random : real; 
        (* Integer Version 2 *) 
const 
    a = 16807; 
    m = 2147483647; 
    q = 127773; (* m div a *) 
    r = 2836; (* m mod a *) 
var 
    lo, hi, test : integer; 
begin 
    hi := seed div q; 
    lo := seed mod q; 
    test := a * lo - r * hi; 
    if test > 0 then 
    seed := test 
    else 
    seed := test + m; 
    Random := seed/m 
end; 

Здесь m - 2^31-1, но вы можете изменить его, чтобы получить 36-битные числа. Фокус в том, что семя делится на привет и ло детали и конечное случайное число генерируется суммированием частей.

Если вам это не нравится, у меня есть lots генераторов случайных чисел в моем блоге. Возможно, один из них сделает то, что вы хотите.

Answer 2

Просто простая идея, я не знаю, если это действительно лучшие: Вы могли бы иметь 3 LCGs на 12 бите с рекурсиями

X_i (п) = а X_i (п-1) + p_i (моды 2^{12})

которые имеют разные простые числа p_i. Если a не слишком большой (скажем, 12 бит), это никогда не будет переполняться. Затем, используя 3 12-битных случайных числа, вы можете сделать 36-разрядное случайное число:

z (n) = x_0 (n) + 2^{12} x_1 (n) + 2^{24} x_2 (n)

Заметим, что если p_i являются простыми и относительно большими, 3 случайные генераторы должны быть совершенно независимыми, поэтому стратегия должна быть вполне удовлетворительной.

Трудность состоит в том, чтобы иметь хороший выбор для.

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