Random number generator
From BenchIT-Wiki
BenchIT provides a pseudo random number generator in its Interface. The generator is independent from the used compiler and libraries. BenchIT-Kernels that need random values to generate their input data should make use of this feature. If the random number generator is initialized with the same value in every run it will allways generate the same sequence of pseudo random numbers. This avoids inexplicable differences between measurements on different systems due to the use of different builtin random number generators what is very useful to get reproduceable/comparable results from data dependent algorithms (sorting, searching, ...).
The generator internally uses 2 linear congruential generators and returns the bitwise xor of them to reduce the serial correlation. Both generators return uniformly distributed sequences and have periods in the range of 10^14. The periods of both generators are not the same what results in a even larger hyperperiod due to the xor. The quality of the generated sequence of pseudo random numbers is expected to be better than the sequences generated by the C standard function 'random()'(stdlib.h) or other simple generators. However, it's just a pseudo random number generator. It is not supposed to use this generator if real randomness is required.
usage:
Before you can use the generator it has to be initialized with a call of bi_random_init(start,max).
The 'start' value is used to set the starting point within the generators period. Internally 2 generators have to be initialized. The state of the first generator is set to the given start value. The state of the second generator is initialized with the first random number returned by the first generator. This ensures reproduceability but it is NOT POSSIBLE to save the state of the generator by storing the last generated number and reinitialize the generator with this number later on. This will result in a completly different sequence.
'max' is used as upper bound for the generated random number. The generator will return values 0<= random number < max.
After initialisation the bi_random32() and bi_random48() functions can be used to get random values. Both functions share the same state and cannot be used independent from each other. The only difference between them is the values margin and the return type.
parameters:
The generators use the formula r(n+1) = ((a * r(n)) + b) mod m. As we use 2 generators a1,a2,m1,m2,b1,b2 have to be specified. Additionally we need fix1 and fix2. Those 2 values specify the fixpoints of the 2 generators (fix= ((a * fix) + b) mod m).
The bi_random_init(...) function uses well tested predefined parameters for the 2 generators. Linear congruential generators are very sensitive to the choise of the parameters. Bad parameters will result in short periods and nonuniform distribution. It is strongly recommended not to change them!
If it is for some reason necessary to change the parameters here is what has to be considered:
- m1 and m2 have to be prime numbers > 2,815e+14 (more than 48 Bit)
- m1 and m2 are not the same number
- a1 is a primitive root of m1, a2 is a primitive root of m2
- a1 and a2 should not be a very small number (2,3,5,7,11,13)
- a1*m1 and a2*m2 are smaller than 2^64 (to avoid overflows)
- b1 is smaller than m1, b2 is smaller than m2
- fix1 = ((a1*fix1) + b1) mod m1, fix2 = ((a2*fix2) + b2) mod m2
- all parameters are positive numbers
The directory benchit_install_dir/tools/random provides some tools to find parameters that meet all restrictions.
Once you have found suitable parameters enter them in the bi_random_init(...) function. At the end of the bi_random_init function the fixpoints are replaced by other values. Make sure that those values really differ from the fixpoints.
