Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!ucla-cs!math.ucla.edu!sonia.math.ucla.edu!allen From: allen@sonia.math.ucla.edu (William C. Allen) Newsgroups: comp.lang.modula2 Subject: Re: RND Function Needed Message-ID: <862@kaos.MATH.UCLA.EDU> Date: 6 Dec 90 21:40:09 GMT References: Sender: news@MATH.UCLA.EDU Reply-To: allen@sonia.math.ucla.edu (William C. Allen) Lines: 46 Distribution:usa 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 Brought to you by Super Global Mega Corp .com