Question about random number generators « Next Oldest | Next Newest »

 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 07-05-2011, 04:01 AM 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 ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 07-05-2011, 04:29 AM I'd be very surprised if this wasn't biased. It is also more computation. - Pauli ▼ Garth Wilson Posting Freak Posts: 887 Threads: 9 Joined: Jul 2007 07-05-2011, 04:36 AM 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. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 07-05-2011, 05:19 AM 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 ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 07-05-2011, 05:52 AM 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 ▼ Bart (UK) Posting Freak Posts: 850 Threads: 10 Joined: Mar 2009 07-05-2011, 08:39 AM 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. ▼ marais Member Posts: 204 Threads: 20 Joined: Jun 2005 07-05-2011, 03:46 PM So have I, but its implementation goes far beyond of what's achievable on pocket calculators. Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 07-05-2011, 05:47 PM 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 ▼ Bart (UK) Posting Freak Posts: 850 Threads: 10 Joined: Mar 2009 07-07-2011, 05:03 AM 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 ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 07-07-2011, 05:26 AM 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. Oliver Unter Ecker Member Posts: 239 Threads: 9 Joined: Dec 2010 07-05-2011, 08:20 PM 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.) Andrés C. Rodríguez (Argentina) Posting Freak Posts: 1,193 Threads: 43 Joined: Jul 2005 07-05-2011, 08:46 AM 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. ▼ Thomas Radtke Posting Freak Posts: 1,089 Threads: 32 Joined: Dec 2005 07-05-2011, 09:51 AM 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. ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 07-05-2011, 09:59 AM 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. ▼ Thomas Radtke Posting Freak Posts: 1,089 Threads: 32 Joined: Dec 2005 07-05-2011, 10:16 AM 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 ;-). ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 07-05-2011, 10:42 AM 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. ▼ Thomas Radtke Posting Freak Posts: 1,089 Threads: 32 Joined: Dec 2005 07-05-2011, 11:01 AM Quote:Thomas, I was not replying to you directly [...] Great misunderstanding :-D. Katie Wasserman Posting Freak Posts: 1,477 Threads: 71 Joined: Jan 2005 07-05-2011, 10:58 AM 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. ▼ C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 07-05-2011, 02:24 PM 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 ! hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 07-06-2011, 09:15 AM 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. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 07-08-2011, 11:05 AM 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

 Possibly Related Threads... Thread Author Replies Views Last Post WP-34S (Prime Number Test) question Barry Mead 3 918 10-20-2013, 05:28 PM Last Post: Dieter HP Prime: RANDOM Alberto Candel 4 980 10-18-2013, 09:18 PM Last Post: Alberto Candel Some random wish list items for the 43s Marcel Samek 18 2,571 07-11-2013, 05:35 PM Last Post: Paul Dale more question regarding complex operations using complex number on wp34s wildpig 22 2,437 09-02-2012, 12:54 PM Last Post: Walter B Stupid question number...WS34P Geoff Quickfall 16 2,074 06-16-2012, 07:04 AM Last Post: Paul Dale OT: Help with Testing Random Number Generators Namir 5 1,067 08-01-2011, 11:20 PM Last Post: Paul Dale Random Number Generation Challenge (sort of) Namir 9 1,464 02-15-2010, 08:05 AM Last Post: Bart (UK) HP17b & it's offsprings - Random Number Generator - How? Peter A. Gebhardt 29 3,263 12-09-2009, 02:18 AM Last Post: Marcus von Cube, Germany O.T. Pseodo-random noise designnut 0 404 11-25-2008, 05:31 PM Last Post: designnut Man calculates the 13th root of a random 200 digit number in his head in 70 secs! BruceH 5 950 12-15-2007, 10:46 AM Last Post: bt_schmidt

Forum Jump: