dwestlan@axion.bt.co.uk (Dave Westland) (05/20/91)
Ladies and Gentlepersons,
Does anyone know any good random number generating algorithms, (or
even not so good ones).
I'm using an FP which has no facility to generate them. It would be extremely
useful (well, a lot less hassle for me) if the algorithm was expressed in
Miranda, (Hope or ML at a push).
Thanks well in advance.
Dave Westland.
*-------------------------------------------------------*
| DAVID WESTLAND |
| BT Laboratories, Martlesham Heath, |
| Ipswich. IP5 7RE U.K. |
| Email : dwestlan@axion.bt.co.uk |
| Tel. : (0473) 642156 Fax : (0473) 643019 |
*-------------------------------------------------------*
``You run and you run to catch up with the sun but it's sinking,
Racing around to come up behind you again,
The sun is the same in a relative way but you're older,
Shorter of breath and one day closer to death.''
Pink Floyd.
---news@massey.ac.nz (USENET News System) (05/23/91)
In article <1991May20.161445@axion.bt.co.uk> dwestlan@axion.bt.co.uk (Dave Westland) writes: > > Ladies and Gentlepersons, > > Does anyone know any good random number generating algorithms, (or >even not so good ones). Here is mine, in Haskell. I just touched it up a bit (and found a few bugs with the seed initialisation), and I hope that it is suitable for your application. Hopefully someone else will find it useful too (I wrote it for a Haskell Noughts and Crosses game). Note: if you are not using arbitrary precision integers, maxInt must be at least 2^46-1 (the quoted article describes a number of ways around this). _______________________________________________________________________________ E.Ireland@massey.ac.nz Evan Ireland, School of Information Sciences, +64 63 69099 x8541 Massey University, Palmerston North, New Zealand. _______________________________________________________________________________ module Random (randoms, random) where -- Multiplicative linear congruential random number generator adapted -- from "Random number generators: good ones are hard to find", -- Stephen K. Park and Keith W. Miller, Communications of the ACM, -- October 1988, Volume 31, Number 10. m = 2147483647 -- modulus a = 16807 -- multiplier randoms :: Integer -> [Integer] -- Given an initial seed (any integer value), returns a potentially -- infinite list of pseudorandom numbers in [1..m-1]. randoms seed = f (f s1 !! 2) -- gives a `better' initial z than f s1 where s0 = abs seed `mod` m -- s0 in [0..m-1] s1 = if s0==0 then 1 else s0 -- s1 in [1..m-1] f z = z' : f z' where z' = (a * z) `mod` m random :: Integer -> Integer -> Integer -- Given a lower and upper bound (x <= y), and a pseudorandom number -- in [1..m-1], returns a pseudorandom number in [x..y]. random x y z = (z * (y-x+1)) `div` m + x -- _______________________________________________________________________________ E.Ireland@massey.ac.nz Evan Ireland, School of Information Sciences, +64 63 69099 x8541 Massey University, Palmerston North, New Zealand.
ted@nmsu.edu (Ted Dunning) (05/24/91)
mister massey's email is subject to rubberizing... While talking to sis-a: >>> RCPT To:<EIreland@sis-a> <<< 550 <EIreland@sis-a>... User unknown 550 <E.Ireland@massey.ac.nz>... User unknown but it seems that this might be of more general interest anyway, Date: Fri, 24 May 91 13:37:51 NZS From: E.Ireland%massey.ac.nz References: <1991May23.134621@axion.bt.co.uk> Organization: School of Maths and Info. Sci., Massey University, NZ In article <TED.91May23130637@kythera.nmsu.edu> you write: >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 >... >lowest order bits, and you have better characteristics for the higher >order bits. If you use only (unbounded) integer arithmetic, make sure you don't seed the generator with a zero, and extract the numbers as with the `random' function in my posting (which effectively results in using the higher order bits only, unless the range [x..y] is huge), what loss of robustness will result? depending on the exact characteristics of the floating point arithmetic you are using, the sequence you get will vary from machine to machine. secondly, it is very difficult to characterize the length of such a method since it again depends on the details of f.p. arithmetic. thus, you have no guarantees. thirdly, assuming that the system you propose actually does act like the integer linear congruential system it resembles, chances are that it will not pass the spectral test. very few linear congruential generators will pass such a test, and all the ones that i know have more significant digits in the constant multiplier. >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. Can you please elaborate on this? What is unreliable about the proposed `minimal standard' generator? they propose the standard use of a linear congruential generator which was shown in knuth to be distinctly sub-optimal. this is absolutely crazy since there are so many good generators of that form that are known. it is even crazier when other forms of generators are also known to produce good results. Do you have references to work which does more than `touch' on additive feedback systems? knuth mentions several and gives some encouraging words. in spite of the fact that this generator has passed innumerable tests and is known (modulo one likely conjecture) to have good multi-dimensional characteristics and is likely faster than most others, the lack of a strong underlying theory keeps some people from whole hearted endorsement. another basic reference would have to be the berkeley source code for random (which may well be part of the liberated berkeley code). Thanks for any help that you can give. I am most interested in generators that use unbounded integer arithmetic (if necessary), perferably not too much bit-twiddling (or none), and have very large cycles. additive feedback systems do not require unbound integer arithmetic. in fact, they will produce as many good bits as you can effectively use, although there will be a serious improvement in speed if you stay inside the bounds of machine arithmetic. the cycle length for the lsb of the most common generator of this sort is 2^54-1. for n bit words, the cycle length is at least 2^f * (2^54-1) larger than this where 0 < f <= n. if you change to subtractive feedback, then you can perform all necessary arithmetic using floating point numbers in [0,1). also, on some machines, subtracting and testing may be slightly faster than adding and testing (both discussed in knuth). -- Offer void except where prohibited by law.