Random number tweaks


#1

Jules, it’s fun to look through your clean code. I’m just starting out by looking at some of the math routines I’m familiar with.

There’s a problem with Random::nextBool(), which is pulling samples from the lower entropy bits of the random pool. This means that the output has an unnecessarily short period of 2^17. Here’s an example which shows that with a seed of 123… the first bool is false and it’s repeated after a cycle of 2^17.

  Random r(123);
  for (unsigned long i=0; i<0x00400000; ++i) {
    bool z(r.nextBool());
    if ((i&0x1FFFF)==0) std::cout << std::hex << i << " " << z << std::endl;
  }

output:

0 0
20000 0
40000 0
60000 0
80000 0
a0000 0
c0000 0
e0000 0
100000 0
120000 0
140000 0
160000 0
180000 0
1a0000 0
1c0000 0
1e0000 0
200000 0
220000 0
240000 0
260000 0
280000 0
2a0000 0
2c0000 0
2e0000 0

Not a critical problem, but the fix is just changing one constant:

bool Random::nextBool() throw() { return (nextInt() & 0x80000000) != 0; }

Also, even more minor, but the nextInt, nextDouble, nextFloat are also throwing out entropy, though just one bit. You can double the period of the generator by changing the references from:

to

return ((uint32)nextInt()) / (double) 0xffffffff;

with the side benefit of getting an extra bit of range at the tail decimal of the double.

And finally, the nextInt(const int maxValue) method has a similar problem as the nextBool() call. The easy way to fix this is below, but a little inelegant since it uses floating point:

int Random::nextInt (const int maxValue) throw() { jassert (maxValue > 0); return (int)floor(nextDouble()*maxValue); }

All of these problems are disguised by the >>16 shift in the core Random::nextInt() call. Changing the LCG to be 64 bit (instead of 48 bit like now) would help a lot, with no extra storage or speed penalty.


#2

Ah - interesting! I’m not much of a mathematician when it comes to this kind of thing, I’m afraid!

I like your tweaks to the bool and floating point methods - thanks very much, I’ll take your advice there. Can’t decide whether it’s worth slowing down the nextInt method with floating point conversions though…


#3