PSEUDO-RANDOM NUMBER GENERATORS
(REPORT II)
A report submitted in partial fulfilment of the requirements for the degree of Bachelor of Science
Z. O’Connell (950786535)
Department of Information Systems and Computing,
Brunel University
June 1999
Table of Contents
Table of Contents 2
1 Background 4
1.1 Definition and Scope 4
1.2 Objectives 4
2 Overall design 5
2.1 Structure 5
2.2 Files 6
2.3 Testing 7
3 Testers 8
3.1 Introduction 8
3.2 API 8
3.3 Library routines 8
3.4 Tests implemented 9
3.5 Unimplemented tests 12
3.6 General observations and conclusion 12
4 Generators 13
4.1 Introduction 13
4.2 API 13
4.3 Library routines 14
4.4 Implemented generators 15
4.5 Unimplemented Generators 19
4.6 General observations and conclusion 19
5 Front-ends 21
5.1 Tester 21
5.2 test-static 21
6 Conclusions 22
References 23
Appendix A – Evaluation 24
A.1 Project Overview 24
A.2 The Approach 24
A.3 Possible Future Work In The Area 24
Appendix B – Tables of results 25
B.1 Empirical test results 25
B.2 Speed test results 26
Appendix C – Source Code 27
1 Background
1.1 Definition and Scope
There are many known algorithms for generating numbers which are, or at least appear to be, random.
There are also a large number of tests to check that what is produced by such generators does closely
resemble a random stream. There is not, however, a currently freely available suite of generators and
testing routines allowing the user to eaisly define new generators and testers for experimental
purposes. This project implements the framework for such a system.
It would be impossible in the timescale to study every possible generator and test procedure available.
The project does however implement the most common of these and it should be very simple to add
new libraries as required.
1.2 Objectives
There are two main objectives:
To produce a portable set of pseudo-random number generators that can be easily used as
part of any application in a variety of programming languages
To test the random number generators for speed and randomness
The main consideration when writing these generators is portability and usefulness. Although in many
cases the generators are coded in such a way that they are slower than they could be trying to speed
up the generators would make the code less readable. The main suite of random number
generators/testers currently available, Diehard, [9 ] consists mostly of highly-optimized FORTRAN code
which has then been automatically converted to C. Even with a detailed knowledge of how the
generators and testers work it is usually impossible to figure out how the code works or adapt it for
other uses.
To achieve the objectives, we can break the problem down into three tasks which need to be
considered:
The generator library and a well-defined API (Application Programmers Interface)
The testing library and a well-defined API
A front-end that can be used to test the generators
2 Overall design
2.1 Structure
Each generator or tester is presented as a stand-alone file that, with the exception of combination
generators, does not rely on other generators. These libraries are dynamically loadable at run time or
can be compiled into a program, allowing the choice of generator to be specified by the programmer or
end-user as desired. There is also a central library of functions used by all the libraries to avoid
excessive duplication of code.
The code is all written in C. There are several reasons for this choice of language. Firstly, it is fast.
Most other languages are harder to optimize and perform bounds checking on arrays and variables
which, while normally desirable, will slow the generators down quite significantly. Secondly, it is
portable. C code can be compiled on almost any computer currently in existence. This allows most of
the generators, except combination ones which rely on dlopen() as discussed below, to be compiled on
virtually any platform. Finally, C code is easy to build into libraries and most programming languages
allow C code to be called from within them.
The development platform is Unix, (Linux primarily, also tested on Solaris 2.5.1) however as the code is
written with portability in mind and it should be easy to compile on other systems with only minor
modifications. There are two notable exceptions to this – dlopen() and gmp. Dlopen() is used to load
libraries dynamically and is only available on some systems. It is used primarily by the front-end tester
but also by some of the “combination” generators. The combination generators could be modified to link
in their component generators statically although this would take quite a bit of work to allow all the
generators to have “alternative” function names when used as component generators. Combination
generators perform poorly both in terms of speed and randomness however so this doesn’t seem
worthwhile.
The ICG generator uses the GMP GNU multi=precision math library for doing inverse multiplication.
Although this library will compile on the majority of systems it is not generally installed as standard.
Both the generators and testers work on bit-streams rather than floating point numbers. Although most
older random number generator systems generate floating point numbers they are harder to analyze
and reliance on floating point math would slow down the generators. It would be trivial, if required, to
convert the output from this API to a floating point number. Care should be taken to ensure that the
granularity of the numbers obtained from a generator is sufficient however – clearly taking a single bit at
a time is going to produce poor results if three decimal places of randomness is required.
2.2 Files
Makefile Instructions for building the programs (See below)
*.c Source code
*.so Compiled dynamic-link libraries
librnd_name.* Generator “name” (See section 4.4)
libtest_name.* Tester “name” (See section 3.4)
random.h Global function definitions, included by every generator.
librandom.* Useful routines used by many generators and testers. (See sections 3.3 and
4.3)
tester Simple testing program that loads in generators and testers dynamically. (See
section 5.1)
test-static Statically linked example showing the display tester and the Mersenne Twister
generator. (See section 5.2)
random.dat Random source used for the file generator and as a seed by other generators.
(See below)
Each generator/tester is a separate source (.c) file and compiles into a separate object (.o) or library
(.so) file.
2.2.1 Makefile
The Makefile is used to compile the code by simply typing make on a Unix system. make -k should
normally be used to force make build all the libraries even if some fail as the ICG generator will only
compile if the gmp library is present. There are only two things that need to be changed in the Makefile
in the normal course of events. The first is the CCOPTIONS line. Normal options would be -O6 -Wall,
indicating full optimization and all compiler warnings. Other useful options are -DVERBOSE to turn on
extra output in generators and testers and -g instead of -O6 to enable debugging symbols in the output
files for use with debuggers such as gdb. -DQUIET can be used to suppress all output from testers.
This is for use when testers might want to be included in a larger program although isn’t the most
common case and therefor isn’t the default option.
If desired, the libraries compiled into test-static can be easily changed here, demonstrating how easy it
would be to incorporate a new generator as part of a program using this API. Debuggers don’t handle
dynamic linking particularly well so in most cases it is eaiser to link a specific library statically as part of
test-static for debugging.
Typing “make clean” will delete all the compiled libraries and executable.
The variable LIB_GCC is a workaround for an apparent bug in the gcc and egcs compilers. For some
reason, under certain circumstances involving dynamic linking not all the correct functions for unsigned
long long math are included in librandom.so. Adding the libgcc library specifically resolves this problem.
2.2.2 Random.dat
For a “true” random source and as a seed for some generators, this file was downloaded from a
hardware source on the Internet. [10] The web site doesn’t allow large downloads in one go, so around
a hundred separate files were downloaded and concatenated together to produce one larger file.
2.3 Testing
Although the generators are tested by the testers, the testers themselves need to be validated to
ensure they give the expected results. To do this, we can use generators known to be “perfect”, such
as cryptographic generators, which should not fail any statistical test. There is a small probability that a
truly random source will produce non-random output however this possibility is very small given the
amount of data being generated and this problem was not encountered.
There are also certain expected results for most tests, as almost every paper discussing a testing
mechanism gives several tests and the results obtained by the author. However,there are many ways of
implementing certain tests and some generators do fail tests they have been shown to pass in other
situations.
3 Testers
3.1 Introduction
The testers are presented as separate libraries which can either be linked in with a program at compile-time or, if supported on the specific platform, dynamically selected and loaded at run-time. The output is
a boolean pass or fail indication for a particular generator, although all the testers produce additional
human-readable text to showing what results were produced. It is not expected that testers will be
called automatically by programs using the libraries, however in same cases this may be desirable.
Some applications may wish to produce a different set of random numbers each time without saving the
state of the generators between each run. However, some “seed” values for generators may produce
poor output. A good tester, such as Maurer, can be quickly applied to a particular generator with a
certain seed value to check if it produces sane output.
3.2 API
There are only two functions required for the tester modules:
int rantest_test(void *state, getbits function)
char *rantest_info_text(void)
Rantest_test takes a pointer to a generators state array and a pointer to a getbits function and
produces a single boolean result to indicate pass or fail. All of the testers produce some sort of
diagnostic output however giving actual p-values where appropriate, and if VERBOSE is defined in the
Makefile they will usually give details of the internal counters. Verbose output is usually unlabelled
however and only really interesting for debugging purposes.
Rantest_info_text simply copies a descriptive string into scratch and returns a pointer to that. It is
implemented this way, rather than by a static text string in the generator, so that extra dynamic
information on the test library could be output, as with the generators, although this is never actually
used.
3.3 Library routines
There are two routines in librandom.c called by testing routines. These are:
double ChiSqPN(unsigned long df, double x)
double KolSmirP(unsigned long df, double x)
ChiSqPN takes degrees of freedom and a value and calculates the p-value for the Chi-squared
distribution from x with df degrees of freedom. The code is adapted from poorly documented Javascript
by Ritter [8] as no other readily-implementable formulae or algorithms were available. This routine
works by normalising x and then passing that to NormalP which actually calculates the p-value for the
normal distribution using a fairly simple formulae.
KolSmirP is also adapted from code by Ritter but is far more complicated and difficult to understand.
Similarly to ChiSqPN it calculates the p-value for the Kolmogorov-Smirnov distribution from x with df
degrees of freedom. Unfortunately, the Kolmogorov-Smirnov distribution has even less information
available about it than the Chi-squared distribution and the source of the underlying algorithm isn’t
known.
3.4 Tests implemented
3.4.1 Display tester
This “display” test simply prints the first 100,000 16-bit numbers from the generator being “tested”. This
is for manually checking the output of a generator is sane, (No leading zeros/all zeros output) doesn’t
have an incredibly short period and for manually checking that a generator is iterating according to the
correct formula.
3.4.2 Speed tester
The speed test measures how fast the generator can produce 2,000,000 16 bit numbers and the results
are presented in Appendix A. Three platforms were measured, Intel, Sun and Alpha, although not all
platforms were directly available so only Intel results are given in full. The test is slightly unfair in that
generators that produce results in multiples of 16 bits will perform better as rangen_generic_getbits is
faster when bits are being requested in multiples of the generator bits per iteration. The reflects how the
generators would probably be used in practice however. There are few surprises here, the generators
perform as would generally be expected and in roughly the same order on all platforms. The file
generator appears slightly faster than all zeros on Intel because it loads a 64-bit value into STATE->output every iteration whereas the zero generator only loads 32 bits a time.
The tester actually measures the CPU time elapsed for the process rather than the actual time elapsed
so even on a fairly heavily loaded machine results will be accurate. On faster generators, however, the
granularity of the system clock seems to cause a problem and affect results by about 5%. The
compiler used can make a more significant difference and can affect results by as much as 50%. On all
platforms, the tests used the gcc compiler. On the sun platform however the sunpro compiler was
found to be between 30% and 300% faster than gcc for various generators.
The speed of a generator can heavily affect the choice of generator for an application – a generator
such as the linux /dev/random, whilst highly random and unpredictable, is far too slow if tens of millions
of random numbers are required.
The speed test always passes a generator.
3.4.3 Chi-squared
The simple statistical chi-squared test fails a surprising number of generators given that it is
independent of ordering. We test ten million 16-bit values however, which will tend to cause any
generator with a period lower than a few million to fail badly. Almost every generator which fails another
test also fails Chi-squared although this is more likely to be coincidence that poor generators also have
shorter periods that are detected by Chi-squared. Generators with short periods fail because slight
deviations from the expected distribution are exaggerated as they loop and give the same values again.
Chi-squared is a two-tailed test so a low value is as bad as a high one – LCG 2 fails as the values are
too close to the expected distribution to be random. A generator passes this test if 0.005 < p < 0.995 -
i.e. it passes at the two-tailed 1% level.
Because this generator is “two-tailed” it detects sequences that are “too random” – i.e. that fir the
expected distribution improbably well – as well as those that are not random enough. LCG 2 exhibits
this property – it gives a Chi-squared value of zero.
3.4.4 Kolmogorov-Smirnov
The KS test is really just a weaker version of the Chi-squared test and fails most of the generators that
Chi-squared picks up. Each result is one-tailed – I.e. it only fails if too high not too low – but two values
are produced and the test fails if either are too high. This tester is weaker than Chi-squared primarily
because calculating the p-value for ten million degrees of freedom is too time-consuming
computationally whereas the million degrees of freedom used are much faster. This test and other tests
based on it passes the test if p < 0.99 - i.e. it passes at the one-tailed 1% level.
3.4.5 Gap test
The gap test measures the distributions of gaps between occurrences of a number fits the expected
distribution. This test actually measures using chi-squared the distribution of gaps between each
possible 8-bit number individually and then performs a Kolmogorov-Smirnov test on the results.
Because of this the test proves to be very powerful – it picks up flaws in generators that every other test
passes. LFSRs and FCSRs failing is a surprise, although looking at debug output by uncommenting the
commented out code lines in the tester shows that the two linear feedback generators are failing due to
extremely long gaps between certain numbers. (This produces a lot of output)
3.4.6 Poker test
The poker tests measures occurrences of the same digit in a four-digit hexadecimal number generated
by the generators. Because we are doing this test on bit streams rather than floating point numbers,
any non-randomness here should also be picked up by the Chi-squared test and this is indeed the
case.
3.4.7 Runs up/runs down
This test proved very difficult to implement as Knuth’s description for calculating the matrices required
for this test isn’t clear. The matrixes, a and b, are hard-coded into the program however as they do not
change when other parameters of the tester change. This tests fails weak generators as expected and
is reasonably powerful. One surprise is that it fails the FCSR generator, which no other tester other
than the gap test fails. The two results this tester produces are Chi-squared vlues for runs up and runs
down.
3.4.8 Runs above/below the mean
This is a very weak test and fails only the poorest of generators. This generator produces four outputs –
a pair of KS results for each of runs above and below the mean. This test doesn’t fail the zero
generator because of a peculiarity in the formulae which will only occur when the entire input is above
or below the mean.
3.4.9 Maurer’s Universal Statistical bit test
Maurer’s test almost lives up to his claim of being able to detect any flaw in a generator detectable by
other means although fails to spot flaws spotted by the gap tester. Unfortunately, his original paper lists
an incorrect expected value when calculated on 16-bit numbers, so the test was conducted only on 8-bit. Maurer’s paper lists the expected value as 15.1670.001 whereas experimental evidence strongly
indicates a value closer to 15.159. The version of the code implemented is a hand-converted C version
of Maurer’s Pascal code [5] and performs flawlessly on 8-bit numbers so the error appears to be in the
expected values provided. The error appears to be mathematical, not typographical, as the same value
is repeated elsewhere within the paper. Unfortunately, calculating the value to the required precision for
testing a million random numbers (Maurer’s code only tests 20,000 8-bit numbers) requires 200,000
iterations of the formula which to achieve in a reasonable amount of time requires more computing
power than readily available. (A bc script to calculate it had not completed after over two days of
running on a PPro200 when the machine was shut down)
3.4.10 File tester
This tester simply writes 2 million bytes of the output of the generator as binary data to a file called
output.dat. This file can then either be renamed for use as a seed/input for other generators or used for
some other purpose.
3.5 Unimplemented tests
3.5.1 Serial correlation
This test isn’t implemented as no exact version of it appears to exist. Knuth gives a version but only
gives conjectured formulae for the expected values which appear not to fit well with actual empirical
results. This test is not included in modern random number packages and appears to have fallen into
disuse, possibly because it measures similar properties to other non-statistical tests such as the run
and gap tests.
3.5.2 Marsagla’s “Stringent” tests
Without further analysis, Marsagla’s tests are not easy to implement. The information supplied with
Diehard [9] is insufficient to easily figure out the algorithm being used for some tests. Unfortunatly, as
has been mentioned previously, the code in Diehard is totally impenetrable and gives no clue as to the
authors intentions.
3.6 General observations and conclusion
Implementing some of the testers, particularly the more common “Knuth” types, proved quite difficult
due to conflicting and inaccurate literature. For example, Banks et al. Give the number of degrees of
freedom for a gap test as the sample size whereas in practice it is actually the number of discrete
values the output can have. (256 for an 8-bit output) The error in Maurer’s paper, mentioned previously,
is another example of this problem. Peer-review of papers in this area appears poor, possibly because
most current work concentrates on cryptographic generators and there is currently little interest in non-cryptographic implementations.
When testing new generators, it would seem sensible to test using Maurer’s test or the Gap test first as
they are the most powerful tests which are more likely to reject a generator than any other if it is
flawed. The generator should then be tested against the other, less powerful, tests if desired.
4 Generators
4.1 Introduction
The generators use a similar API to the testers. The internals of the generator are normally kept hidden
from the calling program so that generators can be changed and the program relinked with no
modification. There are routines for changing the internal variables of a generator however and these
can be used by programs with a greater knowledge of the internals of a specific generator or by a user
to select different values for the generator, either for testing purposes or because specific values might
be more appropriate for a certain applications. Programs can get values from a generator by means of
a routine which extracts a specified number of bits at a time. There is also an information routine in
each generator which will output a textual description of a generator.
4.2 API
There are many more routines used by the generators than there are for testers. These are:
char *rangen_info_text(void *state);
unsigned int rangen_info_statesize(void);
void *rangen_create(void);
void rangen_init(void *);
void rangen_iterate(void *state);
char *rangen_info_getparametername(unsigned int number);
unsigned long long rangen_info_getparametervalue(unsigned int parameter void *state);
void rangen_init_setparameter(unsigned int parameter, unsigned long long value, void *state);
unsigned long long rangen_getbits(void *state, unsigned int bits);
In addition, the state structure should begin as follows:
struct state_struct {
unsigned long long output;
unsigned int outputbitsavailable; };
Rangen_info_text takes a pointer to generator state and returns a pointer to a string giving details of
the generator. If VERBOSE is defined in the Makefile this can include details of the current generator
settings. Rangen_info_statesize returns the current size of the state array which can be used to make a
copy of the generator or, if desired, save it’s current state to disk. Generators that cannot be copied or
saved to disk in this way return 0.
Rangen_create allocates memory for a generator state and returns a pointer. It will also usually fill in
some reasonable default values for the generator. Rangen_init should be called once all parameters
have been set using the state pointer to initialize any arrays and values before rangen_getbits is called
for the first time. If parameters are changed and rangen_init is not called before the next call to
rangen_getbits, behavior is undefined. This will make some generators crash as checks for this are not
performed in the interests of speed.
Rangen_info_getparametername returns a pointer to a string describing parameter number. If number
is higher than the maximum parameter number, NULL is returned. If the first three letters of a
parameter are “Alg” (Short for algorithm) the value required is a pointer to a generator function and the
next parameter is a pointer to generator state. Rangen_info_getparametervalue takes a state pointer in
addition to a parameter number and returns the value of that parameter. Similarly,
rangen_info_setparametervalue can be used to set a value. If parameter zero is available it should be a
value appropriate for “seeding” the generator. No guarantees are made as to how well any particular
seed value will perform however.
There is no sanity checking performed on values selected in this way and unpredictable things (Like
crashes) could happen if invalid values are entered.
Rangen_getbits is the most-used routine and returns an appropriate number of bits from the generator.
In all the generators implemented her this is simply a call to the library routine rangen_generic_getbits
discussed below. Rangen_iterate is intended primarily for use by librandom for putting a new value into
STATE->output. STATE->output always contains the current generator output and STATE->outputbits
the number of bits of random number left in STATE->output.
Throughout the generators, STATE is used as a shorthand for ((struct state_struct *)state). This is
because the state is always passed as a void pointer so that programs without knowledge of the
generator internals can pass it around and thus it requires explicit typing every time it is referenced.
4.3 Library routines
Two library routines are used by generators. These are:
int countbits(unsigned long long);
unsigned long long rangen_generic_getbits(void *state, unsigned int bits, void (*iterate)(void *));
Countbits is used simply to count the position of the left-most one in a binary number and is used by
generators such as Von Neumann and LCGs either as part of the algorithm or to calculate the number
of random bits generated per iteration.
Rangen_generic_getbits takes a state pointer, which must start in the way described above, a number
of bits desired and a pointer to an iteration function and will iterate an appropriate number of times to
produce the desired number of bits. Every generator implemented here uses this routine.
4.4 Implemented generators
4.4.1 “Reference” generators
There are three generators which are implemented to allow testing of the testers. These are Linux, File
and Zero – any valid test should pass the first two and fail the zero generator.
The “Linux” generator uses the crypto-random generator present in the Linux operating system kernel
which uses internal hardware sources of the machine to generate an unpredictable bit stream. The
generator actually uses the non-cryptographic file /dev/urandom as this is much faster than the
cryptographically secure generator /dev/random. It still uses cryptographic functions and hardware
sources so is indeed random.
“File” reads random data from a file “random.dat”. The file used in testing was generated from
http://www.random.org/, which gets data from a hardware random source. The reason this generator
fails the Chi-squared test is because the file in use was only 2Mb and twenty million bytes (10,000,000
16-bit numbers) were tested.
Although primarily intended to test the testers, these two generators could be used in real-world
applications if relatively small amount of randomness is required. There are faster and more convenient
generators available however.
“Zero”, as the name implies, simply generates a stream of zeros.
The Zero and File generators also give an indication of the maximum possible speed of a generator –
I.e. how much is lost in function call overhead compared to actual computational time. The file
generator is marginally faster on Intel because it works on 64 bits values whereas the zero generator
only generates one 32-bit per call to rangen_iterate. (The file generator was reading data off a remote
filesystem on the Sun machine, hence the lower speed)
None of these generators take any parameters and their state cannot be saved.
(Rangen_info_stateside returns zero)
4.4.2 C Library generators
The “Rand” generator tests the properties of the random number generator random() in the system C
library. Rand 1 is results from a Linux machine running glibc2, which performs admirably and is also
reasonably fast. The source code for the library doesn’t give references as to the source of the
generator but it appears to be a “polynomial” type of some description. On a glibc2 machine, this
generator is certainly more than acceptable for randomness although slower than other generators.
Rand 2 are results from a Solaris 2.5.1 machine and passes all the tests except Chi-squared.
Documentation claims this is a “non-linear additive feedback” generator with a period in the order of
2^31 which if true indicates that this failure isn’t in fact due to a small period in the generator but to a
major flaw in it’s implementation.
This generator takes no parameters.
4.4.3 Von Neumann
The Von Neumann generator as implemented performs poorly in almost all tests. The version used is a
“Binary” version – taking the middle binary digits and squaring them – rather than the original decimal
version Von Neumann proposed. A hexadecimal version could also easily be implemented, although
would offer no obvious benefits over the binary version. The original “decimal” version of this generator
would be much slower and also offer no improvement over the binary version.
This generator takes one parameter – number zero is the current internal state of the generator and can
be used to “seed” the generator. The default seed value used is one that has been observed to
perform reasonably well in the Maurer test, which is the most powerful test available, compared to other
seed values. Although this is a relatively fast generator on most platforms it’s failure in over half the
tests makes it unsuitable for use.
4.4.4 Linear Congruential Generator
The values used in LCG 1 are those suggested by Knuth and those in LCG 2 are the defaults compiled
into the generator as suggested by Ritter. Neither set performs particularly well, failing even the Chi-squared test suggesting that the period of these generators is quite low. Although other values may
perform better the generator as implemented is reliant to m being a power of two as we are producing
random bit streams rather than random floating point numbers. Converting from values of m other than
powers of two into a random bit stream is very difficult to do without destroying the randomness of the
generator. LCGs are the most common generators in current usage however because although slower
for large batches of numbers they are easily implemented and fast if only a few values are needed.
This generator takes four parameters. Parameter zero is the internal state of the generator and can be
used as a seed. The first, second and third parameters are m, c and a respectively. M is the modules
of the generator, c the value added each cycle (Zero for pure Multiplicative Congruential Generators)
and a the multiplication value.
4.4.5 Additive Congruential Generators
ACGs perform incredibly well given their simplicity and speed. The initial table used is based on the first
few values in the file used for the “File” generator with a default “lag” of 97. This is the only generator
actually implemented other than Mersenne Twisters that actually passes all the tests and achieve over
a million numbers per second on a PPro200.
This generator takes two parameters. Parameter one is m, the modules and number two is k, the “lag”.
As this generator cannot be usefully seeded in it’s current incarnation there is no parameter zero.
4.4.6 Inversive Congruential Generators
ICGs perform disappointingly, failing every single test, even the very weak runs above/below the mean
tests. Looking at the output it is clear this generator has a very low period – a few hundred – making it
totally useless. There appear to be some suggestions that this is a good generator however I can find
no source that states this with any certainly. Due to it’s use of inverse multiplication it is also very slow,
making it unsuitable for general use. This generator is further hindered by it’s use of the external library
“gmp” – the GNU Multi-Precision math library – for inversive multiplication, which is probably not present
on all systems.
Although it might be possible to speed up this generator and increase it’s period, there seems little
reason to do so. As there is no “hidden” state in this generator it’s maximum period is it’s modules as
with LCGs and there appear to be no benefits of this generator over LCGs despite being slower so the
effort does not seem to be worthwhile.
The parameters of the ICG are the same as for the LCG – zero is the state then one to three are m, c
and a.
4.4.7 L’Ecuyer
The L’Ecuyer combination generator also performs poorly. L’Ecuyer doesn’t give a convincing argument
as to why the output should be uniformly distributed and looking at the verbose output of Chi-squared is
clear there is bias towards particularly high or low results. The bias is only significant for a reasonably
large sample size, greater than 10,000, which is probably why L’Ecuyers original testing of his
generator did not spot this flaw.
The API as defined can not handle an arbitrary number of sub-generators, as L’Ecuyer uses, so the
configuration of this generator is static and there are no parameters.
4.4.8 Algorithm M
Algorithm M performs comparably to the LCGs – It is based on the same generator as LCG 1 for it’s
actual output, shuffled by another identical LCG generator. Although the output of the generator in
terms of it’s ordering is “more random” than a plain LCG, the LCGs used pass most of the ordering-dependant However, LCGs do fail a Chi-squared test and shuffling the output does not help here as
Algorithm M also fails the Chi-squared test.
Algorithm M has quite a few parameters. Firstly, powerk defines how big a “shuffle box” is required –
the implementation limits this to powers of two so, for example, setting powerk to 8 gives a box of size
256. Parameter two is the number of bits obtained from the generator each cycle. Parameters three
through six are the algorithm and state for the two generators X (Number source) and Y. (Shuffle
source)
4.4.9 Linear Feedback Shift Register
This generator passes most of the tests well. Rather surprisingly it fails the gap test, which examination
of verbose output reveals is due to very high gaps between certain reoccurances of the same number.
Unfortunately, because they have to work bit-by-bit it is rather slow to implement in software and are
nearly and order of magnitude slower than Mersenne Twisters and ACGs which perform just as well.
The default settings for the tap bits on this generator is taken from Schneider [4].
There are fiver parameters for this generator. Parameter zero is, as always, the current state and can
be used to seed the generator. (Although a seed of zero will produce a zero output) Parameters one to
four are the tap bit locations, from 0 to 63.
4.4.10 Feedback with Carry Shift Register generators
As with LFSRs, FCSRs suffer from the same failure in the gap test and are even slower. They offer no
obvious advantage over FCSRs and take the same parameters.
4.4.10 Mersenne Twisters
The code for the Mersenne Twisters is adapted from the original code by Matsumoto and Nishimura
[12] with no major modifications. Despite it’s reliance on a relatively large number of operations per
cycle mathematical operations it is very fast as it generates over eight thousand random bits each time.
Rangen_iterate doesn’t return all generated bits every time it is called but breaks them down into more
manageable 32-bit chunks – the real iterate routine is called as required. This generator passes all the
tests easily without any problems and because of it’s speed seems the generator of choice where
anything more than a few random numbers are required. “Seeding” this generator would be difficult as
the initial state is relatively large (Over 8 thousand random bits) although this could be overcome simply
by taking an offset into an existing random source, such as the random.dat currently used to seed the
generator.
Mersenne Twisters have no configurable parameters.
4.5 Unimplemented Generators
4.5.1 Wichmann & Hill Combined
This generator, presented in [2] only produces floating point results and there is insufficient information
in the paper to determine the granularity of the generator which would be required to convert the output
to a bit-stream efficiently.
4.5.2 Polynomial Congruential
As seen by the results of the Rand test, Polynomal Congruential generators are both reasonably fast
and quite random. Unfortunately, although this syle of generator is used by glibc2 and also mentioned
by Knuth insufficient information is available to attempt a decent implementation.
4.6 General observations and conclusion
Implementing the generators proved a much eaiser task than the testers. To construct a good generator
far more theory is required and invariably all the generators include either working code or an algorithm
that can be used to quickly produce working code.
It is clear from the table of results in Appendix B that Mersenne Twisters and ACGs are by far the
generators of choice. They are both very fast and fail none of the tests presented here.
5 Front-ends
5.1 Tester
The first and most useful front-end, “tester”, takes the name of a generator and tester library and runs
them. This program shows how to dynamically load tester libraries on a Unix system that supports
dlopen(). It is necessary to set the environment variable LD_LIBRARY_PATH to the directory holding
the libraries or install the libraries in the system libraries directory so that the dynamic linker can find
them.
Tester is called with two arguments, firstly the full filename of a generator library and second the full
filename of a tester library, for example:
tester librnd_mersenne.so libtest_display.so
(Assuming “tester” is in the current PATH)
If VERBOSE is defined when compiling a library then tester first outputs a short text description of each
library obtained using the info_text functions.
If there are any configurable parameters for the generator then tester will prompt for them one by one,
showing default values. The default values can be accepted by just pressing enter without entering any
data.Tester cannot handle “Alg” type parameters and ignores them.
5.2 test-static
The second tester, test-static, shows how simple it is to include a generator (And tester) in a program.
The libraries included in the static executable can easily be changed by modifying the
STATIC_LIBRARIES variable in the Makefile. Default settings produce a completely static executable,
i.e. one that requires no support libraries other than the standard C libraries. Substituting the .so files
for .o gives a dynamically linked version, where the library files are required to run the program, but
with no modifications to the source. This latter method is the preferred method of linking in the random
number libraries as if a generic name, such as librndgen.so, is used the generator can be changed
merely by replacing the library file with no need to change the source code.
6 Conclusions
The results here are not entirely surprising. As noted in the first report, both Mersenne Twisters and
ACGs were expected to do reasonably well. The failure of LFSRs is a surprise however, as these seem
to be regarded as reasonably proficient generators and although slow in software are often used in
hardware implementations. The failure of combined generators is also somewhat surprising, although
recent research work has moved away from this and into totally new generators.
There is little to be said about the testers as they all performed as expected. It is worth reiterating the
poor quality of work on random number testing however, in the hope that someone may eventually
produce a work that actually includes algorithms for implementing tests quickly and accurately.
Algorithms for this are very thin on the ground and often had to be derived from ambiguous statements
and the ambiguities resolved by experimentation.
References
[1] Knuth, D.E., 1969, The Art of Computer Programming, Volume 2 – Seminumerical Algorithms,
Addison-Wesley
[2] Wichmann, B.A., Hill, I.D., 1982, A Pseudo-Random Number Generator, NPL Report DITC 6/82,
National Physical Laboratory.
[3] L’Ecuyer, P., 1988, Efficient and Portable Combined Random Number Generators, pp.742-749, 774,
Communications of the ACM Volume 31, Number 6.
[4] Schneier, B., 1996, Applied Cryptography, John Wiley & Sons.
[5] Maurer, U.M., 1992, A Universal Statistical Test for Random Bit Generators, pp.89-105, Journal of
Cryptology, Vol.5, No. 2.
[6] Banks, J., Carson 2nd, J., Nelson, B., 1996, Discrete-Event System Simulation, Prentice-Hall.
[7] Fishman, G., 1973, Concepts and Methods in Discrete Event Digital Simulation, John Wiley & Sons.
[8] Ritter, T., Ciphers by Ritter, http://www.io.com/~ritter/
[9] DIEHARD, http://stat.fsu.edu/~geo/diehard.html
[10] Haahr, M., http://www.random.org/
[11] Marsaglia, G., 1984, A current view of Random Number Generators, Computer Science and
Statistics: The Proceedings of the 16th Symposium on the Interface, Atlanta, Elsevier Press.
[12] M. Matsumoto and T. Nishimura, 1998, Mersenne Twister: A 623-dimensionally equidistributed
uniform pseudorandom number generator, ACM Transactions on Modeling and Computer Simulation,
Vol. 8, No. 1, pp.3-30.
[13] Sullivan, J., 1998, Numerical Analysis & Associated Fields Resource Guide,
http://net.indra.com/~sullivan/q10.html
Appendix A – Evaluation
A.1 Project Overview
Initial work was on structuring the API in such a way that it was flexible enough to cope with most
generators and testers although still specific enough to allow generators to be interchanged easily in a
program. Once a rough outline had been produced the “reference” generators and display and speed
tester were written as a “proof of concept” and the API refined as a result of this. Constructing the API
and resolving issues surrounding the basic framework took around a quater of the time, primarily
because constructing dynamic-link libraries and particularly using the dlopen() call causes problems not
encountered in normal programming. Debugging also proved a problem – although most generators
can be linked statically combination generators such as L’Ecuyer rely on dlopen() to work which makes
using standard debuggers such as gdb tricky.
Only around ten percent of the time was spent implementing generators as this proved a relatively easy
task given the wide availability of algorithms to perform the most common generation functions. Writing
the testers and running tests took over half the time taken. This was due primarily to the difficulties in
implementing testing libraries that have been discussed at length previously. The remaining time was
spent writing the report.
A.2 The Approach
There is little to be said about the approach that has not already been covered in the body of the
report. No major assumptions were required for implementation and the reasoning behind the structure
of the project and choice of language has already been covered in section 2.1.
A.3 Possible Future Work In The Area
This project could be extended quite considerably to encompass far more generators and testers than
are currently implemented. Trying to implement even a significant portion of the available generators
would be quite a significant work however as there are a large number of generators and an almost
infinite number of possible parameters for those generators.
Appendix B – Tables of results
B.1 Empirical test results
| Chi-sq | KS | Gap | Poker | Runs | Mean | Maurer | ||
| Linux | 0.362208 | 0.510559 0.675486 | 0.712583 0.000526 | 0.478271 0.428924 | 0.359596
0.874975 | 0.247679 0.393694 | 0.184395 0.458329 | 7.184869 |
| File | 1.000000 | 0.738718 0.948190 | 0.935290 0.001834 | 0.011070 0.011181 |
0.497735 0.132207 | 0.130925 0.047258 | 0.174363 0.272003 | 7.184507 |
| Zero | 1.000000 | 1.000000 0.000000 | 0.000000 1.000000 | 1.000000 1.000000 |
1.000000 1.000000 | 0.000000 0.000000 | 0.000000 0.000000 | 0.000001 |
| Rand 1 | 0.715177 | 0.820229 0.018466 | 0.480549 0.096585 | 0.414513 0.399850 | 0.138942 0.473569 | 0.252494 0.710310 | 0.138706 0.399274 |
7.184058 |
| Rand 2 | 1.000000 | 0.753250 0.382823 | 0.071074 0.162250 | 0.131359
0.109035 | 0.228733 0.801380 | 0.473434 0.175626 | 0.588748 0.818538 |
7.185135 |
| Von N. | 1.000000 | 1.000000 1.000000 | 0.000000 1.000000 | 0.996104
0.972135 | 1.000000 1.000000 | 0.859635 0.757239 | 0.931238 0.753966 |
7.196248 |
| LCG 1 | 1.000000 | 0.247861 0.804789 | 0.000000 1.000000 | 0.154877
0.061890 | 0.230819 0.159677 | 0.215360 0.324168 | 0.477696 0.260543 |
7.198858 |
| LCG 2 | 0.000000 | 0.033461 0.952883 | 0.000000 1.000000 | 0.032041
0.083639 | 0.014468 0.013934 | 0.885685 0.897066 | 0.914775 0.975280 |
7.233509 |
| ACG | 0.191041 | 0.771454 0.167969 | 0.376785 0.270558 | 0.022058
0.093272 | 0.292254 0.498318 | 0.180289 0.403473 | 0.231975 0.144920 |
7.183310 |
| ICG | 1.000000 | 1.000000 1.000000 | 0.999999 0.998766 | 0.999999
0.998766 | 1.000000 1.000000 | 0.928292 0.739950 | 0.999918 1.000000 |
7.180711 |
| L’Ecuyer | 1.000000 | 1.000000 1.000000 | 0.000000 1.000000 | 0.852401
0.554670 | 1.000000 1.000000 | 0.118549 0.250390 | 0.180989 0.411692 |
7.169784 |
| Alg. M | 1.000000 | 0.033915 0.811274 | 0.000000 1.000000 | 0.149044
0.061221 | 0.010887 0.498318 | 0.295884 0.919160 | 0.324374 0.510433 |
7.196667 |
| LFSR | 0.505779 | 0.657751 0.104576 | 0.000000 1.000000 | 0.033919
0.012633 | 0.160175 0.184342 | 0.138039 0.101322 | 0.291267 0.243762 |
7.184588 |
| FCSR | 0.084193 | 0.517227 0.511065 | 0.000000 1.000000 | 0.033539
0.056973 | 0.821765 0.818449 | 0.580329 0.835615 | 0.836863 0.335689 |
7.183938 |
| Mer.Tw. | 0.806905 | 0.642702 0.057305 | 0.532591 0.116994 | 0.097397
0.119505 | 0.424862 0.960693 | 0.717156 0.727823 | 0.245693 0.405926 |
7.183670 |
Red: Failure at the 1% level
Yellow: Failure at the 5% level Green: PassB.2 Speed test results
| Intel PPro200 | Sun Ultra 5/10
(Sun4u 299MHz) | Alpha 21164 533MHz | |
| file | 1851 | 2251 | |
| zero | 1770 | 2483 | 6736 |
| Mersenne | 1470 | 2125 | |
| Von Neumann | 1418 | 727 | 5120 |
| ACG | 1190 | 1309 | 4808 |
| Rand | 1190 | 1636 | |
| LCG | 1058 | 920 | 4367 |
| L’Ecuyer | 794 | 336 | 1295 |
| Algorithm M | 374 | 304 | 1694 |
| LFSR | 160 | 176 | |
| FCSR | 141 | 171 | |
| ICG | 54 | ||
| Linux | 34 |
All values are thousands of 16-bit values per second.