Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!elroy.jpl.nasa.gov!sdd.hp.com!spool.mu.edu!news.cs.indiana.edu!ariel.unm.edu!nmsu!opus!ted From: ted@nmsu.edu (Ted Dunning) Newsgroups: comp.lang.functional Subject: Re: Random number generator/script Message-ID: Date: 23 May 91 19:06:37 GMT References: <1991May23.134621@axion.bt.co.uk> Sender: news@NMSU.Edu Organization: Computing Research Lab Lines: 53 In-reply-to: dwestlan@axion.bt.co.uk's message of 23 May 91 12:46:21 GMT 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.