I recently downloaded Angband v3.4.1, and I couldn't help but be curious to see how the RNG had changed (in z-rand.c). I see that RNG v2 has been replaced with RNG v3, but that the 28 bit code remains. I'm guessing that no one has changed it since they don't know why it was written in such an odd way.
For reference, following are excerpts from the current code:
Before Ben and I changed the code, random numbers were generated with the library's random() function and implemented in the simple random() % N style. But then I discovered a "bug" in the BSD random() function being that the 4 lower bits of "random" numbers actually followed only one of 4 sequences depending upon how the RNG was seeded.
Specifically, for all values of N,
srandom(N); while(1) printf("%ld\n", random() & 0xF);
would print the same sequence of numbers as:
srandom(N%4); while(1) printf("%ld\n", random() & 0xF);
This means that the commonly used random() & 1 could only follow one of 4 sequences. (It's odd that no one noticed the bug for so long.)
I did a little research into the algorithm used in random(), and it was documented that the upper bits were "more random" than the lower bits, but not to the degree of my discovery. Soon after I publicized the bug in random(), a CERT alert was issued about random() and TCP packet sequence numbers. I'm guessing that wasn't a coincidence as I know that software engineers from Sun Microsystems were playing the game at that time.
My solution to the problem was to use the same algorithm but to rewrite the random() code in a different manner (for copyright reasons) and to include my code into the game (for portability reasons). Then I shifted off the useless 4 lower bits of the pseduorandom number. I had been waiting for an excuse to use my unbiased partitioning algorithm, so that got incorporated in as well. Before the partitioning code, "randomness" was somewhat proportionally correlated with the size of the maximun random number requested (N). After the partitioning code, "randomness" was inversely proportional to the size of N. (Which was desirable since I don't recall large random numbers ever being requested.)
As a new RNG has been incorporated in Angband, which presumably is better than the previous one, there shouldn't be any reason to restrict the RNG to 28 bit numbers. (A search indicates this has caused a problem in the past.) If Angband's developers want to retain the unbiased partitioning code, it's trivial to change it to a 31 bit RNG. (Change two constants and then shift r >> 1 instead of r >> 4.) The
The game should work as well as the WELL RNG without the partitioning code. I wanted an unbiased RNG, and Angband still has one. I hope that the partitioning code is retained, yet I am willing to point out that it is optional.
For reference, following are excerpts from the current code:
HTML Code:
/* Partition size */ n = (0x10000000 / m); ... while (1) { /* Get the next pseudorandom number */ r = WELLRNG1024a(); /* Mutate a 28-bit "random" number */ r = ((r >> 4) & 0x0FFFFFFF) / n; /* Done */ if (r < m) break; } }
Specifically, for all values of N,
srandom(N); while(1) printf("%ld\n", random() & 0xF);
would print the same sequence of numbers as:
srandom(N%4); while(1) printf("%ld\n", random() & 0xF);
This means that the commonly used random() & 1 could only follow one of 4 sequences. (It's odd that no one noticed the bug for so long.)
I did a little research into the algorithm used in random(), and it was documented that the upper bits were "more random" than the lower bits, but not to the degree of my discovery. Soon after I publicized the bug in random(), a CERT alert was issued about random() and TCP packet sequence numbers. I'm guessing that wasn't a coincidence as I know that software engineers from Sun Microsystems were playing the game at that time.
My solution to the problem was to use the same algorithm but to rewrite the random() code in a different manner (for copyright reasons) and to include my code into the game (for portability reasons). Then I shifted off the useless 4 lower bits of the pseduorandom number. I had been waiting for an excuse to use my unbiased partitioning algorithm, so that got incorporated in as well. Before the partitioning code, "randomness" was somewhat proportionally correlated with the size of the maximun random number requested (N). After the partitioning code, "randomness" was inversely proportional to the size of N. (Which was desirable since I don't recall large random numbers ever being requested.)
As a new RNG has been incorporated in Angband, which presumably is better than the previous one, there shouldn't be any reason to restrict the RNG to 28 bit numbers. (A search indicates this has caused a problem in the past.) If Angband's developers want to retain the unbiased partitioning code, it's trivial to change it to a 31 bit RNG. (Change two constants and then shift r >> 1 instead of r >> 4.) The
The game should work as well as the WELL RNG without the partitioning code. I wanted an unbiased RNG, and Angband still has one. I hope that the partitioning code is retained, yet I am willing to point out that it is optional.
Comment