Why the Angband random number generator is currently limited to 28 bits explained

[rhutson]

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:

        /* 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;
                }
        }

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.

[Derakon]

That's very interesting! Thanks for the information and the brief history lesson. Also, it's always nice to see another "old" dev return. Welcome back!

[Magnate]

That's very interesting! Thanks for the information and the brief history lesson. Also, it's always nice to see another "old" dev return. Welcome back!

Seconded - many thanks for the explanation. d_m implemented the WELL RNG but I don't see any reason not to keep the partitioning code.

[rhutson]

Seconded - many thanks for the explanation. d_m implemented the WELL RNG but I don't see any reason not to keep the partitioning code.

You're both welcomed! I was having a discussion on another forum in which I reminisced, "I remember going to campus to play Moria on a Dec terminal." That reminded me of Angband, so I decided to see what had become of the game.

I'm glad that we're in agreement on the partitioning code. Before the RNG was a function call, it was implemented as a C macro. Requests for a random number with a constant such a RANDOM(8) could be optimized by the compiler to avoid the use of a division assembly language instruction (or modulus if the assembly language had that). There was concern at the time that the combined overhead of a function with a division in it would slow down the game for some players. I've been playing for 2 1/2 hours now, and Angband has ony used 1 minute and 25 seconds of CPU time on a 5 year old Mac mini (2.4 GHz Intel Core Duo). I'd say that the game is sufficiently efficient.

Correction: That was an 1 hour and 25 minutes of CPU time, which is much more sensible than my prior claim. Obviously I need to be using larger fonts.

I must say that I am having a lot of fun. I've forgotten a few commands, but when it comes to game playing tactics that's like riding a bicycle. I'm coming across some new features. This is reminding me of the first time that I played Angband. I chose a human ranger (as that was my first character), and Farmer Maggot has dropped me a nice short bow.

Thanks to Ben for saving the game, and to all of the subsequent developers for your work!

[Pete Mack]

There's a lot more choice in playing Angband these days, much less roguelikes in general. If you ever played rogue proper, I'd give Sil a chance. It's a much more direct descendant than Angband, although it is derived from the (much-improved!) Angband codebase.

And I agree: Welcome back!

[jrodman]

I think this type of weakness in system rand functions was fairly common at some point. I ship some software on hpux and aix so I still don't trust system rand for anything other than some vaguely varying number. I use the openssl rand for useful values.

Then again my software doesn't need rand very often.

[brbrbr]

I am not developer, but very interested:

1) It's year 2016 and the 28 bit mutation remains. Maybe it's time to remove it from z-rand.c as rhutson suggested ????

2) void Rand_init(void)
{
/* Init RNG */
if (Rand_quick) {
....
Rand_state_init(seed);

Is it a bug? Rand_state_init initialize the COMPLEX rng, but it seems to be invoked withing QUICK rng block.

3) There seems to be error in z-rand.h function randint0
If the intention is to generate 0 < X < M, then definition should be:
#define randint0(M) ((s32b) Rand_div(M+1)),
not
#define randint0(M) ((s32b) Rand_div(M)),

The bug means all randint0 generate 1 lower values.

[AnonymousHero]

