Question about random number generators



#14

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


#15

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


- Pauli


#16

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.


#17

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


#18

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


#19

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.


#20

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

#21

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


#22

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


#23

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.

#24

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.)

#25

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.


#26

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.

#27

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.


#28

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 ;-).

#29

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.


#30

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

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.


#32

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 !

#33

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.

#34

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 715 10-20-2013, 05:28 PM
Last Post: Dieter
  HP Prime: RANDOM Alberto Candel 4 768 10-18-2013, 09:18 PM
Last Post: Alberto Candel
  Some random wish list items for the 43s Marcel Samek 18 2,064 07-11-2013, 05:35 PM
Last Post: Paul Dale
  more question regarding complex operations using complex number on wp34s wildpig 22 1,903 09-02-2012, 12:54 PM
Last Post: Walter B
  Stupid question number...WS34P Geoff Quickfall 16 1,541 06-16-2012, 07:04 AM
Last Post: Paul Dale
  OT: Help with Testing Random Number Generators Namir 5 794 08-01-2011, 11:20 PM
Last Post: Paul Dale
  Random Number Generation Challenge (sort of) Namir 9 1,132 02-15-2010, 08:05 AM
Last Post: Bart (UK)
  HP17b & it's offsprings - Random Number Generator - How? Peter A. Gebhardt 29 2,508 12-09-2009, 02:18 AM
Last Post: Marcus von Cube, Germany
  O.T. Pseodo-random noise designnut 0 288 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 715 12-15-2007, 10:46 AM
Last Post: bt_schmidt

Forum Jump: