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

[takkaria]

Originally Posted by brbrbr

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]

Originally Posted by takkaria

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]

Originally Posted by brbrbr

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]

Originally Posted by brbrbr

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]

Originally Posted by Nick

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.

[rhutson]

Originally Posted by 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 ????

Feel Freel

Originally Posted by brbrbr

The bug means all randint0 generate 1 lower values.

once you have reached the Implementor level.

[rhutson]

Originally Posted by AnonymousHero

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.

The branch is rarely taken in my algorithm. I counted CPU cycles, and I would have never ever injected the inefficient abomination being described into Angband.

Requestfully, [someone] Git the source code, stick in global variables and report the ratio of successful test-branches / function calls. The ratio should be quite, quite low. (I have the source code, but the last time that I played Angband, I started at 6 pm. I had a level 20 character, but I was very sleepy. I looked at the time and wondered why I was so sleepy at only 3 am. Thirty minutes later, I realized that it was 3:30 pm and that I had been playing Angband for 21 1/2 hours. I'm too old for that and don't intend to play Angband again.)

While hardly a reference, the one - but not asserted only- person on this exchange http://stackoverflow.com/questions/1...mber-generator who can be trusted is Rob Napier. Java's implementation seems to me to be the most efficient, while I would say that my algorithm is slightly more efficient for the purposes of Angband than the arc4 algorithm. The performance differences between the 3 algorithms would not even be measurable in microseconds. The primary difference between the 3 algorithms is that I know that I was not paid to design my algorithm.

Originally Posted by AnonymousHero

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.

Correct. Angband's current RNG implementation does not suffer from any bias.

My motivation for putting my algorithm into the game was so that I could sleep well knowing that tomorrow's prayers and spells would be answered or rejected efficiently and unbiasedly. There is little practical difference between the old fashioned mod % N method versus using an unbiased algorithm. I just couldn't sleep knowing that Angband's RNG was not perfectly unbiased.

[rhutson]

Originally Posted by brbrbr

Ok, that explains why simple modulo was not used

And you now know exactly why a simple modulo was inconsistent with my continued existence.

Originally Posted by brbrbr

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.

You seem to me to be an eager student. I would simply share the headerless contents of the email that I sent to Ben explaining how the algorithm works, but I did not maintain a .record in those days. The easiest way for me to explain the algorithm to you would be to use pencil and paper and then scan and upload my diagrams.

Easier for me and as mind food for eager students, read Ben's comments in z-rand.c and then play around with a program that I wrote just today:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

uint32_t randit(uint32_t m)
{
    uint32_t n;

    n = (0x10000000 / m);

    return n;
}

int main(int argc, char *argv[])
{
    uint32_t i;

    assert(argc == 2);
    assert((i = atoi(argv[1])) >= 0);
    assert(i <= 0x10000000);

    printf("Part size %u\n", randit(i));
}

Then, please report back your findings! (I do apologize, and no one else would likely relate that my mind is mostly equally focused on the Pros and Cons of Hanging Guitars from a Vaulted Ceiling versus a floorful of guitar stands juxtaposed with the apparent impossiblity of replacing a John Deere lawn mower belt without removing the mower deck.)

Originally Posted by brbrbr

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.

With parameters of unknown value at compile time, mod is still slightly more expensive than div.

[AnonymousHero]

Originally Posted by rhutson

(About efficiency of the algorithm.)

Right, I think I originally misread the code, but just never corrected myself.

[rhutson]

Originally Posted by AnonymousHero

Right, I think I originally misread the code, but just never corrected myself.

I saw this discussion back in June, but clearly, my attention has been attending to more important matters, hence my delayed response.

There is a Lurking Humor in last night's posts. I was a couple of hours into a detailed study comparing the efficiencies and estimating the CPU cycles used by the 3 algorithms mentioned along with speed testing code, and then I wisely decided to use Nick's approach of "Trust me. I wrote it."€

As for the efficiency of my algorithm, I was pleased to discover that it is practically as efficient as reference grade library routines. The algorithm is just more obscure since I was dealing with a different core RNG which was known to produce less than pseudorandom sequences in the lower bits.

As for the 28 bit limitation, that can now be safely and trivially bumped up to a more classic 31 bit limitation. If it is really an issue, email me, and I'll email you back some diffs. But any major rewrite of known working code in such a vital section of the game for no obvious reason would be an ill-advised waste of time.