▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
I'd be very surprised if this wasn't biased.
It is also more computation.
- Pauli
▼
Posts: 887
Threads: 9
Joined: Jul 2007
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.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 850
Threads: 10
Joined: Mar 2009
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.
▼
Posts: 204
Threads: 20
Joined: Jun 2005
So have I, but its implementation goes far beyond of what's achievable on pocket calculators.
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 850
Threads: 10
Joined: Mar 2009
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.
Regards Bart
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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.
Posts: 239
Threads: 9
Joined: Dec 2010
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.)
Posts: 1,193
Threads: 43
Joined: Jul 2005
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.
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
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.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
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.
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
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 ;-).
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
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.
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
Quote: Thomas, I was not replying to you directly [...]
Great misunderstanding :-D.
Posts: 1,477
Threads: 71
Joined: Jan 2005
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.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
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 !
Posts: 536
Threads: 56
Joined: Jul 2005
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.
Posts: 528
Threads: 40
Joined: Dec 2008
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
|