🚀 go-pugleaf

Regarding all of the posted random number generators for modula-2, here
is one which works very well.  I hope its ok with the readers if I don't
code it.  This random number generator idea comes from Knuth's "ACP, volume 2",
and was invented in 1958 by G.J. Mitchell and D.P. Moore (unpublished).

Define initially some sequence of non-negative integers

  X(1), X(2), ... , X(55)

which are not all even.  For n > 55, define X(n) by

  X(n) = ( X(n - 24 + 1) + X(n - 55 + 1) ) mod M

where M is large and even.  That's it.

As you can easily see, one doesn't really need an infinite array, but merely
a cyclic array (queue) of 55 integers, in order to implement this algorithm.

The values 24 and 55 appearing above are not chosen arbitrarily, but are
instead special values that guarantee { X(n) } will have a period of length
at least 2^f * ( 2^55 - 1 ) for some f satisfying 0 <= f <= log M.  The big
drawback of this method is that there is very little theory developed to
prove that it has desirable randomness properties.  However, I've implemented
this thing in several languages, and it seems to work just fine.  Knuth adds
that this method has consistently passed statisical tests of randomness with 
flying colors, in extensive testing done since 1958.  The biggest advantage
of this thing is that once you have your inital array of 55 elements, which
you can get by using some weak method of generating integers, the successive
elements can be gotten using only addition and subtraction:

  current := X[ n - 24 + 1 ] + X[ n - 55 + 1 ];
   
  if ( current >= M ) then

      current := current - M;

   X[n] := current;

   (* normalized := ( X[n] * 1.0 ) / ( 1.0 * M ) *)

I'll leave the index arithmetic to you.  Knuth actually implements this 
algorithm using subtraction, so all comparisons can be made against 0,
shaving even a few more ticks off of the cpu time.

--Bill Allen
--UCLA Math