True random nunber generator

Heaven forbid! What was I thinking? The simplest and quickest method that required just a little bit of thinking is no good. I suppose the follow up of a goodness of fit test is not mathematical enough either?

"Goodness of fit" cannot determine if a rather long sequence is or is not random, and a distribution plot and parameters of a distribution also cannot determine that either. Almost all digital feedback schemes "miss" one state of 2^n which is a dead giveaway if you know the method; the other dead giveaway is that the sequence does repeat exactly and forever. Yet another dead giveaway is that no generated value repeats (eg: ..4, 9, 3, 3, 7...).

Since the OP wants to determine the *distribution* and that is what I was discussing, what you are saying above about determining randomness is not relevant.

That's not correct. Linear feedback shift registers have N-1 states. Most other PRNG have N states. A simple example is the common linear congruence generator, which is the most used of all, many of the generators of George Marsaglia, and most if not all cryptographically secure random number generators.

the other dead giveaway is that

Dead give-away? (I object to the dead "give-away", not the statement and fact that the PRNG will eventually repeat) Most decent PRNG used for simulations and anything other than simple games have periods much longer than can be sampled and compared in a lifetime. Many can be implemented with periods so long the universe will end before they repeat. So the dead give-away of watching for a sequence to repeat is not very conclusive, it would pass as true random many sequences generated by PRNG.

Sorry, that's not true. Repeats are necessary for any RNG that has to be taken seriously in simulations - and there are at least a dozen algorithms that do it. The ability to produce repeats is also a prerequisite of any RNG that is intended for cryptography - and there are hundred if not thousands of algorithms to do that.

To show how easy it is, here is one I whipped up earlier. This is a linear congruence generator - the simplistic type of PRNG in software. The implemented function is the simplest function that achieves maximum period of N. The function is:

X(i+1) = 5 * x(i) + 1 (mod 2** 15)

Below is a screen grab of a short run. The language is UBASIC (freeware). As you can see, in this sample of 10 outputs, there is a repeat of "0"s and a repeat of "3"s. In fact repeats are possible with virtually any random number generator that does not output its entire state.

90 679 0 91 3396 0 92 16981 3 93 19370 3 94 31315 5 95 25504 4 96 29217 5 97 15014 2 98 9535 1 99 14908 2 100 9005 1 Break in 70

list 10 Y=0 20 X=0 30 X=X*5+1 40 X=bitand(X,0x7fff) 'this is equivalent to mod 2** 15 50 print Y,X,X\\5461 60 Y=Y+1 70 if Y>100 then stop 80 goto 30 OK

s

he

is

is

In real life there is no test that can ever show is a sequence is random or not. Any sequence of finite length is disqualified. Any infinite one can't be checked. All we can ever do is say that the sequence is random enough for our purposes. If you want real randomness, you need to get some quantum physics involved in determining the output.

The trick with digital "random number generators" is to keep a lot of bits hidden and only report a small fraction of the internal state. This way there is not enough information given that even if the rule was known, the next state can't be predicted by the external observer unless a very large number of states is examined.

A trick that can be very useful is to combine a little bit of truly random stuff with a lot of pseudo-random so that the pseudo-random isn't easy to break out. The XOR operation is good for this because it is very like a multiply in its action. If you think about it in the frequency domain, it adds and subtracts the frequencies. This means that the repeat of the pseudo-random is not given away by some frequencies being missing.

On Aug 23, 3:28=A0am, David Eather wrote: [.... pseudorandom ....]

I will suggest that there is an infinite number of RNGs that repeat the values.

If a sequence is long - and a 1000 year, 100 MHz sequence is easy these days - and all you see is, say, 16 bits chopped out of the sequence, those simple tests don't work to spot a deterministic sequence. Generated values will certainly repeat, and all 2^16 states appear with equal probability, at least in our lifetimes. But other compute-intensive tests can identify simple polynomial generators.

If it were DAC'd and filtered and presented as an analog signal, I suspect the underlying sequence would be impossible to identify, buried in noise and inter-symbol interferance.

If the goal is cryptography or academic purity, a polynomial-based generator is weak. For most any other purpose, it's fine.

John

us

the

is

s

Yes but they are no fun to check. I have spent a lot of hours looking at ones that only where good for a few months just to be sure that I hadn't made any typos.

I will suggest that there is an infinite number of RNGs that repeat the values.

Actually, it's infinite minus one. I'm about to write a Wikipedia article whose existence will prove it.

-- Mike --

If you're talking about XOR-ing random with pseudo-random, you need as much random as pseudo-random. It's more productive to use the true RNG to periodically re-seed the PRNG.

XOR-ing independent streams has the advantage that a flaw in one stream can't make the output any worse than just using the other stream alone.