<center><H1>DieHarder: A Random Number Test Suite</H1></center>
<center><H2>Version 2.24.7</H2></center>

<center><H3>Robert G. Brown (rgb)</H3></center>
<center><H3>Dirk Eddelbuettel</H3></center>

<p>At the suggestion of Linas Vepstas on the Gnu Scientific Library
(GSL) list this GPL'd suite of random number tests will be named
"DieHarder".  Using a movie sequel pun for the name is a double tribute
to George Marsaglia, whose <a
href="http://stat.fsu.edu/~geo/diehard.html">"Diehard battery of
tests"</a> of random number generators has enjoyed years of enduring
usefulness as a test suite.</p>

<p>The DieHarder suite is more than just the diehard tests cleaned up
and given a pretty GPL'd source face in native C.  Tests from the <a
href="http://csrc.nist.gov/rng/">Statistical Test Suite (STS)</a>
developed by the National Institute for Standards and Technology (NIST)
are being incorporated, as are new tests developed by rgb.  Where
possible or appropriate, <i>all</i> tests that can be parameterized
("cranked up") to where failure, at least, is unambiguous are so
parameterized and controllable from the command line.</p>  

<p>A further design goal is to provide some indication of <i>why</i> a
generator fails a test, where such information can be extracted during
the test process and placed in usable form.  For example, the
bit-distribution tests should (eventually) be able to display the actual
histogram for the different bit ntuplets.</p>

<p>DieHarder is by design extensible.  It is intended to be the "Swiss
Army Knife of random number test suites", or if you prefer, "the last
suite you'll ever ware" for testing random numbers.</p>

<hr>

<center><h2><a href="./dieharder">DieHarder Download
Area</a></h2></center>

<p>The version numbers have the following meaning:

<ul> 

<li> First number (major).  Bumped only when major goals in the design
roadmap are reached (for example, finishing all the diehard tests).
Version 1.x.x, for example, means that ALL of diehard (and more) is now
incorporated in the program.  Version 2.x.x means that the tests
themselves have been split off into the libdieharder library, so that
they can be linked into scripting languages such as R, new UIs, or user
code.  3.x.x would be expected to indicate that the entire STS suite is
incorporated, and so on.

<li> Second number (first minor).  This number indicates the number of
tests currently supported.  When it bumps, it means new tests have been
added from e.g. STS, Knuth, Marsaglia and Tsang, rgb, or elsewhere.

<li> Third number (second minor).  This number is bumped when
significant features are added or altered.  Bug fixes bump this number,
usually after a few bumps of the release number for testing snapshots.
This number and the release are reset to 0 when the major is bumped or a
new test is added to maintain the strictly increasing numerical value on
which e.g. yum upgrades rely.

</ul>

<p> The single-tree dieharder sources (.tgz and .src.rpm) files can be
downloaded from this directory.  In addition, i386 binary rpm's built on
top of Fedora Core 6 are present. Be warned: the GSL is a build
dependency.  The current packaging builds both the library and the
dieharder UI from a single source rpm, or from running "make" in the
toplevel directory of the source tarball.  With a bit of effort (making
a private rpm building tree), "make rpm" should work for you as well in
this toplevel directory.</p>

<p> This project is under very active development.  Considerable effort
is being expended so that the suite will "run out of the box" to produce
a reasonably understandable report for any given random number generator
it supports via the "-a" flag, in addition to the ability to
considerably vary most specific tests as applied to the generator.  A
brief synopsis of command options to get you started is presented below.
In general, though, documentation (including this page, the man page,
and built-in documentation) may lag the bleeding edge snapshot by a few
days or more.</p>

<p>An rpm installation note from Court Shrock:</p>
<pre>
I was reading about your work on dieharder.  First, some info
about getting dieharder working in Gentoo:

cd ~
emerge rpm gsl
wget
http://www.phy.duke.edu/~rgb/General/dieharder/dieharder-0.6.11-1.i386.rpm
rpm -i --nodeps dieharder-0.6.11-1.i386.rpm
</pre>

