Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!caen!news.cs.indiana.edu!ariel.unm.edu!nmsu!opus!ted From: ted@nmsu.edu (Ted Dunning) Newsgroups: comp.lang.functional Subject: Re: Random Number Generating Algorithm/script Message-ID: Date: 24 May 91 16:22:02 GMT References: <1991May20.161445@axion.bt.co.uk> <1991May23.005659.10244@massey.ac.nz> Sender: news@NMSU.Edu Organization: Computing Research Lab Lines: 92 In-reply-to: news@massey.ac.nz's message of 23 May 91 00:56:59 GMT mister massey's email is subject to rubberizing... While talking to sis-a: >>> RCPT To: <<< 550 ... User unknown 550 ... 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 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.