Angband Forums Why the Angband random number generator is currently limited to 28 bits explained
 Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 July 20, 2013, 10:44 #1 rhutson Rookie   Join Date: Jul 2013 Location: In the Misty Mountains Posts: 23 Why the Angband random number generator is currently limited to 28 bits explained 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: 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; } }``` 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. Last edited by rhutson; July 22, 2013 at 03:14.
 July 20, 2013, 17:03 #2 Derakon Prophet     Join Date: Dec 2009 Posts: 9,024 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!
July 20, 2013, 22:41   #3
Magnate
Angband Devteam member

Join Date: May 2007
Location: London, UK
Posts: 5,057
Quote:
 Originally Posted by 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!
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.
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila

July 21, 2013, 03:32   #4
rhutson
Rookie

Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
Quote:
 Originally Posted by Magnate 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!

Last edited by rhutson; July 21, 2013 at 06:19.

 July 21, 2013, 11:33 #5 Pete Mack Prophet   Join Date: Apr 2007 Location: Seattle, WA Posts: 5,865 Donated: \$40 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!
 August 13, 2013, 10:50 #6 jrodman Apprentice   Join Date: Feb 2009 Posts: 56 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.
 June 20, 2016, 08:40 #7 brbrbr Adept   Join Date: Sep 2015 Posts: 104 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. Last edited by brbrbr; June 20, 2016 at 12:21.
June 20, 2016, 12:24   #8
AnonymousHero
Veteran

Join Date: Jun 2007
Posts: 1,372
Quote:
 Originally Posted by brbrbr 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?)

Quote:
 Originally Posted by brbrbr 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.

Quote:
 Originally Posted by brbrbr 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.

June 21, 2016, 08:14   #9
brbrbr

Join Date: Sep 2015
Posts: 104
Quote:
 Originally Posted by AnonymousHero 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:
Code:
```/* 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:
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.

June 21, 2016, 13:03   #10
AnonymousHero
Veteran

Join Date: Jun 2007
Posts: 1,372
Quote:
 Originally Posted by brbrbr It would be much cleaner and faster to use unbiased modulo code: 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.

 Tags rng

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Angband     AAR     Vanilla     Development     ToME     Sil     Variants     Competition The real world     Idle chatter     Oook! Obsolete     v4

 Similar Threads Thread Thread Starter Forum Replies Last Post LostTemplar Development 0 May 16, 2013 22:05 EpicMan Vanilla 3 December 4, 2010 06:10 Chud Vanilla 21 November 8, 2010 19:00 Jude Variants 44 November 19, 2008 21:44 TJA Variants 32 August 18, 2007 17:47

All times are GMT +1. The time now is 19:48.