<p>Rebuilding from tarball source should always work as well, and if you
are planning to play a lot with the tool may be a desireable way to
proceed as there are some documentation goodies in the ./doc
subdirectory and the ./manual subdirectory of the source tarball (such
as the original diehard test descriptions and the STS white paper).

<p>George Marsaglia retired from FSU in 1996.  For a brief time diehard
appeared to have finally disappeared from FSU webspace, but what had
really happened is google's favorite path to it had disappeared when his
personal home directory was removed.  Diehard is still there, at the URL
<a
href="http://www.stat.fsu.edu/pub/diehard">http://www.stat.fsu.edu/pub/diehard!
as well as at a Hong Kong website.  The source code of diehard itself is
(of course) Copyright George Marsaglia but Marsaglia did not incorporate
an explicit <i>license</i> into his code which muddles the issue of how
and when it can be distributed, freely or otherwise.  Existing diehard
sources are <i>not directly incorporated into dieharder in source
form</i> for that reason, to keep authorship and GPL licensing issues
clear.</p>

<p>Note that the same is not true about data.  Several of the diehard
tests require that one use precomputed numbers as e.g. target mean,
sigma for some test statistic.  Obviously in these cases we use the same
numbers as diehard so we get the same, or comparable, results.  These
numbers were all developed with support from Federal grants and have all
been published in the literature, though, and should therefore be in the
public domain as far as reuse in a program is concerned.</p>

<p>Note also that most of the diehard tests are <i>modified</i> in
dieharder, usually in a way that should improve them.  There are three
improvements that were basically always made if possible.
<ul>
 <li> The number of test sample p-value that contribute to the final
Kolmogorov-Smirnov test for the uniformity of the distribution of
p-values of the test statistic is a variable with default 100, which is
<i>much</i> larger than most diehard default values.  This change alone
causes many generators that are asserted to "pass diehard" to in fact
fail -- any given test run generates a p-value that is acceptable, but
the <i>distribution</i> of p-values is not uniform.
 <li> The number of actual samples <i>within</i> a test that contribute
to the single-run test statistic was made a variable when possible.
This was generally possible when the target was an easily computable
function of the number of samples, but a number of the tests have
pre-computed targets for specific numbers of samples and that number
cannot be varied because no general function is known relating the
target value to the number of samples.
 <li> Many of diehard's tests investigated overlapping bit sequences as
being "independent identically distributed (iid) samples.  This was
generally done because it used file-based input of random numbers and
the size of files that could reasonably be generated and tested by in
the mid-90's contained on the order of a million random deviates.  The
restriction of testing to small, overlapping samples is neither
necessary nor desireable in modern testing -- numerical simulation can
easily consume ten to the eighteenth or more uniform deviates and the
integration of the test with the built-in generators in the GSL permits
"most" generators to be tested with essentially no limits on the number
that can be generated for testing purposes.  Indeed, some tests are
likely to reveal the short period or limited number of returns by some
generators <i>because</i> they can consume far more numbers than are
available within the period, which was not so easy with diehard.
dieharder therefore permits overlapping sequences to be a
<i>non</i>-default option selected by the user wherever possible.
</ul>

<p>In a few cases other variations are possible for specific tests.
This should be noted in the built-in test documentation for that test
where appropriate.</p>

<p>Aside from these major differences, note that the algorithms were
independently written more or less from the test descriptions alone
(sometimes illuminated by a look at the code implementations, but only
to clear up just what was meant by the description).  They may well do
things in a different (but equally valid) order or using different (but
ultimately equivalent) algorithms altogether and hence produce slightly
different (but equally valid) results even when run on the <i>same data
with the same basic parameters</i>.  Then, there may be bugs in the
code, which might have the same general effect.  Finally, it is always
possible that <i>diehard</i> implementations have bugs and can be in
error.  Your Mileage May Vary.  Be Warned.</p>

<hr>

<center><h2>About DieHarder</h2></center>

