RecipesAtHome appears to be using C's standard library for random number generation, which is sketchy for a couple of reasons:
- the underlying implementation could be arbitrarily bad. it's almost certainly an LCG, which isn't inherently bad, but some internal constants work better than others. there's quite a few of them out there. Microsoft (msvcrt.dll) still seems to use
(x=x*214013+2531011)>>16 in particular.
- it probably uses a relatively small amount of internal state. the period of the lower bits of an LCG can be improved by mixing an internal, larger state into a smaller output integer type.
- it's not thread-safe, unless OMP is doing something fancy here.
additionally, there's a bit of bias in the way the RNG is being used. using a non-power-of-two modulus with a power-of-two-based RNG creates bias, unless the result is suitably re-rolled. there's also an instance of rand() % 100 < 50 where a simple rand() & 1 would suffice. (I suppose you were playing with the ratio at some point)
I think what this means is… edit: I'm looking at the code again with a clearer mind, and the impact should be minimal since handleSelectAndRandom typically falls through which does not invoke the RNG, assuming default settings.
anyway, I've thrown together an ad-hoc patch utilizing the PCG C library (on github) (Apache 2.0/MIT dual-licensed) that should resolve these issues. this library is still LCG-based, but: the constants should be sound, it implements output mixing, it supports up to 128-bits of internal state (what I've chosen), and it performs re-rolls for bounded queries. there are plenty of other libraries out there; this was simply the first to catch my attention. I didn't make this a pull request since my patch is kind of a hack.
RecipesAtHome appears to be using C's standard library for random number generation, which is sketchy for a couple of reasons:
(x=x*214013+2531011)>>16in particular.additionally, there's a bit of bias in the way the RNG is being used. using a non-power-of-two modulus with a power-of-two-based RNG creates bias, unless the result is suitably re-rolled. there's also an instance of
rand() % 100 < 50where a simplerand() & 1would suffice. (I suppose you were playing with the ratio at some point)I think what this means is…edit: I'm looking at the code again with a clearer mind, and the impact should be minimal sincehandleSelectAndRandomtypically falls through which does not invoke the RNG, assuming default settings.anyway, I've thrown together an ad-hoc patch utilizing the PCG C library (on github) (Apache 2.0/MIT dual-licensed) that should resolve these issues. this library is still LCG-based, but: the constants should be sound, it implements output mixing, it supports up to 128-bits of internal state (what I've chosen), and it performs re-rolls for bounded queries. there are plenty of other libraries out there; this was simply the first to catch my attention. I didn't make this a pull request since my patch is kind of a hack.