A report submitted in partial fulfilment of the requirements for the degree of Bachelor of Science by Z. O’Connell (950786535)
Department of Information Systems and Computing, Brunel University
January 1999
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 report reviews the sources required for implementing such a program and presents some background on the more fundimental aspects of random number generation and testing.
This project studies the speed and efficiency of pseudo-random number generators and tests used to eliminate “flawed” generators. Methods for converting “flat” integer distributions into standard real number distributions are also briefly examined. The ultimate aim of the project is to produce a set of random numbers generators of various types and a battery of tests which can be used to “weed out” any flawed generator, hopefully arriving at a single generator or set of generators for various applications that are both fast and as random as possible.
Cryptanalysis of random number generators in general is too wide a field to be able to study in detail in this project, so this project will concentrate on the algorithmic and simulation modeling applications of random numbers. Despite this, much of the source material comes from cryptography primarily because most of the recent work on PRNGs has been in that area.
The generators we study produce, in general, equally distributed output between zero and a known value. Although mathematical functions exist to convert this output into other distributions using real numbers, such techniques are also not examined here.
The aim of this report is to briefly summarise the sources of information required to produce a suite of random numbers. It is not intended that there should be enough information contained here to do any theoretical analysis of generators or tests or to implement the more complicated tests as such a report would be several times the size of this one.
Generators discussed here are those directly relating to the main area of study – uses of pseudo-random numbers in simulation modeling and probabilistic algorithms. It is intended to analyse more generators than those presented here in the second part of the project in order to compare these generators to near-perfect or “secure” (Unpredictable) but slower cryptograpic and hardware generators, however such generators do not need to be implemented as source code or generator output is freely available.
Knuth [1] offers the only detailed published non-cryptographic discussion on what a random number actually is, although much of the discussion is now out of date. The discussion is, in any case, mathematical and doesn’t help us understand what a random number is at a fairly basic level. Most notably, his discussion makes no reference to the use of random numbers for encryption, which is now one the main area of research connected to random numbers.
A good definition [22] of a “True” random number generator is that is should be “Unbiased, unpredictable and unreproducable”. As we are concentrating on probabilistic algorithms and simulation modeling applications, we are primarily concerned with the unbiased aspects of random number streams. A pseudo-random number generator will always be predictable and reproducable given knowledge of the algorithm and initial seed value used. In both fields, we are not worried about the predictability of an unbiased algorithm, and unreproducability can be a very undesirable trait if a particular run needs to be repeated.
A computer, being a purely mathematical machine cannot generate truly random number sequences. Instead, it has to rely on mathematical ‘tricks’ to produce a sequence that appears to be random. There are electronic devices, such as ERNIE and Rairfield et al’s integrated circuit [3] based on “…the frequency instability of a free running oscillator”. These systems can generate random number sequences which are dependent on entropy in the environment and as they are not practically predictable, are suitable for use in cryptographic systems or where predictable numbers are undesirable, such as lotteries. They are not studied here however as we are interested primarily in generators which are implementatable in software. Cryptographic generators are also not looked at as they sacrifice much of their speed in the interests of security. Similarly, cryptographic hashes of semi-random sources, such as the SHA hash of entropy gained from hardware events used by Linux (See [11], also
/usr/src/linux/drivers/char/random.c on any Linux machine) are also not discussed as they require OS-level access to the hardware to generate the initial entropy and as such can not be implemented portably.
It is very easy for anyone to propose a random number generator without properly understanding what they are doing, as Knuth [1] mentions, (“…random numbers should not be generated with a method chosen at random. Some theory is required.”) so any generator which doesn’t at least have an analysis using the standard tests isn’t discussed here. For our non-cryptographic purposes, we require generators that are far quicker than these cryptographic ones. There are many combination generators and “shuffling” tecniques which are also mostly not discussed, such as the McGill “Super-Duper” generator mentioned in [21], as there are so many that it would take a long time to study and discuss the relative merits of each. These methods are in general much slower than a single generator and designed to “defeat” cryptographic attacks rather than increase randomness.
One of the most important aspects of a generator is it’s peroid and it’s tendancy to “degenerate” to sequences such as all zeros. The period of a generator is how long a sequence it generates without repeating. This is mainly a problem with generators, such as the Von Neuman middle-squared method, that use the output of one iteration as the “seed” for the next one and don’t maintain any hidden “state”. With such a system, a particular seed will always produce the same output sequence, and if that value reoccurs in the output sequence the generator repeats. Evaluating the period of a generator with internal state of more than 32 bits algorithmically requires a prohibitive amount of memory (512Mb, assuming states that have occurred are stored in an array of 232 single-bit boolean values) and knowledge of the internals of the generator, so it is difficult to do. Fortunatly, the serial test picks up on this well and other tests tend to produce poorer results for generators that have a low period or degenerate quickly so we do not need to test for these attributes directly.
The earliest proposed generator, by Von Neuman, is simple and relatively quick but no longer considered suitable for any application because of it’s relatively low period and tendancy to degenerate rapidly. The basis of the generator is to take a seed value, square it and take as many digits from the middle of the number as required. Knuth [1] describes this method in details and points out that in most (not all) cases that a Von Neumann generator will loop after a relatively small number of iterations. Although he gives a method for stopping a Von Neumann generator from looping and gives cases with a very long period, there are generators which are almost as fast which are for more random.
Paul & Balmer [15] discuss a modified form of Von Neumann where rather than squaring a number, the product of two numbers is used and the middle digits are taken but this “mid-product” method is also flawed and biased in the same way as Von Neumann, although with longer peroid and less tendancy to degenerate.
Congruential generators, those which in some way use the modulus function, are by far the most common generators in use and are discussed in every book on the topic. There are several types of congruential generator available, however.
Also called a “mixed congruential generator”, several texts describe linear congruential methods in detail, although they were originally proposed by Lehmer in 1948, although not published until 1951. [17] Knuth (As usual) presents the best basic discussion on this method, which is based on the formula f(x+1)=(a
f(x)+c)modm, where a, c and m are constants chosen to give good speed and period. For this generator, r=m, but as Knuth shows it is a mistake to choose m
to be a “convenient” value such as 65536. Knuth [1] and Banks et al. [13] go into quite some detail over the choice of a, c and m which are shown to be very important to choose carefully to get a good generator. In practice these values are usually fixed in a particular implementation as the potential to produce a very poor generator by accidently choosing the wrong vaules is very high. When analysing linear congruential generators each set of choices for values is generally considered as a separate generator as properties such as period and even the overall randomness of the output vary wildly based on them. Schneier [8] gives a table of “good” values which pass the spectral test, a partly-theoretical test used to analyse the choice of values for linear congruential generators. Because of their simplicity, linear congruential generators with good choices of values are still considered good sources of random numbers for non-cryptographic applications. The period of a well-chosen LCG on a 32-bit computer is only 2D109
[13] however, so other generators are required for many uses.
Lehmer, when he originally proposed a congruential generator, actually gave a linear congruential generator but with c=0. This “multiplictive congruential generator” is not often used because computationally c@0 is trivial and greatly increases the randomness of the generator. [1] It is used as the basis for other combined generators however, most notably Wichmann & Hill [5], although they don’t say why they chose multiplicative over linear congruential generators.
Additive congruential generators, sometimes called “Fibonacci” generators, of the form f(x)=(f(x-1)+f(x–k))mod m are mentioned briefly by Kleijnen and Groenendaal [17] although are no longer considered good generators in most cases. (The name Fibonacci is due to the similarity of the generator to the fibonacci sequence with k=2 rather than any link with the mathematician of the same name.) The origins of this form of generator are unclear but Knuth mentions it as having been proposed in 1950’s with k=2 and then analysed with k@2
by Green, Smith and Klem in 1959. m=235 and k=97 is mentioned in [17] as being a good version of this generator. If these values give a good period and pass the standard randomness tests then this is a very good generator as it is faster then even Von Neumann – it is a single addition operation and a modulus that, on a 64-bit computer, can be implemented in a single AND instruction.
Schneier [8] and Knuth [1] mention, unfortunately without references for their source, polynomial congruential generators of the form f(x+1)=(a f(x)n+b
f(x)n-1…+c)modm. Without knowing where these come from it is impossible to make a guess as to good values for the generator. As with all congruential generators, theory is required to select values to produce a good generator. Although the spectral test (See section 3.4) could probably be adapted to do this, such work is beyond the scope of this project.
Wichmann & Hill [5] produced an combined generator based on three multiplictive congruential sources with different periods. (There is no reason not to use more source generators, but Weichman &
Hill state that they found three adequate to produce good randomness) Although their original paper is very short (Just over 3 pages with spacing similar to this report) and was initially only an attempt to produce a fast, portable generator for Pascal they managed to find a new form of generator that produces good random numbers. The main attraction of this generator is it’s speed as it is designed with microcomputers in mind. (Specifically, the PDP-11) For a congruential generator, it also has a very large period (Wichmann & Hill claim 2.78D1013) which should be sufficient for most applications. Unusually, this generator produces real numbers between 0 and 1 rather than integers. The production of real numbers appears too closely tied in with the theory behind the generator to be removed, and this fact could slow the generator down under certain circumstances as discussed in the next section. Unfortunately, Wichmann & Hill don’t say what the resolution of the output is (I.e. How many decimal places can be regarded as random) which we will need to know to do accurate testing, so some theoretical analysis of this generator is probably needed. A serial test conducted on a generator with an assumption of more resolution than is actually present will probably fail.
L’Ecuyer [7] produced what is now considered the best method of combining linear congruential generators, and is the only “non-cryptographic” generator Schneier [8] bothers giving code for and the only combined generator discussed by Banks et al. [13] L’Ecuyer’s generator has a far more detailed theoretical base than Wichmann & Hill present. Although more complex than W&H’s combined generator, it is still easy to implement and relatively fast compared to some other generators. Schneider claims a period for his implementation of “somewhere in the neighborhood of 1018”. This brings us onto the interesting question of speed versus portability. Although L’Ecuyers period is much greater than W&Hs period for most applications W&H is adequate and if it passes randomness tests adequately there seems no reason to use L’Ecuyer if it is slower. L’Ecuyer is more complicated however, so likely to be slower but W&H relys on floating-point calculations, the speed of which can vary wildly between different processor types. Therefor, when considering the speed of generators during implementation they will need to be tested on different platforms to gauge the difference in performance caused by such details.
Although ICGs, which are essentially LCGs that use the multiplicative inverse of f(x-1) rather than the raw value, are usually ignored as they fail the Diehard tests [19], Marsaglias implementation in the diehard suite did not use the best values, [26] which highlights the importance of choosing the correct values for a generator and the fact that a specific implementation should be tested before use and not blindly relied on because it implements a “known good” generator. There appears to have been no “fixed” version of this generator tested using the Marsaglia/Diehard tests so it is not known if this generator performs well or not.
The other major type of generator is the feedback shift register, sometimes called Tausworthe generators. The origin of this generator is unclear – some sources say it was proposed by Selmer in 1965, others by Tausworthe in the same year. The generator works by taking a single bit from the right of a n-bit
register, shifting the register right by one bit then calculating the left-most bit based on the contents of the whole register. The main attraction of this style of generator lies with the cryptographic security of certain versions of FSRs and in it’s ease of implementation in hardware. However, they are also very easy to implement in software and fast so they are also valuable for other applications. As with congruential generators, there is more than one version of this generator.
The fastest form of FSR is the linear feedback shift register, which uses two or more bits from the register XORed together to give the new bit. Schneier [8] gives a detailed discussion of this method, including details on how to choose which bits to XOR for maximum effect. Schneier claims that a LFSR is non-random if large numbers are generated although doesn’t give a convincing argument as to why this should be and Kleijnen and Groenendaal [11] don’t consider the LFSR flawed compared to congruential generators. There are certain problems with this style of generator, most notably that the shift register must be large compared to the size of output word to approximate random output. It is also relatively easy for the output to degenerate into all-zeros or other repeating patterns in a similar manner to Von Neumann generators.
Feedback with carry shift register generators are relatively new and were devised for cryptographic uses so there is no study on their practical use in non-cryptographic applications. The basic feedback function is the sum of all the “tapped” bits plus the carry register – that value mod 2 becomes the new bit, and div 2 becomes the new carry register. [8] Like congruential generators with differing values for a, c and m, FCSRs need to have any initial value tested before use to check that they have reasonable period and don’t degenerate. Schneier gives a table of “tap sequences” (Which bits in the FSR need to be used) to give maximum periods – the maximum periods are typically in the range 2n where n
is the size of the feedback shift register. This gives a maximum period of 3.4D1038 for a 128-bit generator, which is certainly acceptable for most applications.
Mersenne Twisters are a form of generator proposed by Matsumoto and Nishimura in [24] that, they claim, have the rather amazing period 219937-1 and pass “several stringent statistical tests, including diehard”. They are based on “Twisted” Feedback-shift-register generators that use Mersenne Primes to produce longer periods (Most generators, particularly congruential and combination generators use normal primes or relatively-prime numbers to achieve a longer period) This generator is very new (Less that one year at the time of writing) and although apparently well received on the Internet, not discussed in other works as yet. The algorithm on initial examination appears to be quite slow but actually lends itself quite well to computer implementations and general Internet research (Comments made on newsgroups) suggest that it probably compares favorably with other non-cryptographic generators.
The above generators are by no means the only FSR generators available. However, they are the only two fast enough to be considered usable for general applications. For example, the FSR-based Blum, Blum & Shub generator is often used in cryptography and considered very good but is far too slow for most uses. [18, NEWS2/94061801.HTM]
Algorithm M is a method originally proposed by MacLaren and Marsaglia for combining two random sequences in a computing-friendly (I.e. fast) way to produce a “considerably more random” output. [1] It is named after it’s discussion in Knuth where it is referred to as just “Algorithm M”. Unlike combination generators discussed earlier this generator is designed to work with any sequence and not just congruential generators. Knuth mentions that if the two source generators periods are relatively prime with respect to one another that the period of the product of both generators, and this is true in the case of most combination generators. Knuth doesn’t actually offer a proof of this, it is left as a (relatively easy) exercise for the reader.
The Lagged-Fibonacci generator is dealt with in great detail by Marsaglia, [21] and as the name implies is closely related to the additive congruential generator discussed above. The generator has the formula f(x)=f(x–r)¿f(x-s) where r and s
are the “lag” constants for the generator and ¿ is a mathematical operation. The additive congruential generator follows this formula where r=1, s=k and ¿ is addition followed by mod m. Lagged-Fibonacci generators are typically dealt with separately from congruential generators as the theory behind choosing the correct values is radically different. Marsaglia goes on to show that Lagged-fibonacci generators using multiplication are the only non-combination generator he studies that passes all the “diehard”
[19] tests. However, it is not clear whether the comments in [26] were made before or after this comment – see section 2.5.2.
Marsaglia also gives two combination generators in [21], COMBO and NCOMBO, based on two specific cases of the Lagged-Fibonacci combined using simple subtraction. Marsaglia shows that the result is indeed more random as long as neither generator degenerates, based on work done by Brown and Solomon and Marshall and Olkin, however the proof is rather complicated. The theory is applicable to generators other than Lagged-Fibonacci, and Marsaglia also analyses the McGill “Super-duper” MCR/LFSR combination generator in the same paper.
A cross between the lagged fibonacci generator and the Feedback-with-Carry-Shift-Register generators are the “with-carry”
generators, and although usually considered separately from Lagged-Fibonacci generators are essentially of the same class. Add-with-carry generators are basic additive congruential generators that add in the concept of carry as used by FCSR generators. Subtract-with-borrow and multiply-with-carry generators follow along the same lines using subtraction and multiplication instead of addition. Add-with-carry and subtract-with-borrow are not particularly powerful generators, however multiply-with-carry has been shown to perform well in tests and have a long period as well as being very fast. These generators have been studied extensively by Marsaglia in [18], [19] and [25]. Knechtel writes: [26] “The best of [the multiply with carry generators] seem to pass all the Diehard tests (See section 3.3), even tests that many common pseudorandom number generators fail.” Little independent study of these generators exist yet, however Marsaglia himself is bullish: “I predict it will be the system generator for many future computers”, and claims a period of 2 f(x-1)+c mod 232, given if a
is chosen “from a large set of easily found integers”.
Unfortunately, the comments above are not dated and the diehard suite [19] has evolved over time; the tests the latest version employs are no longer the same as the ones discussed in [21]. As mentioned in [25], Marsaglia didn’t examine this generator in paper [21] which may mean he was unaware of it at the time.
sequences
The descriptions of tests given here are necessarily brief – most of them would take at least two full pages each to describe in detail. The information here is meant to be sufficient to understand the comments and discussion on the generator and to give the reader some understanding of the analysis routines that will be written as the implementation part of this project. When applying these tests, it is important to remember that it is almost always possible to construct a non-random algorithm which a specific test will not pick up on as non-random – such an approach is not a proof that the test does not work.
Formulae for the statistical tests and values of S(x) (Needed for statistical analysis of the output results) for tests are given, as these are often wildly different between texts, particularly in the case of Kolmogorov-Smirnov, so “standardised”
versions are necessary for implementation. Where this isn’t possible, due to the complexity of the equations or a requirement for lengthy lookup tables, a specific work with good examples is cited. Most of the tests here are “standard” tests used and discussed by almost every basic textbook on the subject, so specific citation is only given to unique points of note.
Knuth [1] points out that there is no such thing as a “Random Number”, as you cannot say whether a single number on it’s own is random or not. For example, is the number 3 random or not? We cannot answer this question. It is assumed here that all the generators produce integer values from 0 to r, as this is true in all but one case for the generators we have looked at. Following on from this, is the sequence 3, 3, 3, 3 random? Possibly, as it is just as likely as any other sequence of four numbers. When testing random numbers, we test probabilities – a generator that produces many threes and few other numbers over a long period of time is highly unlikely to be unbiased and, in statistical terms, we “reject the hypothesis” that it is unbiased. As Paul and Balmer [15] note, “You can try to be too perfect. Genuine random sequences contain subsequences that are highly systematic”.
There are several tests not considered here. There has been much work published on the spectral test (Also known as Fourier analysis) in many different forms however it has a theoretical base closely related to choosing good values for linear congruential generators. Theoretical tests have also not been discussed as they require human (rather than algorithmic) analysis on the structure of the generator. It is somewhat surprising to see that almost all the tests have their origins in work done by Kendall and Babington-Smith in the 1940s and that Knuth’s [1] work in 1969 is still probably the most valuable text on empirical testing – Marsaglia actually refers to the standard tests as “Knuth’s” (See quote in section 3.3) rather than Kendall and Babington-Smith’s. I have limited statistical tests to just the three most common which measure different properties of the generator as any common statistical test could be applied.
In the interests of readability, the following notation is used throughout, regardless of the notation used in the source documents as almost every book uses different notation.
n – Length of random sequence being analysed. (I.e. Number of values being analysed) “Total number of independent observations” in statistical terminology.
r – Number (Mnemonic: Range) of possible outputs. (For example, r=65536 if possible integer outputs are in the range 0-65535 inclusive)
Or – Observed frequency of value r.
Er – Expected frequency of value r.
F(x) – PRNG as a function, 0Tx<n
S(x) – C.d.f of expected output
p – Probability of a given distribution output, calculated using S(x)
The Chi-squared (æ2) test verifies that a random sequence is distributed as we would expect. In all the generators discussed here, the output is initially evenly distributed real numbers between two values. To do this, a count of the number of occurrences of each value s is taken, referred to as Os. Using the equationwe can measure the “goodness of fit” of a particular generator. In all cases studied here, Es=n/r as the generators raw output are all evenly distributed between two numbers. Once we have the æ2
value, the value of p can be calculated to find out how likely such a value is and therefor if the value is “suspect” or not. Is it possible to approximate appropriate values of p for æ2, (p cannot be calculated exactly) however the formula to do this is very complicated and most mathematical libraries include code to do this as standard. If only a “Fail” or “Pass” indication is required, it is faster to use a table of critical values, such as those given in most statistical texts, Most books on the subject assume this is what is required, however for our purposes we will need the actual values to implement Knuths suggestion of running the Kolmogorov-Smirnov test on the outputs of many æ2
tests, as discussed below.
Knuth points out that applying this test to a very large sample of output has it’s problems however, as although it picks up general long-term bias in the output, it won’t always detect what Knuth terms “Locally non-random behavior”, for example often-repeated sequences of numbers. These could be picked up if they are frequent enough and biased heavily towards one set of numbers, but they could easily be balanced out long-term by other locally non-random behavior. Although we are constrained by the general requirement that EsU5 for æ2, [1] it is best to keep n as small as possible and repeat the test several times. This applies to all the other tests discussed here as well, although some tests such as the serial test produce a small amount of output for a large r so there is only likely to be enough data in even a large sample for a single æ2
test.
When applying this test many times on one generator, we need a method of measuring the output more formal than simply the standard statistical “reject the hypothesis” method, as with a large enough number of independent tests this is likely to occur at least once. This also checks that the distribution of p is reasonable – i.e. the generator is “globally random”. To do this Knuth proposes applying the Kolmogorov-Smirnov test to the values of p. (See section 3.1.2) The æ2 test is inappropriate for this task as it is not well suited to handling relatively small n with infinitely variable real, as opposed to a fixed number of integer, values. Other authors unfortunately assume a single test and don’t discuss this.
It is important to note that æ2 requires independent tests. For example, if applying æ2 to the serial test in section 3.3, if c=2 and a=2, x should be sampled as 0, 1, 4, 5, 8, 9… to avoid using any values twice. However, Marsaglia [21] has produced modified versions of many of the standard empirical tests which are suitable for running with “overlapping” values.
The Kolomogorov-Smirnov (KS) test is a measure of the maximum difference between the expected and actual distribution. It is more suited to evaluating real numbers rather than discrete integer values, however it can detect non-randomness that æ2 fails to, so it is a useful test. This gives a formula for KS of D=n½maxsF(x)-S(x)s,
which like æ2 produces a values which can be calculated to give p to see if the value is too high or low. Fortunately, p can be approximated for large n using the formula S(x)=1-e(-2x2). Knuth suggests n=1,000, although this only gives 2 decimal places of accuracy. With modern computing hardware, n=100,000 gives a better compromise between speed and accuracy. (3 d.p.) This does mean that a large number of KS/æ2
tests will need to be carried out for each generator unless a table of critical values is used. (The same formula is used for applying KS to KS results) There are many versions of the KS test, so care should be taken to use the correct tables/formula. Knuths formulae from [1] are used here primarily because his descriptions on KS are better and he presents the formula for S(x), although the form of equations he uses are not the most common-version.
Algorithmically, KS is best calculated by ordering the data from X1 to Xn
(Ascending order if S(x) increases as x increases and vise-versa) and finding max(max(j/n-S(Xj), max(S(Xj)-(j-1)/n)), 1TjTn. (The c.d.f. for evenly distributed random numbers from 1 to r-1 is S(x)=x/r, 0Tx<r)
The requirement to order the data and the use of floating point operations means that the test is slower than æ2, particularly for very large n. There is no reason however to use the same subdivisions of data that æ2 uses, so it is more efficient to divide the data into smaller segments then apply KS again to the results.
Sometimes referred to as the “serial correlation test” or “autocorrelation test”
when applied to random number theory, unlike æ2 and KS the correlation test (Specifically, the Pearson Product Moment Correlation Coefficient) checks the relationship between successive values – that is, it is dependent on the ordering of the output values within the test set. The previous two statistical tests are independent of ordering so won’t detect non-random sequences like 1, 2, 3… as long as the set has the expected distribution. Banks et al. [13] and Kleijnen and Groenendaal [16] give a full description of this test when applied to random number sets, and fortunately PPMCC is a standard statistical test and details of it’s calculation don’t vary between texts. The correlation test is not often applied however as it measures the same properties as the serial test discussed in section 3.2.1. (No source referenced considers both the correlation test and the serial test)
The serial tests applies the statistical frequency tests in section 3.2 to tuples of numbers, (F(x), F(x+a), F(x+2a)…F(x+ca)). This is equivalent to evaluating a generator with
r=rgeneratorc, so is unfeasible for c>2 for most generators. (Assuming an 8 bit generator, if c =4 then æ2 tests on 21 billion values would be required to satisfy EsU5.) Although even books as recently as 1993 [15] regard the serial test even with c=2 as
computationally too difficult to carry out generally, modern hardware should be capable of running tests in a reasonable amount of time.
Marsagla [21] proposes the “Overlapping M-Tuple test”, which is a variation of the basic serial test with the m in the title being the c of the serial test, using PPMCC to “modify” the output to be appropriate for æ2 tests despite not being independent values. Marsaglia analyses data as bit-streams rather than discrete numbers and takes only three bits of a number at a time for this test which makes use of a larger c
feasible.
The gap test checks the gap between numbers follows the expected distribution, which Banks et al. [13] show is S(x)=1-0.9x+1. As S(x) is non-linear, it is necessary to vary the size of the frequency counts to satisfy EsU5. For example, if n=10,000, E71=0.56, so E71+=5.1 should be used instead. Counting the frequency of each gap size is algorithmically very easy and fast compared to some other tests. Kendall and Babington-Smith’s original version only counted the gap between zero digits [5] although with modern computing it should be possible to apply this test to all possible values.
There are two ways to conduct a poker test. Knuth’s [1] method involves testing for two, three, four or five of the same number recurring in sets of five random numbers. With a large r, this is not really feasible however. (If r=65536 and n=100000 EpairY1) The more commonly discussed method, such as in Banks [13] counts the reoccurrence of the same digit within a random number. It is important to note however that if analysing in decimal a number produced by a binary generator, the first digit may not be in the range 1-10 and the expected distribution should be adjusted as appropriate. Although only mentioned in an exercise in [1] and not discussed in detail anywhere, the same test could be carried out using hexadecimal, octal or even binary digits instead of decimal.
The coupon collectors test evaluates how long a run is required to get at least one occurrence of every possible number. We cannot apply this test to all generators, as some may always degenerate or loop before they generate every possible value and also requires a very large sample set compared to other tests and may be very time-consuming on slower generators. (For one output value, at least r random numbers will have been generated) Knuth [1] discusses this test in detail but other books (Which all cite Knuth as a reference) have not mentioned it. This is probably due to the fact that the coupon collectors test is difficult to implement and, as Wichmann & Hill [5] point out, measures the same properties as the gap test.
The run test as used by Knuth checks that the length of “runs up” and “runs down” of random numbers matches the expected distribution. The formula to do this is somewhat complicated however, as successive values are not independent of each other so æ2
cannot be used. Knuth[1] gives formula, which are quite long and involve tables so are not given here, which allow the calculation of a statistic which can be subjected to æ2. Kleijnen and Groenendall [16] state “We again use a æ2 statistic to test whether the generator is acceptable. The standard æ2 test, however, does not apply because of the dependence between the successive [run lengths]” but do not give the test which is used.
Kleijnen and Groenendall also have a variation on this test of “Runs above and below the average”
which functions exactly as the name implies – checking that the distribution of runs above and below the expected mean. (0.5r in our case) This picks up generators that tend to produce long runs of numbers higher or lower than average, something most other tests are only slightly sensitive to.
Knuth [1] gives an algorithm for counting the frequency of orderings of random numbers. For example, if using sets of three random numbers (a, b, c) together this test counts the frequency of each possible combination of the three numbers when ordered, of which there are six (3!) combinations. (a<b<c, a<c<b,
b<a<c, b<c<a, c<a<b and c<b<a)
This test, along with the Maximum-of-t test, isn’t even mentioned in any other books or papers on the subject which may mean that this test is no longer considered useful. Despite this, I can find no reference that actually shows this specific test to be a poor test. As with the overlapping-permutation test discussed below, it may simply be that this test does not pick up any non-random attributes not found by other tests such as the run test and serial test.
Marsaglia’s version of this test is the overlapping-permutation test, which as the name implies is a variation of the permutation test with overlapping sets of data. Marsaglia himself doesn’t regard this test as particularly good: “[Overlapping permutation] tests…are not very stringent; most generators seem to pass them…”
The maximum-of-t test, again only discussed by Knuth [1] tests the distribution of the maximum of t random numbers is distributed as expected. This is a simple and quick test to implement although again there is a strange absence of this test from other books.
Although often referred to as a “statistical” test, Maurers test presented in [11] is not a general statistical functions like KS or æ2. It is geared more towards hardware cryptograpical uses, but it does fail more modern flawed software generators that the earlier tests don’t pick up, so it still useful in non-cryptographic software situations. Maurer himself states that although the test is designed to defeat hardware generators, a good software generator should certainly pass his test. The basis for the test is trying to detect whether a generator has detectable “memory” (That is, that later values are based in some way on earlier ones) Maurer claims his test will fail any generator that fails another test presented here and although Maurer presents no empirical or theoretical proof of this, although it is fairly likely to do this based on the nature of the test. Being a comparatively recently developed test, there are few good discussions on it’s relative merits, although it is generally regarded as a good test.
In [19] and [21], Marsaglia presents a suite of tests apparently of his own devising rather more complicated than those previously studied, which are “more difficult to pass than [Knuth’s] tests that have become standard”. Although there is little independent discussion of these tests in texts, primarily because they are significantly more difficult to analyse that other tests, they are considered worthwhile tests. Each test is discussed briefly, although the fact the formula presented by Marsaglia are very complicated and the lack of independent discussion on them means that descriptions are somewhat brief. Two of his tests, the M-Tuple test and Overlapping-permutations are modifications of the standard tests and have already been discussed in section 3.2.
Although proof of the tests is given in most cases, Marsaglia doesn’t discuss why this particular group of tests as a whole is useful, a discussion which is lacking in most books as well. As more powerful extensions of the “standard” tests they should perform well in practice and passing these tests is considered a very good indication of the suitability of a generator for non-cryptographic uses but it remains to be seen if any of the more obscure generators and particularly Maurer pick out poor generators that these “stringent”
tests fail to.
OPSO is an unusual test that tried to overcome the problems of requiring large amounts of memory and a large number of tests to do serial tests with large r and c=2.
This test actually applies a probabilistic algorithm of “parking cars” in an n-dimensional space and compares the result with one from a known-good random source. (There is no theory to solve this problem that is not probabilistic) Although suggested elsewhere, this is the only actual discussion about a specific implementation of a probabilistic problem.
The Birthday spacings test as presented in Marsaglias paper appears to be related to the standard gap test, although the description presented is somewhat confusing and incomplete. Marsaglia appears not to have published a proof or detailed description of it yet, only source code. Apparently, “…a detailed discussion of the test will appear elsewhere” although no indication is given as to when or where this might be.
Marsaglia’s description of the “ranks of binary number matricies” test is also unclear, and his test results suggest that this is not a powerful test as it does not fail a generator that is not failed by several other tests. It is, apparently, designed with simulation modeling in mind and the availability of source code in [19] may make this test implementable, even though the paper appears to give insufficient information for this.
At this stage, without any hard empirical results to refer to, it is difficult to draw any conclusions, particularly with regard the the suitability of the tests. All the tests discussed above are “accepted” by the community as valid tests so, barring implementation problems, none should spuriously fail otherwise valid generators. There is some obvious overlap in the generators however, particularly with regard to the standard “Knuth” tests and Marsaliga’s work. No suite of tests would be complete without those listed in [1] however, so they have been included nonetheless.
Most of the basic congruential and linear-feedback generators are now considered fairly poor, so the most likely “winner” (The fastest generator that passes all tests) will probably be a form of Lagged-Fibonacci-with-carry generator or one of the two combined congruential generators. Additive Congruential generators have been neglected in recent studies and although likely to fail Maurers test may just prove to be a front-runner despite their simplicity. Lagged-Mersenne Twisters are too new to say much about, although they have been reported to pass all the tests given here except perhaps Maurers.
References
[1] Knuth, D.E., 1969, The Art of Computer Programming, Volume 2 – Seminumerical Algorithms, Addison-Wesley
[2] Reif, J.H., Tygar, J.D., 1985, Efficient Parallel Pseudo-Random Number Generation, pp.433-446, Advances in Cryptology – Proceedings of CRYPTO ’85.
[3] Rairfield, R.C., Mortenson, R.L., Coulthart, K.B., 1984, An LSI Random Number Generator, pp.203-230, Advances in Cryptology – Proceedings of CRYPTO ’84.
[4] Newman, T.G., Odell, P.L., 1971, The Generation of Random Variates, Griffin.
[5] Wichmann, B.A., Hill, I.D., 1982, A Pseudo-Random Number Generator, NPL Report DITC 6/82, National Physical Laboratory.
[6] Neave, H., 1972, Random Number Package, University of Nottingham.
[7] L’Ecuyer, P., 1988, Efficient and Portable Combined Random Number Generators, pp.742-749, 774, Communications of the ACM Volume 31, Number 6.
[8] Schneier, B., 1996, Applied Cryptography, John Wiley & Sons.
[9] Kelsey, J., Schneier, B., Wagner, D., Hall, C., 1988, Cryptanalytic Attacks on Pseudorandom Number Generators, pp. 168-188, Fast Software Encryption, Fifth International Workshop Proceedings (March 1998), Springer-Verlag.
[10] Harel, D., 1992, Algorithmics, The Spirit of Computing, 2nd edition, Addison-Wesley.
[11] Maurer, U.M., 1992, A Universal Statistical Test for Random Bit Generators, pp.89-105, Journal of Cryptology, Vol.5, No. 2.
[12] Eastlake 3rd, D., Crocker, S., Schiller, J., 1994, Request for Comments 1750: Randomness Recommendations for Security, Network Working Group.
[13] Banks, J., Carson 2nd, J., Nelson, B., 1996, Discrete-Event System Simulation, Prentice-Hall.
[14] Fishman, G., 1973, Concepts and Methods in Discrete Event Digital Simulation, John Wiley & Sons.
[15] Paul, R., Balmer, D., 1993, Simulation Modelling, Chartwell Bratt.
[16] Kleijnen, J., Groenendaal, W., 1992, Simulation – A Statistical Perspective, John Wiley & Sons.
[17] Lehmer
[18] Ritter, T., Ciphers by Ritter, http://www.io.com/~ritter/
[19] DIEHARD, http://stat.fsu.edu/~geo/diehard.html
[20] Haahr, M., 1998, random.org – introduction,
http://www.random.org/essay.html
[21] 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.
[22] Author unknown, Random number generaton, RNGs and PRNGs, http://www.helsbreth.org/random/
[23] Moreau, T., 1996, A practical ‘perfect’ pseudo-random number generator, article submitted to Computers in Physics.
[24] 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.
[25] Marsaglia, G., Zaman, A., 1991, A new class of random number generators, Annals of applied probability Vol. 1, No. 3, pp.462-480.
[26] Sullivan, J., 1998, Numerical Analysis & Associated Fields Resource Guide, http://net.indra.com/~sullivan/q10.html
Much of the time taken (Well over one quarter) was spend tracking down appropriate books and papers, for which the Internet has proved an invaluable tool. Unfortunately much of the early work done by Von Neumann and Kendall & Babington-Smith is no longer available and even very large libraries such as the British Library and Library of Congress have no record of the books. The tendency for work in this field to be published purely as conference papers and in journals rather than in books also proved a hinderance. This seems partly due to the success of Knuth’s work [1] as no-one seems to have produced any widely-used text on the subject because his work is regarded as being “definitive”, despite being considerably outdated. Much confusion was also caused by the lack of standard naming for many tests and generators and wildly varying notation – it is often not possible to tell that two complex tests or generators are identical until some considerable research has been carried out.
Almost all of the time in the initial few weeks was spent narrowing down the areas covered as it was clear from a fairly early stage that certain topics, discussed below in section A.2, were not appropriate or too complex bearing in mind the ultimate implementation aim of the project.
Most of the remainder of the time was spent reading and attempting to understand some of the more complicated tests and generators and following up references given in some of the more useful works. Some of the maths involved required revising old mathematical courses or researching mathematical concepts (Such as Mersenne Primes used by the Mersenne Twister generator) new to the author. References are not given for books used for this purpose as they are generally outside the scope of this project and not useful to the reader.
Once the bulk of the topic had been understood, the actual writing of the report took relatively little time however, as is to be expected, this was hardly a linear effort and new ideas or problems were introduced with almost every writing session, entailing more research.
Many areas, most notably theoretical analysis of generators, were too complicated and would not be useful topics to study for producing a suite of programs for generating and analysing random numbers. Cryptographic areas of study were also dismissed fairly early as being too complicated. More time was initially spent looking at converting the uniformly distributed output produced by the generators here to patterns following other distributions however this is really outside the scope of the project as described in the initial project proposal and was dropped. Although useful in a few specific types of simulation modelling, in general an equally distributed integer generator is sufficient for most applications. Also, most of the work in this area is primarily mathematical and not computer-science based.
The most obvious extension of the work discussed here is theoretical analysis of many of the newer generators, particularly Mersenne Twisters. This is a topic best pursued by a mathematician rather than a computer scientist, however, as proper theoretical study is not a case of simple algorithmic work but requires at times some fairly complex mathematics.
Another approach would be an actual suite of generation and analysis tools, which is the eventual aim of the implementation phase. The only suite currently freely available seems to be Diehard [19], however the choice of tests used appears, in the currently available version, to be limited to tests devised by the author himself. However, the suite is widely referenced and does seem to be regarded as something of a “benchmark” in the field. The basic design is not particularly expandable, having been converted by and large automatically from Fortran source and as such does not lend itself well to experimentation by other researchers.
A somewhat more time-consuming and exhaustive topic would be a full-blown article or book on the subject of non-cryptographic random numbers, rather than just a literary review, including analysis of some of the more recent developments such as work by Fishman, Maurer and Marsaglia – essentially an updated version of Knuth’s work in [1]. This is still the most widely used reference in the field but only discusses congruential generators and the Kendall & Babbington-Smith tests and is sadly out of date in many areas.
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.
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
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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)
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.
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.
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.
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)
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.
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.
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.
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.
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.
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.
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.
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)
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
[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
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.