<p>The primary point of DieHarder (like Diehard before it) is to make it
easy to time and test (pseudo)random number generators, both software
and hardware, for a variety of purposes in research and cryptography.
The tool is built entirely on top of the GSL's random number generator
interface and uses a variety of other GSL tools (e.g.  sort, erfc,
incomplete gamma, distribution generators) in its operation.  Five
examples are provided of wrapping a random number generator (including
both file I/O and the entropy-based /dev/random and /dev/urandom
available on many linux systems) and inserting it so that it is can be
called via the GSL interface. It is <i>strongly suggested</i> that any
software random number generator to be tested by provided with such an
GSL-compatible interface.</p>

<p>A file interface (still consistent with the GSL to the extent
possible) has been added that allows random numbers in either binary
unsigned integer or a variety of ascii encoded formats to be read in
from a file.  This permits dieharder to be used with "any" generator
(directly wrappable or not) that can generate a table of random numbers,
but this will place severe limits on some of the tests, which can
require very large numbers of random numbers.  For this reason software
generators should be implemented directly if at all possible and not via
the file interface.</p>

<p>In this respect, DieHarder differs significantly from Diehard, which
used file based sources of random numbers exclusively and would "work"
with only a few million random numbers in such a file.  Modern random
number generators in a typical simulation application can easily need to
generate 10^18 or more random numbers, generated from hundreds,
thousands, millions of different seeds, over months to years of
accumlated run time and are therefore sensitive to weaknesses that might
not be revealed by such short sequences even with excellent and
sensitive tests.</p>

<p>This was, in part, the motivation for the development for the
Statistical Test Suite by NIST, which focusses more on cryptographical
strength (although the general testing methodology is much the
same).</p>

<p>The development of DieHarder was motivated by the following, in
rough order of importance:<p>

<ul>

<li> To provide a <b>readily available, rpm-installable toolset</b> so
that "consumers" of random numbers (who typically use <i>large</i>
numbers of random numbers in e.g. simulation or other research) can test
the generator(s) they are using to verify their quality or lack thereof.

<li> To provide a very <b>simple user interface</b> for that toolset for
random number consumers.  A GUI is on the list of things to do, although
it adds little to the practical utility of the tool.

<li> To provide lots of <b>lots of knobs and dials</b> and low level
control for statistical researchers that want to study particular
generators with particular tests in more detail.

<li> To have the entire test code and documentation be fully <b>Gnu
Public Licensed</b> and hence openly available for adaptation, testing,
comment, and modification so that the testing suite itself becomes
reliable and can be easily extended.

<li> To provide a fairly <b>simple API</b> for adding new tests with a
common set of low-level testing tools and a <b>common test structure</b>
that leads (one hopes) to an <i>unambiguous</i> decision to accept or
reject any given random number generator on the basis of any given test
for a suitable choice of controllable test parameters.

<li> To allow all researchers to be able to directly test, in
particular, the <b>random number generators interfaced with the GSL</b>.
This is a deliberate design decision justified by the extremely large
and growing number of random number generators prebuilt into the GSL and
the ease of adding new ones (either contributing them to the project or
for the sole purpose of local testing).

<li> To allow researchers that use e.g. <i>distributions</i> directly
generated by GSL random distribution generation routines (which can in
principle fail two ways, due to the failure of the underlying random
number generator or due to a failure of the generating algorithm) to be
able to directly validate their particular generator/distribution
combination, where possible.

</ul>

<p>Note well that the primary objections I have towards diehard and STS
are not that they are or are not adequate, accurate and complete; it is
that the code itself is not properly packaged for reuse, testing, and
extension.  Diehard is remarkably poorly documented (with one small
paragraph of text describing each test, even very complex ones, and with
no accompanying description of how certain important data used in the
program were actually computed). STS, in contrast, is really nothing
<i>but</i> its description in documentation with no readily available
open source code for implementation.  DieHarder will hopefully rectify
both situations and be <i>both</i> well documented <i>and</i> available
in clearly publically licensed code to make it extremely easy for
anybody to test random numbers on any GSL-supported platform.</p>

