Запись 36-разрядного генератора случайных чисел

Я пишу приложение в среде с функциями

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

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

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

Итак, я ищу либо набор чисел 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 (Symbolic Stream Generator) в операционной системе UNISYS 2200 под управлением EXEC 8.

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

Ответы

Ответ 1

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

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-битные числа. Фокус в том, что семя расщепляется на hi и lo детали, а конечное случайное число генерируется суммированием частей.

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

Ответ 2

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

x_i (n) = a x_i (n-1) + p_i (mod 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 случайных генератора должны быть совершенно независимыми, поэтому стратегия должна быть вполне удовлетворительной.

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

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