Pure Programmer
Blue Matrix

Cluster Map

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

For Floating Point

type: f
count: 10
numbit: 32

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.


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.


$ g++ -std=c++17 ACORN_PRNG_Test.cpp -o ACORN_PRNG_Test -lfmt $ ./ACORN_PRNG_Test 10 int type: d count: 10 numbit: 32 3525859771 299349408 94661936 3464755953 886085559 2552130646 3532328694 1290424736 1909062334 3213765198 $ g++ -std=c++17 ACORN_PRNG_Test.cpp -o ACORN_PRNG_Test -lfmt $ ./ACORN_PRNG_Test 10 float type: f count: 10 numbit: 32 0.8209281999 0.0696977153 0.0220401995 0.8067013586 0.2063078710 0.5942142210 0.8224343634 0.3004504219 0.4444882120 0.7482630196