The ThinAir FAQ
ThinAir is a C++ class library which defines a simple, powerful interface to a
set of pseudo-random number generators (PRNGs). This class library gives a
large number of generators, all having the same interface.
Besides the fact that naming a class library is one of the few things
harder than actually writing one, I had two reasons for naming it ThinAir.
Both are based on the same pun (suggested by Rick Hoselton). Unfortunately
"thin air" is where most people get their random numbers. People who are
somewhat more sophisticated get their random numbers from PRNGs. Those people
usually get their generators from "thin air."
If you do any programming project requiring random sequences of numbers,
ThinAir may be able to help you. This library provides a large number of
generators. These generators all have the same interface. So if you decide
that one generator does not suit your application, changing to another
can be (almost) painless.
Seventeen.
In most cases, when a person asks for a random number, what they really want is
an unpredictable number. PRNGs provide somewhat unpredictable streams of
numbers.
Random number sequences are useful in many kinds of programming projects. A
couple of obvious examples include simulations and computer games. Many
mathematical problems are solved using the Monte Carlo method, which consumes
quite a few random numbers.
It is not possible to generate real random numbers or random number
sequences computationally. Most functions that claim to generate random
numbers actually generate pseudo-random number sequences. In other
words, the function generates a sequence of numbers that appears to be
random as long as you don't look at it too carefuly. In order to save typing,
I normally refer to a "pseudo-random number generator" as a PRNG.
Historically, the random number generators provided in most languages have
been lousy. In many Fortran implementations, the RANDU function was provided as
the standard PRNG. This generator has been extensively studied and found to be
horrible. Not all generators are this bad, but many are less than ideal.
In addition, once you have coded a particular generator into your program, it's
probably not going to be easy to change. If the program has problems, you
won't be able to tell if the problem is the generator or your code.
There are many uses for sequences of random numbers in cryptography. Most
PRNGs are not suited for these projects. In general, with a small amount of
knowledge, a cryptographer can crack most PRNGs with only a few contiguous
numbers from the PRNG sequence. Most of the generators in this library are
not suited to cryptography. Before using this library for a cryptographic
project, you should do quite a bit of research.
The short answer is "You don't."
With most PRNGs, an expert can use a sequence of numbers from your generator
and reverse engineer the generator you're using. When that's done, the expert
can duplicate any password ever generated by your system.
With a solid background in information theory and a very paranoid mind, it is
possible to generate good passwords with the help of a PRNG. But the PRNG
becomes a small part of the overall solution.
If you have a generator you would like me to add to ThinAir, send me
email on your generator. I'll do what
I can to get the PRNG converted.
If you want to extend the ThinAir library yourself, please send me the completed
code, if you don't mind having your generator freely available. I will make certain
full credit is given for your work in the source and the documentation.
The best PRNG to use depends on the particular problem you are solving. If you
are working on a simple computer game, any reasonable random sequence
may be good enough. A more complex game or a simulation would need a higher
quality sequence. If the results of your program will affect lives or
large amounts of money, you probably want very convincing proof of the
randomness of the sequence.
The length of the sequence you need also plays a role in your selection. If you
only need 6 numbers in a sequence, you probably don't care if the generator
repeats after 1000 numbers or 231-1 numbers. However, if your simulation
runs for days, and consumes billions of numbers, the generator's period is much
more important.
There are several published algorithms for testing random number sequences. One of the
best sets of tests is published in Knuth's Art of Computer Programming,
Vol 2. Unfortunately, Knuth's algorithm's are somewhat difficult to convert
into code.
Dr. Jerry Dwyer and K. B. Williams coded Knuth's algorithms and published in
two issues of C/C++ Users Journal.
The code for June and
August is available online from
CUJ.
Probably the simplest way to test random sequences is to use Marsaglia's DIEHARD
Battery of Tests of Randomness (
http://stat.fsu.edu/~geo/diehard.html).
A good PRNG should produce a sequence of numbers that is unpredictable. You
might ask how you measure this unpredictability. Here are some characteristics
of a good random sequence of numbers.
- Long period. The generator should take a long time to repeat.
- Uniform distribution. Every number or range of numbers should be equally
likely. (Doesn't apply for generators designed to have other
distributions.)
- Low correlation between nearby numbers. Looking at a small set of the
sequence should not make it easier to predict the next number.
A bad PRNG can have one or more bad characteristics which can affect your
programs. A PRNG that has short cycles can generate artificial
patterns in our output data. A PRNG that has long runs of increasing
or decreasing numbers can cause similar effects. A PRNG that does not cover the
full range of numbers might not cover the full range of test-cases needed by
your program. For instance, how useful is a generator that always generates
32-bit integers in the range 1000 - 65536. A PRNG that generates numbers in
clumps would also cause patterns that have nothing to do with your
code.
Almost everyone has a scheme for generating random numbers. What most people
don't realize is that choosing a generator at random, or making a quick little
change to make the generator "even more random" is very likely to destroy the
good properties of a particular generator.
One of my favorite examples involves the C rand() and
randomize() functions. I have seen several people try to make
rand() "even more random" by calling randomize()
regularly in their code. (Sometimes before every rand() call.)
What they don't realize is that randomize() resets the current
value of rand() with the system time. This almost guarantees a
linearly increasing set of random numbers.
For a good, bad example of a "super-random" generator, see Knuth, Vol. 2,
Section 3.1, Algorithm K.
One good way to test your code for sensitivity to bad random sequences is to
run it using a non-random sequence generator. For this reason, the ThinAir
library includes several (well-labelled) bad generators. These can be used to
test programs or to break random sequence test programs. For instance, what
does the test program do with the output of a simple counter?
I have tried to give information and references on every generator in the
library. In addition, I have attempted to simplify the use of
DIEHARD tests to test
PRNGs in ThinAir. I want to convert any random number tests I find to deal with
the ThinAir interface.
The ThinAir library contains a special interface to allow you to plug
a ThinAir generator in place of the rand() function. You will need
to include the header file rand_rng.h in any file that calls rand()
or its friends. You will also need to call the function ResetGenerator()
at the beginning of your code to set the generator. See the
documentation for further details.
Yes. The STL template function random_shuffle() requires a function
object which generates a random number sequence. ThinAir implements a function
object interface for just this purpose.
I am currently doing all maintenance on the library myself. This means that
the only platforms I can guarantee are the one's I have access to. The
current list includes Borland C++ 4.5 (DOS, Windows), Visual C++ 4.2
(Windows, port in progress), and Gnu++ 2.7.2 (Linux).
If you need ThinAir to work in another environment, email
me. I will do all that I can (within
reason) to help make it work in your environment. If you make changes to the
source to port ThinAir to another environment, please send me the changes so
that I can incorporate them into the official source. I am trying my best to
give full credit for all changes in the source and documentation.
You will be able to download ThinAir from this
site soon. The ThinAir library is supplied as an archive containing all of
the source and documentation.
You can use applications generated using the ThinAir library in any way you
like. I retain the copyright on all of the source code. If you distribute
the source code, you must retain all copyright messages in that source.
That's it. I would also appreciate a quick email message explaining any
uses you have made of the ThinAir library. I would like to have a page on this
site describing interesting uses for the ThinAir library, someday.
Since the ThinAir library is distributed as source code, building the library
becomes an interesting challenge. The source distribution comes with three
makefiles for three different environments. You can also see the file
README which describes the various makefiles and tells
how to go about converting one of the makefiles to your environment. In
some cases, all you will need to do is change a few directories in the makefile
and type
make -f [makefile]
where [makefile] would be replaced by the name of the correct makefile. If you
need more help on make, see the documentation for your system.
For further information, contact G. Wade Johnson
(gwadej@anomaly.org).
© 1996 G. Wade Johnson.
All rights reserved.
http://www.anomaly.org/ThinAir/faq.html