2) void Rand_init(void)
{
/* Init RNG */
if (Rand_quick) {
....
Rand_state_init(seed);

Is it a bug? Rand_state_init initialize the COMPLEX rng, but it seems to be invoked withing Rand_quick = TRUE block, which is the opposite.

Without looking at the code at all... not sure why Rand_quick even exists any more. Modern machines should be fast enough to use WELLRNG for all random number generation.

(Maybe it's something to do with having to force a seed and WELLRNG being slow at that?)

3) while (1) {
/* Get the next pseudorandom number */
r = WELLRNG1024a();

It seems ineffective to cycle through random values, until you find one, which is less than M.

You're certainly right that using a while loop to do this is absolutely horrible for performance -- not sure why it's done this way (but see below). I'm sure there are much more efficient ways to do it, though I don't know the right search keywords to find an appropriate algorithm on Wikipedia.

Would it be much faster to do
r = WELLRNG10245 % m +1
???

Yes, but that method can lead to bias in that the resulting values are not perfectly uniformly distributed across the entire interval. The problem becomes obvious if you look at the whole output range of WELLRNG -- let's assume 32 bits -- and then look at what happens of you map all the numbers in that range using f(x) = x % m. Now, if (2^32 % m == 0) then everything is fine and every "point" on the [0, m-1] interval is hit exactly the same number of times. In any other case, you'll have some "points" on the [0, m-1] interval which get hit once more than some of the other points. This leads to (very subtle) bias in the output.

The "while (1)" method doesn't suffer from this bias.

I'm not sure if this actually matters in practice for a game like Angband, but it obviously matters for statistical applications.

[brbrbr]

Yes, but that method can lead to bias in that the resulting values are not perfectly uniformly distributed across the entire interval. The "while (1)" method doesn't suffer from this bias.

I'm not sure if this actually matters in practice for a game like Angband, but it obviously matters for statistical applications.

Ok, that explains why simple modulo was not used.

Now, I have an issue understanding the "Rand_div" code.
For example:

/* Partition size */
n = (0x10000000 / m);

The usual call for randint is with m=100(decimal), that means the partitions are not of same size, which MAY bias the random number generator.

It would be much cleaner and faster to use unbiased modulo code:

#define RAND_MAX=0xFFFFFFFF; 
while(1)
{
  r =  WELLRNG1024a();
  if (r < RAND_MAX - RAND_MAX % m)
    return r % m;
}

That code will run 1 time most of the time. Unbiased.


The other issue is more serious, I think.
randint0 return values from 0 to m-1, not from 0 to m.
For example, the "desperate" spell chance calculation
randint0(100) < 50 gives max 99<50, not 100<50
Which is, probably OK, because 0 is also a valid value.
I havent' checked all the code for all randint0 calls, just worried the description is not correct and function may be misused.

[AnonymousHero]

It would be much cleaner and faster to use unbiased modulo code:

#define RAND_MAX=0xFFFFFFFF; 
while(1)
{
  r =  WELLRNG1024a();
  if (r < RAND_MAX - RAND_MAX % m)
    return r % m;
}

That code will run 1 time most of the time. Unbiased.

Yup, that method occurred to me a few minutes after posting . AFAICT it should work for unbiased uniform randomness.

The code has an error in the #define (there should be no "="), and may have other issues wrt. overflow -- not sure without thinking about it a bit more.

[takkaria]

The other issue is more serious, I think.
randint0 return values from 0 to m-1, not from 0 to m.
For example, the "desperate" spell chance calculation
randint0(100) < 50 gives max 99<50, not 100<50
Which is, probably OK, because 0 is also a valid value.
I haven't checked all the code for all randint0 calls, just worried the description is not correct and function may be misused.

z-rand.h says:

randint0: Generates a random signed long integer X where "0 <= X < M" holds.
randint1: Generates a random signed long integer X where "1 <= X <= M" holds.

I think these are accurate, no?

[brbrbr]

z-rand.h says:

randint0: Generates a random signed long integer X where "0 <= X < M" holds.
randint1: Generates a random signed long integer X where "1 <= X <= M" holds.

I think these are accurate, no?

No, randint0 generates from 0 to M-1.

So, I've tried to change macro to

#define randint0(M) ((s32b) Rand_div(M+1))

, recompiled the code, and got heaps of assertion failures.
Angband developers must used it correctly, despite wrong description.
Kudos!

[Derakon]

No, randint0 generates from 0 to M-1.

To be clear, a generator described as "0 <= X < M" should mean that M cannot be generated, i.e. M-1 is the maximum possible value. Are you saying that in fact M-2 is the maximum possible value? The "max is M-1" case is in fact desirable when picking a random item out of an array; if you tried to access item M then you would get an array index out of bounds exception (if you were working in a modern language, but in C you'd just get an access violation at best and major memory corruption at worst).

[Nick]

No, randint0 generates from 0 to M-1.

Which is precisely what "Generates a random signed long integer X where "0 <= X < M" holds." means.

X < M and X, M integers means the greatest value X can take is M-1. Trust me, I'm a mathematician.

[brbrbr]

Which is precisely what "Generates a random signed long integer X where "0 <= X < M" holds." means.

X < M and X, M integers means the greatest value X can take is M-1. Trust me, I'm a mathematician.

Ah, point taken. All good here.