Random number generator, not so random?

[Thomas Jentzsch]

When using a 16-bit LFSR, I'd highly recommend shifting the two halves in opposite directions and getting a result by XOR'ing them together.  Depending upon the constant used, this will allow all 65,535 byte pairs other than (0,0) to appear on consecutive invocations (i.e. after reading one byte, the next byte can be anything unless the first byte was zero, in which case the second byte can be anything non-zero).

Interesting idea. But one can only speculate about the better randomness. Maybe someone should do some basic randomness tests first.

Edited January 10, 2006 by Thomas Jentzsch

[djmips]

When using a 16-bit LFSR, I'd highly recommend shifting the two halves in opposite directions and getting a result by XOR'ing them together.  Depending upon the constant used, this will allow all 65,535 byte pairs other than (0,0) to appear on consecutive invocations (i.e. after reading one byte, the next byte can be anything unless the first byte was zero, in which case the second byte can be anything non-zero).

Interesting idea. But one can only speculate about the better randomness. Maybe someone should do some basic randomness tests first.

997407[/snapback]

 

Yes it would be interesting to run the tests. I can't run any tests until I fix the 6502 simulator to output to a file instead of screen only. You can't even cut/paste from the output window. Sigh. Well, at least I have the source to the simulator.

 

A couple of things, first of all I have heard that LFSR's with a lot of zero taps are not as uniform as ones with more uniform taps.

 

supercat reminded me with his routine that it has been shown that you can create a more uniform LFSR sequence by the combination of two independant LFSR sequences with XOR. The output sequence length is the product of the two sequences and by some measure, the uniformity is also a product of the two. The caveat was that the sequence lengths should be relatively prime to each other.

[Thomas Jentzsch]

Yes it would be interesting to run the tests. I can't run any tests until I fix the 6502 simulator to output to a file instead of screen only. You can't even cut/paste from the output window. Sigh. Well, at least I have the source to the simulator.

I once wrote as simple Pascal program, where I reprogrammed the LFSRs and output the results into a file. Maybe I can find it.

[+batari]

Just ran the tests. This result is from the unaltered LFSR:

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 65535 byte file by 0 percent.

Chi square distribution for 65535 samples is 0.00, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4986 (127.5 = random).
Monte Carlo value for Pi is 3.246658121 (error 3.34 percent).
Serial correlation coefficient is 0.381309 (totally uncorrelated = 0.0).

Looks good except for the correlation. However, reversing the rotation of one byte the opposite direction combined with EOR of each gives better results:

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 65535 byte file by 0 percent.

Chi square distribution for 65535 samples is 0.00, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4986 (127.5 = random).
Monte Carlo value for Pi is 3.130928401 (error 0.34 percent).
Serial correlation coefficient is -0.000022 (totally uncorrelated = 0.0).

 

The difference would matter with cryptography or something. But I am not convinced that anyone would ever notice the difference in a 2600 game, even with the fairly significant correlation.

[Thomas Jentzsch]

But I am not convinced that anyone would ever notice the difference in a 2600 game, even with the fairly significant correlation.

Very true. Usually even a 8 bit LFSR will be random enough, especially when combined with some user input. Only for sutff like the example wich started this thread you need more bits.

[djmips]

The difference would matter with cryptography or something.  But I am not convinced that anyone would ever notice the difference in a 2600 game, even with the fairly significant correlation.

997423[/snapback]

 

Well... I have already wrestled with issues of correlation in a 2600 game, which is what got me interested in this topic (prior to this thread).

 

On your first test of the 16 bit LFSR, did you generate only 1 new bit per output byte? If it's no trouble, I'm interested in the results for generating 8 new bits per byte as well.

 

I'm going to try supercat's routine in my game because it seems it would also solve my correlation problem but requires only two iterations.

 

Thanks everyone.

[supercat]

But I am not convinced that anyone would ever notice the difference in a 2600 game, even with the fairly significant correlation.

Very true. Usually even a 8 bit LFSR will be random enough, especially when combined with some user input. Only for sutff like the example wich started this thread you need more bits.

997437[/snapback]

 

Whether a random number generator is good enough for an application depends greatly on how the application will use it. If there is something that will 'feed some randomness' into the generator (e.g. iterating the random function while in a busy-loop waiting for INTIM to reach its proper value) between uses, even a simple 8-bit LFSR may be adequate. On the other hand, if the random number generator will be used to generate a level's worth of data at once, without anything happening to help improve its randomness, it may be quite unsuitable. The best such a generator can do is generate 255 different configurations, and many are apt to show certain similarities.

 

Using a 16-bit LFSR will improve things, but if one only takes numbers off one end or the other, there will still be a major problem: following a particular byte 'n', the next value can only be one of two things. If the values are used for, e.g., plotting X,Y coordinates, this will cause severely non-uniform distribution. If both halves of the LFSR shift in the same direction, XORing them won't solve this problem.

 

Shifting both halves of the LFSR in opposite directions and XORing them together will for the most part ease the correlation problem, but outputting the results to a file in binary (one line per number) or, better yet, plotting them to a high-res screen will reveal that while the number stream generally looks good, there are highly-visible anomolies within it. Using two iterations of the LFSR for each byte generated will make these anomolies pass twice as quickly; using four iterations will make them all but invisible.

 

As noted, games that need a random byte here and there probably don't need to worry about PRNG quality; those that need lots of random data, however, do.

[potatohead]

Stumbled on this thread late it seems.

 

I ran into this early on with Ooze. In a nutshell, if one expects reasonably random numbers, don't ask for them quick!