<p>Although this tool is being developed on Linux/GCC-based platforms,
it should port with no particular difficulty to other Unices, especially
ones that support RPMs.  No particular effort is being expended at this
time to make it run on Windows based compute platforms (due to a lack of
availability of such platforms and compilers to rgb) but there is no
reason to think that such a port would be terribly difficult PROVIDED
that the Gnu Scientific Library is installable under Windows.</p>

<center><h2>Essential Usage Synopsis</h2></center>

<p>If you compile the test or install the provided binary rpm's and run
it as:</p>

<tt>dieharder -a</tt>

<p>it should run -a(ll) tests on the default GSL generator.</p>

<p>Choose alternative tests with -g number where</p>

<tt>dieharder -g -1</tt>
<p>will list all possible numbers known to the current snapshot of the
DieHarder (mostly from the GSL).</p>

<tt>dieharder -l</tt>

<p>should list all the tests implemented in the current snapshop of
DieHarder.  Finally, the venerable and time tested:</p>

<tt>dieharder -h</tt>

<p> provides a Usage synopsis (which can quite long) and</p>

<tt>man dieharder</tt>

<p>is the (installed) man page, which may or many not be completely up
to date as the suite is under active development.  For developers,
additional documentation is available in the toplevel directory or doc
subdirectory of the source tree.  Eventually, a complete DieHard manual
in printable PDF form will be available both on this website and in
/usr/share/doc/dieharder-*/.</p>

<center><h2>List of Random Number Generators and Tests
Available</h2></center>

<p>List of GSL and user-defined random number generators that can be
tested by DieHarder:</p>
<pre>
rgb@lilith|B:1344>dieharder
              Listing available built-in gsl-linked generators:           |
 Id Test Name           | Id Test Name           | Id Test Name           |
==========================================================================|
  0 borosh13            |  1 cmrg                |  2 coveyou             |
  3 fishman18           |  4 fishman20           |  5 fishman2x           |
  6 gfsr4               |  7 knuthran            |  8 knuthran2           |
  9 lecuyer21           | 10 minstd              | 11 mrg                 |
 12 mt19937             | 13 mt19937_1999        | 14 mt19937_1998        |
 15 r250                | 16 ran0                | 17 ran1                |
 18 ran2                | 19 ran3                | 20 rand                |
 21 rand48              | 22 random128-bsd       | 23 random128-glibc2    |
 24 random128-libc5     | 25 random256-bsd       | 26 random256-glibc2    |
 27 random256-libc5     | 28 random32-bsd        | 29 random32-glibc2     |
 30 random32-libc5      | 31 random64-bsd        | 32 random64-glibc2     |
 33 random64-libc5      | 34 random8-bsd         | 35 random8-glibc2      |
 36 random8-libc5       | 37 random-bsd          | 38 random-glibc2       |
 39 random-libc5        | 40 randu               | 41 ranf                |
 42 ranlux              | 43 ranlux389           | 44 ranlxd1             |
 45 ranlxd2             | 46 ranlxs0             | 47 ranlxs1             |
 48 ranlxs2             | 49 ranmar              | 50 slatec              |
 51 taus                | 52 taus2               | 53 taus113             |
 54 transputer          | 55 tt800               | 56 uni                 |
 57 uni32               | 58 vax                 | 59 waterman14          |
 60 zuf                 |
                   Listing available non-gsl generators:                  |
 Id Test Name           | Id Test Name           | Id Test Name           |
==========================================================================|
 61 /dev/random         | 62 /dev/urandom        | 63 empty               |
 64 file_input          | 65 file_input_raw      |
</pre>

<p>Note that the last five tests are examples of random number
generators that have been wrapped up in GSL compatible clothes and
linked to the GSL so that the standard GSL interface works for them.
<i>Any</i> random number generator that one wishes to test can thus
easily be added for testing using these as prototypes, and can likely be
submitted to the GSL for inclusion if they pass the tests as well or
better than the tests that are already there.  That makes this a <i>very
convenient tool</i> for testing new RNGs.</p>

