#include <rng_sfmt.h>
Public Member Functions | |
| RNG_SFMT (QObject *parent=nullptr) | |
| unsigned int | rand (int min, int max) override |
| Public Member Functions inherited from RNG_Abstract | |
| RNG_Abstract (QObject *parent=nullptr) | |
| QVector< int > | makeNumbersVector (int n, int min, int max) |
| double | testRandom (const QVector< int > &numbers) const |
Private Member Functions | |
| unsigned int | cdf (unsigned int min, unsigned int max) |
Private Attributes | |
| QMutex | mutex |
| sfmt_t | sfmt |
This class encapsulates a state of the art PRNG and can be used to return uniformly distributed integer random numbers from a range [min, max]. Though technically possible, min must be >= 0 and max should always be > 0. If max < 0 and min == 0 it is assumed that rand() % -max is wanted and the result will be -rand(0, -max). This is the only exception to the rule that !(min > max) and is actually unused in Cockatrice.
Technical details: The RNG uses the SIMD-oriented Fast Mersenne Twister code v1.4.1 from http://www.math.sci.hiroshima-u.ac.jp/~%20m-mat/MT/SFMT/index.html The SFMT RNG creates unsigned int 64bit pseudo random numbers.
These are mapped to values from the interval [min, max] without bias by using Knuth's "Algorithm S (Selection sampling technique)" from "The Art of Computer Programming 3rd Edition Volume 2 / Seminumerical Algorithms".
|
explicit |
|
private |
Much thought went into this, please read this comment before you modify the code. Let SFMT() be an alias for sfmt_genrand_uint64() aka SFMT's rand() function.
SMFT() returns a uniformly distributed pseudorandom number from 0 to UINT64_MAX. As SFMT() operates on a limited integer range, it is a discrete function.
We want a random number from a given interval [min, max] though, so we need to implement the (discrete) cumulative distribution function SFMT(min, max), which returns a random number X from [min, max].
This CDF is by formal definition: SFMT(X; min, max) = (floor(X) - min + 1) / (max - min + 1)
To get out the random variable, solve for X: floor(X) = SFMT(X; min, max) * (max - min + 1) + min - 1 So this is, what rand(min, max) should look like. Problem: SFMT(X; min, max) * (max - min + 1) could produce an integer overflow, so it is not safe.
One solution is to divide the universe into buckets of equal size depending on the range [min, max] and assign X to the bucket that contains the number generated by SFMT(). This equals to modulo computation and is not satisfying: If the buckets don't divide the universe equally, because the bucket size is not a divisor of 2, there will be a range in the universe that is biased because one bucket is too small thus will be chosen less equally!
This is solved by rejection sampling: As SFMT() is assumed to be unbiased, we are allowed to ignore those random numbers from SFMT() that would force us to have an unequal bucket and generate new random numbers until one number fits into one of the other buckets. This can be compared to an ideal six sided die that is rolled until only sides 1-5 show up, while 6 represents something that you don't want. So you basically roll a five sided die.
Note: If you replace the SFMT RNG with some other rand() function in the future, then you need to change the UINT64_MAX constant to the largest possible random number which can be created by the new rand() function. This value is often defined in a RAND_MAX constant. Otherwise you will probably skew the outcome of the rand() method or worsen the performance of the application.
|
overridevirtual |
This method is the rand() equivalent which calls the cdf with proper bounds.
It is possible to generate random numbers from [-min, +/-max] though the RNG uses unsigned numbers only, so this wrapper handles some special cases for min and max.
It is only necessary that the upper bound is larger or equal to the lower bound - with the exception that someone wants something like rand() % -foo.
Implements RNG_Abstract.
|
private |
|
private |
1.14.0
