Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

pseudo Random Number Generator improvements? #2565

Open
IIIlllII opened this issue Oct 20, 2019 · 1 comment

Comments

@IIIlllII
Copy link

@IIIlllII IIIlllII commented Oct 20, 2019

First of all excuse my ad hoc approach. If time allows I'll come up with a more scientific approach with better documentation.
Is your feature request related to a problem? Please describe.

  1. The following is actually more a question and less a request or proposal. Therefore I cannot present any solution or alternatives since I might be missing here something. If I'm not mistaken the frequently used method to calculate random numbers is genrand_int31() from mt19937ar.c (according to random.c and random.h). I'm wondering why the return value is shifted by 1 bit >>, since this pretty much removes 2^31 entries of the set of potential numbers.

  2. If I'm not mistaken the pRNG in mt19937ar.c is a multiplicative congruential generator. This could lead to repetitions and alternations especially in the lower bits field. This itself can lower the quality of random numbers but it might be increased if not even exponentiated by the fact how for example items to be dropped are chosen. According to mob.c this calculation is used: "if (rnd() % 10000 >= drop_rate)". So only entries of ~0x3F of a random number are used to determine whether to drop an item or not. All of the mentioned above might result in a poor distribution.

I ask you for any input or feedback. Please do correct me if anything is wrong or seems to be wrong. I really really appreciate it.

Describe the solution you'd like
One could contemplate to use a more sophisticated pRNG overall. To my knowledge there are a lot of very capable generators which to my understanding should be free to use, either published CC0 or GPL. They could improve the load on the server though which might not be desirable.

Describe alternatives you've considered
If you should choose not to change the pRNG there could be another improvement. To my understanding changing the line "if (rnd() % 10000 >= drop_rate)" to "if (Math.floor((rnd() * 10000)/ 2^32) >= drop_rate)" [assuming int32 architecture and overflows to be carried over] could improve the significance of higher bits of random numbers for the distribution.
Please do correct me on any mistakes and errors. Thank you for your time.

@MishimaHaruna

This comment has been minimized.

Copy link
Member

@MishimaHaruna MishimaHaruna commented Oct 22, 2019

You mention that the PRNG we're using is a multiplicative congruential generator, but to the best of my knowledge, it's a twisted generalized feedback shift register generator.

It's true that LCG/MCG generators and GFSR/TGFSR generators have several points in common, and that the MT we're using has some flaws (such as a very slow recovery from some initial states - which is resolved in an updated 'SFMT' version that I'm aiming to switch to as soon as I have time to test it), but it is generally considered a good and fast PRNG and very widely used. Details and papers at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

Do you have any data that you can share with us, that shows the way we're using it results in a poor, unsuitable distribution?

Concerning the other point you mention, the use of genrand_int31(), the reason is that it returns a positive signed 32 bit integer (in the range [0-0x7fffffff] - 31 bits + 1 sign bit, always 0), which is what we need most of the time, and is safe to store in an int without causing an underflow. It does so by sacrificing the least significant bit of the original 32 bit result.

Switching to another PRNG is of course an option, if there's any evidence that the Mersenne Twister isn't suitable for our needs, and if there's an efficient alernative (again, please provide data to back your claims)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.