🚀 go-pugleaf

In article <1991May23.134621@axion.bt.co.uk> dwestlan@axion.bt.co.uk (Dave Westland) writes:


	   Multiple thanks to everyone who sent me scripts or references.
   I now have a working random # generator in Haskell, based on an ML library
   function, which goes something like this :-

   randlist :: Double -> [Double]
   randlist seed = r : (randlist r)                    -- infinite list
		   where 
		   r = x - (fromInteger (floor x))
		   x = seed * 147.0

	   It's probably a bit more pseudo than random, but it's sufficient for
   my purposes.



generators of this sort (linear congruential) are relatively delicate
vis a vis the characteristics of the underlying floating point
implementation and the selection of multipliers.  knuth gives a good
treatment of them.  you also have to worry about the fact that a zero
may be generated, at which point, only zeros will be generated.

in general, a much more robust generator can be constructed by using
an additive feedback in which an short queue of integers is kept.  new
elements are generated by adding several older elements together
modulo some limit which is conveniently the machine's largest positive
integer.  the length of the queue, and exactly which older elements to
add are selected so that the low order bits of the integers form a
maximum length linear feedback shift register (since adding without
carry = xor).  thus you have relatively good characteristics for the
lowest order bits, and you have better characteristics for the higher
order bits.

the period for an additive feedback shift register is absolutely
enormous, and the statistical characteristics are good.  all zeros in
the queue is a fixed point as with a linear congruential generator,
but this is easily avoided by keeping a running total of how many
consecutive times the generator has produced a zero output and
reseting the generator when this total reaches the length of the
queue. 

the recent cacm article (a proposed standard random number generator
or some such) was absolute drivel and should not be relied on.  knuth
is a good source, although he only touches on additive feedback
systems.

--

if feeling bad is a justification for not living, 
    then living is a justification for feeling good.