<p>Note also that the last two non-gsl generators are "universal"
generators in the sense that they permit you to input your OWN random
number stream from a file (but NOT from /dev/random or /dev/urandom, be
warned).  The file_input generator requires a file of "cooked" (ascii
readable) random numbers, one per line, with a header that describes the
format to dieharder.  This interface is still somewhat experimental --
not all ascii formats have been tested.  However, it has been tested and
should work for 32 bit unsigned integers represented directly in ascii
or as 32 bits of binary.  An example of the required header for these
formats is given here:</p>
<pre>
#==================================================================
# generator mt19937_1999  seed = 1274511046
#==================================================================
type: u
count: 100000
numbit: 32
3129711816
  85411969
2545911541
 903839182
2564046000
1157728411
 202655667
 969286899
1519043834
... (for 100,000 rands total).
</pre>
<pre>
#==================================================================
# handmade.  Comments are ignored, obviously.
#==================================================================
type: b
count: 10
numbit: 32
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
00000000000000000000000000000100
00000000000000000000000000000101
00000000000000000000000000000110
00000000000000000000000000000111
00000000000000000000000000001000
11111111111111111111111111111111
11111111111111110000000000000000
</pre>
<p>(where the latter is clearly not very random).</p>

<p>The last type, file_input_raw, accepts a file of raw bits as input,
such as might be generated by
<pre>
 dd if=/dev/urandom of=testrands.raw bs=4 count=1000000
</pre>
(to generate 1,000,000 four-byte ints directly from the
software-augmented kernel entropy generator).  That is, running the
tests from such a file should be <i>approximately</i> the same as
testing /dev/urandom directly.</p>

<p>The main (important!) difference is that some of the test require a
<i>lot</i> of random numbers -- far more than were needed by diehard.
Indeed, dieharder runs many of the diehard tests 100 <i>independent</i>
times, generating a p-value for each, and plots a histogram of the
p-values and generates a p-value for the (presumed uniform) distribution
of p-values!  This approach mimics the histogram presented in the STS
suite but augments it with a hard Kolmogorov-Smirnov p-value that
describes the distribution of p itself in many independent test
runs!</p>

<p>This protects one somewhat from the "p happens" problem described by
Marsaglia -- every now and then you <i>will</i> have a run with a very
low p from a <i>good</i> generator, but overall a good generator will
generate a uniform distribution of p-values.  Dieharder lets you
visually decide if the distribution is or isn't credibly uniform, while
giving you an index that in most cases is a fairly clear "good" or "bad"
indicator for a given random sequence or generator.  Direct control over
the number of samples used in the computation of the KS p-value (as well
as other important test parameters) permit one to "crank up" the
generator to clarify what appears to be a marginal level of success or
failure based on a few separate runs.</p>

<p>File input rands are delivered to the tests on demand, but if the
test needs more than are available it simply rewinds the file and cycles
through it again, and again, and again as needed.  Obviously this
significantly reduces the sample space and can lead to completely
incorrect results for the p-value histograms unless there are enough
rands to run EACH test without repetition (it is harmless to reuse the
sequence for different tests).  <b>Let the user beware!</b></p>

<p>List of the CURRENT fully implemented tests (as of the 07/12/06
snapshot):</p>
<pre>
rgb@lilith|B:1346>dieharder -l

                     DieHarder Test Suite
========================================================================
The following tests are available and will be run when diehard -a is
invoked.  Special options or suggested parameters are indicated if
they are needed to get a satisfactory result (such as completion in a
reasonable amount of time).

            Diehard Tests
   -d 1  Diehard Birthdays test
   -d 2  Diehard Overlapping Permutations test
   -d 3  Diehard 32x32 Binary Rank test
   -d 4  Diehard 6x8 Binary Rank test
   -d 5  Diehard Bitstream test
   -d 6  Diehard OPSO test
   -d 7  Diehard OQSO test
   -d 8  Diehard DNA test
   -d 9  Diehard Count the 1s (stream) test
   -d 10 Diehard Count the 1s (byte) test
   -d 11 Diehard Parking Lot test
   -d 12 Diehard Minimum Distance (2D Spheres) test
   -d 13 Diehard 3D Spheres (minimum distance) test
   -d 14 Diehard Squeeze test
   -d 15 Diehard Sums test
   -d 16 Diehard Runs test
   -d 17 Diehard Craps test
   -d 18 Marsaglia and Tsang GCD test

             RGB Tests
   -r 1 Bit Persist test
   -r 2 Bit Ntuple Distribution test suite (-n ntuple for 1-8)
   -r 3 Timing test (times rng)

      Statistical Test Suite (STS)
   -s 1 STS Monobit test
   -s 2 STS Runs test

            User Tests
   -u 1 User Template (Lagged Sum Test)

