Better, smaller and faster random number generator

iq/rgba

With the 195/95/256 64 kbilobytes demo project rgba learnt something very important: don't subestimate how slow a data conversion can be. The problem came when debugging the software synthetiser made by Marc (Gortu). After several test and profiles, we found something really atonishing: one of the bottlenecks of the synth was the noise generator. That one was basically creating an integer pseudo-random number (using the same generator as VC) and then casting it to float and scaling it down to +-1.0 range. Here goes the original code:

```
static unsigned int mirand = 0;

float sfrand( void )
{
int a;

// ripped from VC libraries (disassembling rulez)
mirand = 0x00269ec3 + mirand*0x000343fd;
a = (mirand>>16) & 32767;

return( 1.0f + (2.0f/23767.0f)*(float)a );
}

```

It cannot be easier, right? However, as I said, the cast from int to float was simply killing performance. We new fistp instrucction was slow, but not so much! So I made some experients on creating a random number generator able to directly create a random float within the range of -1 to 1. The idea was really simple, and worked quite well: first try to create 32 bit random bits integer. Since the original algorithm of VC only gives 15 random bits, I made a fast investigation on the net to find that

mirand *= 16807;

was doing in fact better than

mirand = 0x00269ec3 + mirand*0x000343fd

and faster (just avoid initalizing "mirand" with 0!). In fact, the (16807,0) pair of values for the congruential random generator creates 32 random bits. So, the only thing I had to do was to interpret those 32 bit as a float value, and I should get a random float value, with no conversion at all! But still a small issue remained - how to make that float be in the correct range? I tried tweaking the appropiate bits in the exponent of my float (according to IEEE 754 standard, that is used in PCs and Macintosh machines, have a look at http://en.wikipedia.org/wiki/IEEE_floating-point_standard). So I carrefully selected the bits to be modified. This is the layout of the bits on the floating point format:

```
33        22                          0
10        32                          0
seee eeee efff ffff ffff ffff ffff ffff

```

where

s = sign bit
e = exponent
f = fractional part of the mantisa

value = s * 2^(e-127) * m, where m = 1.f, and thus 1<=m<2

The main idea is to realize that we allready have a random fractional part, what means we have a random mantisa between 1 and 2. We could just fix our exponent to 127, the sign bit to cero and that way we would get a random floating point number between 1 and 2. We could afterwards scale (by 2.0) and offset it (by -3.0) to make it fit in the segment [-1,1). But, we can do a bit better and avoid the scaling by directly generating a float random number between 2 and 4. For that we force the exponent to be 128, so that the output value is

value = s * 2 * m

that belongs to the range [2,4). So, first operation to do to our 32 randon bits is to mask the sign and exponent bits with

```
seee eeee efff ffff ffff ffff ffff ffff
0000 0000 0111 1111 1111 1111 1111 1111

```

or 0x007fffff in hexadecimal. We then just have to force the exponent to be 128 (10000000 in binary), so we do it with the bit pattern

```
seee eeee efff ffff ffff ffff ffff ffff
0100 0000 0000 0000 0000 0000 0000 0000

```

or 0x40000000 in hexadecimal. So, finally, the complete signed floating point random generator looks like:

```
static unsigned int mirand = 1;

float sfrand( void )
{
unsigned int a;

mirand *= 16807;

a = (mirand&0x007fffff) | 0x40000000;

return( *((float*)&a) - 3.0f );
}

```

It cannot be simpler and faster, perfect for a 4k or 64k intro! (well, some tricks can be done to this when translating to assemblre, of course). I made some measures to test performance, and I got 4 times the performance of the old generator. Regarding the quality, this generator is a lot better than generating a normal integer random value with rand() and then scaling it as the original function shown here does. Remember we are generating 23 random bits instead of 15. I also checked the density distribution, and in fact I found it to be perfectly uniform, and quite better than the old version. So, what else can we ask to our improved random number generator?