Pure Programmer
Project: ACORN Pseudo-Random Number Generator
Write a class that implments the [[ACORN Pseudo-Random Number Generator]]. The class constructor should take a single integer that defines the order value for the generator. The constructor should set the modulus to 232 and generate the initial values to seed the generator using the standard built-in random generator. The class should provide generator objects with two methods, nextInt() and nextFloat() that produce a random 32-bit integer or random floating point value in the range [0,1) respectively.
Write a main method that takes two command line arguments: the number of values to generate and the type of values "int" or "float". The program should create a generator object with order 10. Then generate output that is compatible with the [[Dieharder]] program that tests a generator for "randomness". This is basically text output of one random number per line, either a positive integer if "int" is specified on the command line or a 10 digit floating point value in the range [0,1) if "float" is specified. The file has a few lines of header before the random numbers as follows:
For 32 Unsigned Decimals
type: d count: 10 numbit: 32 2098827589 439136540 2373046645 ...
For Floating Point
type: f count: 10 numbit: 32 0.3371689620 0.1058913951 0.6198943132 ...
Use the Dieharder program to test the randomness of the generator. You can run the ACORN program to generate 109 random integers and redirect into a file called acorn.dat. Then run Dieharder.
$ dieharder -g 202 -a -f acorn.dat
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name | filename |rands/second|
file_input| acorn.dat| 4.27e+06 |
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.16148359| PASSED
diehard_operm5| 0| 1000000| 100|0.01254752| PASSED
diehard_rank_32x32| 0| 40000| 100|0.42647251| PASSED
...
What value for the order should we use to get passing results from Dieharder? Add the additional capability to output an infinite stream of random bytes if no arguments are specified on the command line. Then we can use this program to feed the stream of random bytes to Dieharder like this...
$ ACORN_PRNG | dieharder -g 200 -a
Where ACORN_PRNG is replaced by the invokation of this program as appropriate. Alternatly you can use some of the other projects on this page to generate a histogram of some random bytes to see if they appear uniformly distributed. First generate some random bytes into a file. You will need to press Ctrl-C after about 10 seconds to stop the generation of bytes.
$ ./ACORN_PRNG_Test > test.dat
Then pipe the data through FrequencyTableBytes, ReorderColumns and finally Histogram.
$ cat test.dat | ./FrequencyTableBytes | ./ReorderColumns 1 4 | ./Histogram
For a uniform distribution, all bars in the histogram should be roughly equal for large sample sizes.
ACORN PRNG Formula
The ACORN PRNG is defined by the following equations:
Let the order `k` and the modulus `M` (typically an integer power of 2) be positive integers.
Define the array `Y[m]` where `m = 0,1,...,k` to contain a randomly selected positive integer seed values satisfying the relation `0 <= Y[m] < M` for all elements of the seed array. The seed values and `M` should be realtively prime, meaning that they have no factors in common. If `M` is a power of 2, then the seed values simply need to be odd to satisfy this condition.
To compute the next random integer `n` in the sequence compute:
`Y[m] = (Y[m-1] + Y[m]) mod M` where `m = 1,2,...,k` (Must be computed in this order)
then return `Y[k]` as the next random positive integer less than `M`
If a random floating point value in the range [0,1) is desired, return `Y[k] // M` using floating point division.
See [[ACORN_(PRNG)|ACORN PRNG]]