randomizer.html This file randomizer.dll Randomizer library bbs.ave Example of using BlumBlumShub algorithm bbskey.ave Example of generating keys for BBS moa.ave Example of using MotherOfAll algorithm gonzo.ave Benchmark example (see Comparison of Algorithms below) source_c.zip C++ source code for Randomizer moa_random.ave Avenue implementation of MotherOfAll algorithm moa_example.ave Example of using moa_random.aveRandomizer.dll encapsulates seven pseudo random number algorithms:
BBS BlumBlumShub MOA MotherOfAll MTW MTwister RNC RandC RSH Ranshi RRW RanrotW TPR TripleRandEach algorithm has two methods to return numbers:
XXX_GetIntegerA Returns n where min <= n <= max XXX_GetFloatA Returns n where 0.0 <= n < 1.0Two additional methods are used in initializing:
SetSeedA Sets the seed for all algorithms except BBS SetIntegerRangeA Sets min and max for XXX_GetIntegerAFor all algorithms except BBS, if the seed has not been explicitly set by SetSeedA, the current time is used.
Use SetIntegerRangeA to set min and max for XXX_GetIntegerA. Otherwise, 0 will be returned.
The following methods are used in conjunction with the BBS algorithm:
BBS_InitA Initializes the BBS generator BBS_BlumInitA Initializes BBS_GenBlumPrimeA and BBS_GenKeyA BBS_GenBlumPrimeA Generates Blum prime for BBS_InitA BBS_GenKeyA Generates key value for BBS_InitABBS must be initialized using BBS_InitA. Arguments P and Q are very large, different Blum prime numbers. (A Blum prime mod 4 equals 3.) Argument KEY is a quadratic residue mod (P*Q). If BBS_InitA has not been run, the numeric methods will return 0.
Some additional methods have been implemented to assist the user in obtaining P, Q, and KEY (see "bbskey.ave" for an example of their use):
BBS_BlumInitA initializes the FreeLIP pseudorandom number generator for BBS_GenBlumPrimeA and BBS_GenKeyA. SEED is a seed for the pseudorandom number generator. If SEED is 0, the current time is used.
BBS_GenBlumPrimeA generates a pseudorandom, highly probable (50 tests) Blum prime number for use as P or Q in BBS_InitA. (A Blum prime mod 4 equals 3.) Returns 0 if failed. The argument NUMBITS is the required number of bits for the resulting value. Run BBS_BlumInitA first.
BBS_GenKeyA generates a quadratic residue mod (P*Q) for use in BBS_InitA. Returns 0 if failed. Run BBS_BlumInitA first. Adapted from the bc code by Jeffrey I. Schiller [ http://www.mit.edu/afs/net.mit.edu/dapps/mit/jis/random/].
MotherOfAll (MOA) is taken from the Mother of All code by Agner Fog [ http://www.agner.org/random/].
MTwister (MTW) is an implementation of the Mersenne Twister algorithm by M. Matsumoto and T. Nishimura, adapted from the C code at: [ http://www.math.keio.ac.jp/~matumoto/emt.html].
RandC (RNC) uses the standard C++ library rand function.
Ranshi (RSH) is an implementation of the Ranshi algorithm by F. Gutbrod, adapted from the Fermilab HEP Random library at: [ http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/CLHEP/doc/html/CLHEP-random.html].
RanrotW (RRW) is taken from the RANROT W code by Agner Fog [ http://www.agner.org/random/].
TripleRand (TPR) is an implementation of the TripleRand algorithm, adapted from the Fermilab HEP Random library at: [ http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/CLHEP/doc/html/CLHEP-random.html].
Algorithm Run Time Arith Mean Chi Square Exceed Correlation Entropy ArcView 616 127.49 19841.74 0.01 -0.000061 7.998256 BlumBlumShub 25899 127.47 243.05 50 -0.000084 7.999982 MotherOfAll 814 127.52 266.63 50 0.000575 7.999981 MTwister 808 127.52 270.93 25 0.000304 7.999980 RandC 816 127.48 261.50 50 0.000208 7.999981 Ranshi 806 127.47 249.56 50 -0.000174 7.999982 RanrotW 806 127.51 238.13 75 -0.000245 7.999983 TripleRand 805 127.51 208.30 97.5 0.000429 7.999985Run Time = run time in seconds on a dual PIII 700 machine
Arith Mean = arithmetic mean (127.5 = random)
Chi Square = chi square distribution for 100000 samples
Exceed = the percent of times the chi square distribution would exceed this value (50 is random, values closer to 0 or 100 are less random)
Correlation = serial correlation coefficient (totally uncorrelated = 0.0)
Entropy = entropy in bits per byte (8.0 is maximum)
While the arithmetic mean, correlation, and entropy scores are good for all algorithms, ArcView fails miserably in the chi square test. TripleRand has the next worst score, and MTwister and RanrotW are marginal.
Another series of tests were performed using the program DIEHARD. For more information on DIEHARD see: [ http://stat.fsu.edu/~geo/diehard.html]. The results are given below:
Test ArcView BlumBlumShub MotherOfAll MTwister RandC Ranshi RanrotW TripleRand Birthday spacings 0.420 0.248 0.245 0.718 0.730 0.245 0.386 0.934 OPERM5[1] 0.780 0.026[4] 0.243 0.573 0.162 0.516 0.965 0.534 Binary rank 31x31 0.429 0.568 0.955 0.329 0.356 0.636 0.973 0.321 Binary rank 32x32 0.633 0.967 0.743 0.508 0.470 0.936 0.707 0.705 Binary rank 6x8 1.000 0.292 0.787 0.640 0.112 0.471 0.567 0.740 Bitstream[2] 1.000 0.915 0.835 0.146 0.000 0.184 0.967 0.270 OPSO[2] 1.000 0.304 0.118 0.451 1.000 0.637 0.586 0.790 OQSO[2] 1.000 0.495 0.340 0.819 1.000 0.026 0.172 0.036 DNA[2] 1.000 0.905 0.667 0.107 1.000 0.218 0.380 0.480 1's successive[1] 0.969 0.687 0.368 0.243 0.253 0.879 0.208 0.010 1's specific[2] 0.298 0.695 0.960 0.437 0.430 0.757 0.545 0.827 Parking lot 0.771 0.762 0.556 0.666 0.222 0.473 0.619 0.637 Minimum distance 0.666 0.744 0.782 0.461 0.793 0.586 0.483 0.581 3D spheres 0.286 0.341 0.133 0.120 0.863 0.552 0.558 0.782 Squeeze 0.901 0.487 0.413 0.336 0.303 0.683 0.140 0.453 Overlapping sums 0.834 0.640 0.466 0.243 0.966 0.382 0.310 0.297 Runs up[1] 0.738 0.302 0.546 0.448 0.388 0.900 0.325 0.801 Runs down[1] 0.800 0.920 0.542 0.182 0.310 0.932 0.669 0.928 Craps win 0.102 0.273 0.944 0.096 0.884 0.471 0.316 0.913 Craps throw 0.948 0.159 0.052 0.689 0.684 0.109 0.167 0.846 Tests failed[3] 5 1 0 0 4 0 0 1[1] Result of 1st test
[2] Result of KS test on multiple p values.
[3] Assumes that if p < 0.025 or p > 0.975, the algorithm fails at the 0.05 level.
[4] The second score is 0.000.
BlumBlumShub, while a favorite in the cryptographic community, is by far the worst in terms of run time. The next slowest algorithm runs in 3% of the time. Granted, the choice of FreeLIP as the large number library may be a factor. Nonetheless, the fact that other, far more efficient algorithms have comparable or better randomness scores would pretty much rule this out as an algorithm for scientific applications.
Of the remaining algorithms, putting equal weight on ENT and DIEHARD, MotherOfAll and Ranshi show the best overall randomness.