The Museum of HP Calculators

HP Forum Archive 20

 Question about random number generatorsMessage #1 Posted by Namir on 5 July 2011, 4:01 a.m. Using the linear congruential generator method to calculate a sequence of pseudo-random numbers: ```S(n+1) = (A * S(n) + C) mod M ``` The S() is the integer seed values. The random number between 0 and 1 is calculated using: ```X(n) = S(n) / M ``` What do you think if one uses the following algorithm instead: ```S(n+1) = (A * S(n) + C) mod M if S(n+1) < S(n) then X(n) = S(n+1) / S(n) Else X(n) = S(n) / S(n+1) End If ``` Namir

 Re: Question about random number generatorsMessage #2 Posted by Paul Dale on 5 July 2011, 4:29 a.m.,in response to message #1 by Namir I'd be very surprised if this wasn't biased. It is also more computation. - Pauli

 Re: Question about random number generatorsMessage #3 Posted by Garth Wilson on 5 July 2011, 4:36 a.m.,in response to message #2 by Paul Dale What do you want to run it on? If there's a timer/counter and its value might be anything when you need the random number, you could bring that into the derivation.

 Re: Question about random number generatorsMessage #4 Posted by Namir on 5 July 2011, 5:19 a.m.,in response to message #3 by Garth Wilson Just a general random number generator. My very basic tests show that the new algorithm generates a good spread. BUT ... MORE testing is needed. Another more complex algorithm I had developed last year uses a VIRTUAL CLOCK. The clock ticks each time you call it's random number generator. This way, it is independent of the real CPU clock. That algorithm seems to do well. Of course when you use RNG for Monte Carlo methods, you need very good ones (based on this book I am reading). Cheers from southern France! Namir

 Re: Question about random number generatorsMessage #5 Posted by Paul Dale on 5 July 2011, 5:52 a.m.,in response to message #4 by Namir A very good rule of thumb regarding random number generators is to not try to invert your own. It is very easy to stuff it up in a way you won't recognise. I.e. it is easy to produce what you think is randomness when in reality, you've produced nothing of the sort. So, find a reputable pseudo random number generator and stick with that. Linear congruential is quite popular. Mersenne twister is gaining popularity. The 34s uses the Taus generator from the GNU scientific library. But use a reputable, known, tried and tested algorithm. If you're planning cryptographic applications, choose one specialised for that, the ones I've mentioned here are not suitable. - Pauli

 Re: Question about random number generatorsMessage #6 Posted by Bart (UK) on 5 July 2011, 8:39 a.m.,in response to message #5 by Paul Dale I have used Mersenne Twister with good results on Monte Carlo type simulations with iterations around 1E7. How would the 34s Taus generator compare? -Bart Edited: 5 July 2011, 9:06 a.m.

 Re: Question about random number generatorsMessage #7 Posted by marais on 5 July 2011, 3:46 p.m.,in response to message #6 by Bart (UK) So have I, but its implementation goes far beyond of what's achievable on pocket calculators.

 Re: Question about random number generatorsMessage #8 Posted by Paul Dale on 5 July 2011, 5:47 p.m.,in response to message #6 by Bart (UK) The primary problem with the MT algorithm is the amount of state it requires. It requires more data in its state vector than the 34s has persistent RAM :-) Tau on the other hand requires twelve bytes of state. The Tau generator has a much smaller period than MT, only about 10^28 instead of something like 10^6000 but either of these is more than large enough for a calculator. They are more than large enough for a super computer. Tau is also supposed to be faster which is relevant on a low speed computing device. Both are reputable and pass the usual battery of tests to which these things are subjected (the spectral test is only the beginning). They are not suitable for cryptographic applications however. That is a completely different story with much more stringent requirements. The GSL documents their random number generators quite well. - Pauli

 Re: Question about random number generatorsMessage #9 Posted by Bart (UK) on 7 July 2011, 5:03 a.m.,in response to message #8 by Paul Dale Thanks Pauli,The period sure seems long enough. I am still learning to use my recently "acquired" 34s, and I'm curios to try and run some of my simulations on it :-). Having so many useful functions already built into the calculator really helps to keep programs short! (as I discovered many years ago when I went from a 28C to an fx-850p - the fx had more than double the memory but I used it all up rewriting functions that were built into the 28).Thank you for the link, it is an interesting read.RegardsBart

 Re: Question about random number generatorsMessage #10 Posted by Paul Dale on 7 July 2011, 5:26 a.m.,in response to message #9 by Bart (UK) Quote:The period sure seems long enough. I'd hope so. By my rough calculations, assuming that one FLOP is sufficient to generate the next number in sequence (which it isn't even close), it would take the current world's fastest super-computer approximately 3.8e19 years to get the RNG to repeat. I don't think you'll be running out :-) Quote:Having so many useful functions already built into the calculator really helps to keep programs short! It is definitely a programmers' calculator. - Pauli Edited: 7 July 2011, 7:09 a.m.

 Re: Question about random number generatorsMessage #11 Posted by Oliver Unter Ecker on 5 July 2011, 8:20 p.m.,in response to message #5 by Paul Dale Thank you for this discussion! It helped me decide that ND1 will support the Mersenne twister with the next update. (I was just working on adding ARC4, which will also be available, for crypto-applications.)

 Re: Question about random number generatorsMessage #12 Posted by Andrés C. Rodríguez (Argentina) on 5 July 2011, 8:46 a.m.,in response to message #1 by Namir There is a specific chapter in "The Art of Computer Programming", vol 2- Seminumerical Algorithms, by Donald Knuth. It includes a memorable example of a random number generator that seems to be very random, but it fails badly, prompting for a clear statement "Never use a randomly chosen method to create random numbers". AFAIK, the critical test for randomness is the "spectral test", which sort of measures the "white noise" quality of a pseudo-random sequence. The congruential one used for HP-41C applications, where S(n+1)=FRAC(S(n) * 9821 + 0.211327) is reported as passing the "spectral test". As all these bits of data are just from memory, I apologize for possible inaccuracies and idiomatic mistakes. HTH.

 Re: Question about random number generatorsMessage #13 Posted by Thomas Radtke on 5 July 2011, 9:51 a.m.,in response to message #12 by Andrés C. Rodríguez (Argentina) Quote:AFAIK, the critical test for randomness is the "spectral test", which sort of measures the "white noise" quality of a pseudo-random sequence. The congruential one used for HP-41C applications, where S(n+1)=FRAC(S(n) * 9821 + 0.211327) is reported as passing the "spectral test". An interesting test is to calculate 'how much' a series is a cyclic difference set. Years ago, I implemented this in a simple Java spreadsheet program to quickly check the 'randomness' of a given series. By definition of this method, a series is at maximum random if self-similarity is minimal.

 Re: Question about random number generatorsMessage #14 Posted by Marcus von Cube, Germany on 5 July 2011, 9:59 a.m.,in response to message #13 by Thomas Radtke I think one of the problems you can run into are sequences that repeat themselves and are short compared to the number of possible values given the machine accuracy. If you have such cycles you split the random numbers into distinct sets which do not overlap. Another possible outcome is that the sequence converges or bounces around only a few values. This may happen only after a million cycles. But it may happen.

 Re: Question about random number generatorsMessage #15 Posted by Thomas Radtke on 5 July 2011, 10:16 a.m.,in response to message #14 by Marcus von Cube, Germany Quote:I think one of the problems you can run into are sequences that repeat themselves [...] That would be a very predictable sequence, and so not really random. The CDS method perfectly identifies this. When using a ranom number generator, you should use it inside a unique series only anyway. Quote:[...] and are short compared to the number of possible values given the machine accuracy. I'm not sure I understand. I calculate the algebraic difference, *not* doing boolean algebra (i.e. test on equalty). That's a little different from the usual CDS thing, I admit. Quote:Another possible outcome is that the sequence converges or bounces around only a few values. This may happen only after a million cycles. But it may happen. And here I'm sure I don't understand what you mean ;-).

 Re: Question about random number generatorsMessage #16 Posted by Marcus von Cube, Germany on 5 July 2011, 10:42 a.m.,in response to message #15 by Thomas Radtke Thomas, I was not replying to you directly but to the complete thread. But I try to answer you questions anyway. ;) Given you have a sequence S(n+1) := F(S(n)). The numeric precision of your device is limited. So you have only a limited set V of values, the set having N elements. Depending on F you split this set in subsets. The simplest function F is identity (not random at all). S(n+1) := S(n) for every S in V. You split V in N subsets. If your function F cycles through just the half of the possible values and there are starting seeds S and S' which create distinct subsets, you split V in two subsets, one containing S and the other containing S'. This may still be a good random sequence but it limits the possible number of random numbers in a single sequence to a subset of the possible values. If the split is asymmetric (one set much larger than the other) you can either get a good sequence or a very bad one, depending on the seed. F might have another unwanted behavior. Even if F can produce all numbers in V in a single run, there may be values in the sequence which lead to more or less short cycles. You can enter the cycle from anywhere in V but once in the loop, F never produces values outside the loop. Edited: 5 July 2011, 10:44 a.m.

 Re: Question about random number generatorsMessage #17 Posted by Thomas Radtke on 5 July 2011, 11:01 a.m.,in response to message #16 by Marcus von Cube, Germany Quote:Thomas, I was not replying to you directly [...] Great misunderstanding :-D.

 Re: Question about random number generatorsMessage #18 Posted by Katie Wasserman on 5 July 2011, 10:58 a.m.,in response to message #1 by Namir Quote: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. -- John von Neumann Or southern France, as the case may be. Edited: 5 July 2011, 11:00 a.m.

 Re: Question about random number generatorsMessage #19 Posted by C.Ret on 5 July 2011, 2:24 p.m.,in response to message #18 by Katie Wasserman By luck, I am living in North-East of France and I am only involve with pseudo-random numbers set and ions spectrometric generators. This perhaps explain why I usely make differencies between : - a set of random data, - a random set of data, - a set of random data, - data of a random set, - to set data from a random, and so on !

 Re: Question about random number generatorsMessage #20 Posted by hugh steers on 6 July 2011, 9:15 a.m.,in response to message #1 by Namir you would need to, in addition to the usual constraints on A, C and M, ensure low correlation between S(n) and S(n+1). This is to say, S(n) would have to pass the serial correlation test, achieved by having low partial quotients of A/M. The partial quotients are the numbers that come out from the euclidian algorithm for GCD(A,M). See knuth V2, 3.3.3, theorem D and K.

 Re: Question about random number generatorsMessage #21 Posted by David Hayden on 8 July 2011, 11:05 a.m.,in response to message #1 by Namir The X86 processors have a random number generator built into the hardware (RDRAND instruction). It uses a combination of truly random numbers, generated by an entropy source on the chip, and a pseudo-random number generator that is periodically seeded from the entropy source. Dave

Go back to the main exhibit hall