Had not expected a request so soon 😉
Ok, here is an attempt to explain my analysis:
The original GCE Random() function implements a 17-bit linear feedback shift register (LSFR). For storing the "seed", the BIOS uses 3 bytes (24 bits), located at Vec_Random_Seed. The upper 7 bits of Vec_Random_Seed+2 are not actively used and irrelevant for the random number generation. To be a bit more precise, that Random() routine uses those 3 bytes to which Vec_Seed_Ptr points, and the BIOS initializes this pointer to the address of Vec_Random_Seed. By redirecting this pointer, the programmer can, for example, use the Random() routine in combination with several different random number generators in a program (we will get back to that later).
I have to admit, that I find the term "seed" a bit misleading, as the seed value is actually the current n-bit value (or the current state) of the n-bit LFSR. From this state, the next following n-bit random number is (deterministically) computed. In our case, the "seed" are bits 0 to 7 of Vec_Random_Seed concatenated with bits 0 to 7 of Vec_Random_Seed+1 concatenated with bit 0 of Vec_Random_Seed+2 (or in simpler terms bits 0 to 16 of Vec_Random_Seed).
Some fundamentals: A n-bit Linear Feedback Shift Register operates by shifting all the bits of its current value one position to the right, and by filling up the now "empty" least-significant bit position with some computed entropy value. This operation is defined by a characteristic polynomial which determines the (other) bit positions which are used to compute this next pseudo-random entropy bit (as a big XOR of all the coefficient bits of the polynomial). As there are only 2
n different n-bit values, it is clear the after a certain period the thus produced sequence of n-bit values starts repeating over and over in exactly the same way. If the characteristic polynomial is carefully chosen, then the period is of maximum length (2
n – 1). Note that the n-bit zero as a seed must be avoided and excluded as it leads to a deadlock. A maximum period is desirable in order to get the best (and largest) pseudo random distribution of all n-bit numbers. For each n, there is exactly one polynomial yielding such maximum period.
I tried to explain this the best I can. You can also read all this stuff here:
So why did the GCE programmers implement only a 17-bit LFSR when they had 24 bits at hand?
Now, my guess is, that in order to make the Random() routine compute as fast as possible, the GCE designers settled for a maximum-period polynomial which has the fewest possible number of coefficients. For a maximum-period 17-bit LFSR, only two bits are used to compute the entropy bit, namely bit 16 and bit 13 of Vec_Random_Seed.
The corresponding polynomial is (x17 + x14 + 1). Note that the coefficients are numbered starting from 1, while we programmers usually number bits starting from 0. There are other polynomials with only two coefficients (such as for bits widths 9,10,11, and 15). The designers chose the 17 bit polynomial, because the highest coefficient (bit 16) corresponds to the least significant bit of one of the three seed bytes (bit 0 of Vec_Random_Seed+2). Why would this be good? Because that allows for computing the new entropy bit with the fewest number of 6809 shift and rotate operations. The "other" coefficient bit (bit 13) just needs to be shifted (or rotated) to bit position zero, and then the XOR can be computed. Only four ROLA instructions are need before computing the XOR. For all values of n other than 17, more shift or rotate instructions (or another register load) are needed to compute the XOR, and the routine would thus be slower.
Except for a 20-bit LFSR!!!
If I am not mistaken, that one can be computed with just three ROLA instructions. I checked all polynomials, and I overlooked that possibility at first. So maybe the GCE programmers did not realize that as well? The whole Random() routine can easily be patched to function as a 20-bit LFSR while being one ROLA quicker at the same time. Not that this would change much in terms of quality of the randomness.
Ok, so much for how Random() works, and why it effectively uses just 17 seed bits. Now why do we think badly of it?
Well, rather than being a pseudo random NUMBER generator, a LFSR is actually a pseudo random BIT generator. It shifts all its internal bits one position to the right, and introduced just one single new entropy bit in each call. As result, Random() returns the lowest 8 bits of its seed (the byte in Vec_Random_Seed).
For each two subsequent calls of Random(), we either get the two values (x and 2*x), or (x+1 and 2*x). To be more precise we get either (x and (2*x mod 256)) or (x+1 and (2*x mod 256)). Not very random.
Large slices of the bit patterns keep repeating, or rather reappearing in higher bit positions. One can immediately see this in
Malban 's Shroom example.
Using subsequent calls of the same LFSR to generate pairs of data, of which the two values should be independent of each other, will never work in a "randomly" fashion (e.g. two subsequent calls of Random() to get the y and the x coordinate of an object). LFSRs are quite good in a statistical or purely mathematical sense, when it comes to considering large samples of data, but not in the common applications of game programming, like random positions of objects. Unfortunately, this "dependence" of subsequent data is pretty strong: "the subsequent value being the double of the previous value", never mind those tiny +1 entropy injections.
What can we do about it?
What we have always done. Complain, and use our own pseudo random number generator 😉
Or, to give the original designers credit, one could use several different 3-byte random number seeds, and adjust Vec_Seed_Ptr to switch between them. Use one generator for the y coordinates, and a different one for the x coordinates of random objects. No correlations between y and x anymore. But still within the sequence of y coordinates, and still within the sequence of x-coordinates.
Or we keep in mind what I wrote above: a LFSR is a pseudo random BIT generator. A good idea is to just use only any eighth byte value generated by Random(). Then there will be no (direct) correlation anymore between two subsequent random bytes. It is interesting that there is a Random_3() BIOS routine which iterates through Random() three times, before returning a value. If it were a Random_8() routine, iterating eight times, that would be great and would actually make some sense. Of course the big drawback of this method is that is takes eight times as much time as a single call to Random(). But the results, in terms of pseudo randomness, are much better (I tried it with the Shrooms).
That's for now. Hope all this makes sense.
Many Cheers,
Peer