</pre>

<p>Note that the design goal of completely encapsulating diehard is
<b>COMPLETED</b> with all tests apparently functional as of 7/12/06.
dieharder is now in a "beta" debugging/testing phase until the new code
shakes out, but it produces what are for the most part very reasonable
and consistent values for all the tests on known "good" or "bad" random
number generators encapsulated in the GSL.</p>

<p>Full descriptions of the tests are available (as you can see) from
within the tool and source documentation.  All tests are completely and
independently rewritten from their description alone, and may be
functionally modified or extended relative to the original source code
published in the originating suite.  The author (rgb) bears complete
responsibility for these changes, subject to the standard GPL code
disclaimer (in essence, yes it's my fault if they don't work but using
the tool is at your own risk and you can <i>fix it</i> if it bothers
you and/or I don't fix it first).</p>

<center><h2>Development Notes</h2></center>

<p>All tests are encapsulated to be as standard as possible in the way
they compute p-values from single statistics or from vectors of
statistics, and in the way they implement the underlying KS and chisq
tests.  Diehard is now complete in dieharder, and attention will turn
towards implementing more selected tests from the STS.  I also have my
eye on the as-yet unimplemented tests from Knuth's <i>The Art of
Programming</i>, lagged correlation, and more bitwise tests that have
occurred to me as I ported diehard (which does some things somewhat
backwards or indirectly, IMO).</p>

<center><h2>Thoughts for the Future/Wish List/To Do</h2></center>

<ul>

<li> Tests of GSL random distribution (as opposed to number) generators,
as indirect tests of the generators that feed them.

<li> Anderson-Darling KS test.  Kuiper works, but AD is more common.  It
therefore should be a user choice, or should even do both.  Why not?
The computation for either is trivial compared to the effort required to
run the tests in the first place.

<li> New tests, compressions of existing ones that are "different" but
really the same.  Hyperplane tests.  Spectral tests.  Especially the bit
distribution test with user defineable lag or lag pattern (to look for
subtle, long period correlations in the bit patterns produced).

<li> Collaborators.  Co-developers welcome, as are contributions or
suggestions from users.  Note well that users have already provided
critical help debugging the early code!  Part of the point of a GPL
project is that you are NOT at the mercy of a black box piece of code.
If you are using dieharder and are moderately expert at statistics and
random numbers and observe something odd, please help out!

</ul>

<center><h2>Conclusions</h2></center>

<p>I hope that even during its development, you find dieharder useful.
Remember, it is fully open source, so you can freely modify and
redistribute the code according to the rules laid out in the Gnu Public
License (version 2b), which might cost you as much as a beer one day.
In particular, you can easily add random number generators using the
provided examples as templates, or you can add tests of your own by
copying the general layout of the existing tests (working toward a
p-value per run, cumulating (say) 100 runs, and turning the resulting KS
test into an overall p-value).  Best of all, you can look inside the
code and see how the tests work, which may inspire you to create a new
test -- or a new generator that can <i>pass</i> a test.</p>

<p>To conclude, if you have any interest in participating in the
development of dieharder, be sure to let me know, especially if you have
decent C coding skills (including familiarity with Subversion and the
GSL) and a basic knowledge of statistics.  I even have documents to help
with the latter, if you have the programming skills and want to LEARN
statistics.  Bug reports or suggestions are also welcome.</p>

<p>Submit bug reports, etc. to</p>
<address>
  rgb at phy dot duke dot edu
</address>