HP Forums
Question about random number generators - Printable Version

+- HP Forums (https://archived.hpcalc.org/museumforum)
+-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html)
+--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html)
+--- Thread: Question about random number generators (/thread-187180.html)



Question about random number generators - Namir - 07-05-2011

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 generators - Paul Dale - 07-05-2011

I'd be very surprised if this wasn't biased.
It is also more computation.


- Pauli


Re: Question about random number generators - Garth Wilson - 07-05-2011

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 generators - Namir - 07-05-2011

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 generators - Paul Dale - 07-05-2011

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 generators - Bart (UK) - 07-05-2011

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 generators - Andrés C. Rodríguez (Argentina) - 07-05-2011

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 generators - Thomas Radtke - 07-05-2011

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 generators - Marcus von Cube, Germany - 07-05-2011

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 generators - Thomas Radtke - 07-05-2011

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 generators - Marcus von Cube, Germany - 07-05-2011

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 generators - Katie Wasserman - 07-05-2011

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 generators - Thomas Radtke - 07-05-2011

Quote:
Thomas, I was not replying to you directly [...]
Great misunderstanding :-D.


Re: Question about random number generators - C.Ret - 07-05-2011

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 generators - marais - 07-05-2011

So have I, but its implementation goes far beyond of what's achievable on pocket calculators.




Re: Question about random number generators - Paul Dale - 07-05-2011

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 generators - Oliver Unter Ecker - 07-05-2011

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 generators - hugh steers - 07-06-2011

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 generators - Bart (UK) - 07-07-2011

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


Re: Question about random number generators - Paul Dale - 07-07-2011

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 generators - David Hayden - 07-08-2011

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