pioneer
pioneer copied to clipboard
pioneerspacesim
Check random number generator
<jpab> I'm a bit concerned by the new random number generator
<robn> jpab: anything specific, or just gut feeling?
<jpab> specifically, I'm concerned by it only having 32 bits of state
<robn> so we need to stress it or something?
<robn> I'm no good on rng theory
<robn> I could revert it
<robn> it just makes startup so damn fast though :)
<robn> factions really hurt
<jpab> nah, don't revert, I'm just putting a marker in that I think we'll have to revisit it
Several years ago, I worked some time in the area of simulation studies of computer networks, where RNGs are heavily used. One rule for the cycle length I encountered there: "The use of PRNGs with adequately long cycles is also strongly advocated by recently established theoretical restrictions on the number of pseudo-random numbers from one PRNG that can be used in a single simulation. For example, if one is concerned with two dimensional uniformity of pseudo-random numbers generated by a PRNG with cycle length L, then one should not use more than 8*cubic_root(L) numbers from this PRNG during one simulation [15]." [1]
A random number generator with 32 bits of state space can only have a maximum cycle of 2^32 (I did not check if the RNG you use is full-cycle), which by the above rule would only yield approx. 13000 independent samples. So, 32 bits is not sufficient at all.
One reasonably fast alternative to the Mersenne Twister (MT19937) is WELL512, which has only 512 bits of state space (there also variants with 1024, 19937 and 44497 bits). It is closely related to MT but said to have better statistical properties [2]. I don't know if there is an implementation with a suitable license, though.
On the other hand, since independence in multiple dimensions might also be an issue and the MT implementation is already there, maybe you should just stick with that (even if it is slower).
[1] Pawlikowski et. al. On Credibility of Simulation Studies of Telecommunication Networks. Obtained from http://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2012_SS/L_19540_Modeling_and_Performance_Analysis_with_Simulation/2000_On_Crediblity_of_Simulation_Studies_of_Telecommunication_Networks.pdf
[2] http://www.iro.umontreal.ca/~panneton/WELLRNG.html
@robn @johnbartholomew @Brianetta Having just done a lot of stuff with the face gen I do have a concern about the RNG, I'm getting the same faces over and over and over again :/ Even just visiting a station I'll see the same face crop up two or three times out of maybe 6 or 7 possiblities.
It would be useful to have MTRand available for those cases where it's needed rather than have a single kind of RNG.
I think that cycle length should be the most important criterion for choosing an RNG for Pioneer, at least as far as universe generation is concerned. This isn't cryptography, randomness deficiencies are quite likely to be made imperceptible by producing non-obvious patterns, OTOH repetitions will just repeat.
And yeah, face gen does seem to repeat the same result over and over lately, but I thought it was a problem somewhere higher, maybe even an intentional behaviour until we get non-awful faces?
Revisit, anno 2021
Just doing some necro posting, to drop a link and summarize current state of random number generation issues in pioneer by:
- we've merged "Use PCG for random number generation" (#3485, which is where we have the main discussion on RGN),
- We might also have this: "Investigate the modulo bias in Pioneer" #4036
- New link: Random number generators for C++ performance tested]. I dunno about Xoshiro256+, but looks impressive by these charts:
The article also has some links for more reading on random number generation, in the last paragraph.