Writing a 36 bit random number generator

Question

I'm writing an application in an environment that features

• 36 bit one's complement integers
• arithmetic limited to +, -, *, / and remainder
• no bit operations like AND or OR. But because of one's complement, XOR is equivalent to subtraction and NOT to negation.
• numeric overflow is fatal, so can't be used for silent truncation
• Yes, there are conditionals: IF/THEN/ELSEIF/ELSE/IF.

Ideally, I'd like 35 or 36 bit random integers, but 25 bits would suffice too.

My naive implementations of the linear congruential generator run into overflow if based on sufficiently large numbers and produce only a small number of bits when I use smaller numbers.

So I'm looking either for a set of numbers a,c,m that will yield the maximum number of bits in the constraints, or a sensible adaptation of the LCG to combine 2 or more numbers.

As a starting point, here's what I'm using so far:

*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

---

In case anyone cares, the scripting language is SSG (Symbolic Stream Generator) in a UNISYS 2200 mainframe operating system called EXEC 8.

---

On criticality: The app this RNG works in generates test data. It's not encrypting state secrets or the nuclear missile codes. So we're talking about "nice to have" and "best effort" rather than "mission critical." I'd be happy about an improvement but am not looking for the ultimate solution.

Answer 1

It is possible to write a linear congruential random number generator that can never overflow, as Stephen K. Park and and Keith W. Miller demonstrate in their paper Random Number Generators: Good Ones Are Hard To Find:

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;

Here m is 2^31-1, but you could change it to yield 36-bit numbers. The trick is that the seed is split into hi and lo parts and the final random number is generated by summing the parts.

If you don't like that, I have lots of random number generators at my blog. Maybe one of them will do what you want.

Answer 2

Just a simple idea, I don't know if that's really the best: You could have 3 LCGs on 12 bits with recursions

x_i(n) = a x_i(n-1) + p_i (mod 2^{12})

which have different primes p_i. If a is not too large (say 12-bit), this will never overflow. Then, with the 3 12-bit random numbers, you can make a 36-bit random integer:

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

Remark that if the p_i are primes and relatively large, the 3 random generators should be quite independant, so that strategy should be quite ok.

The difficulty is to have a good choice for a.

Anyway, before using it, I guess that it would be better making some tests.