-
Notifications
You must be signed in to change notification settings - Fork 0
/
README.etaus
159 lines (120 loc) · 6.28 KB
/
README.etaus
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
etaus is a random number generator (RNG) that produces 32-bit unsigned
integers in a uniform distribution. etaus is based on 1024 32-bit
states. etaus uses these 1024 states to perform a Bays-Durham shuffle.
The 'e' in "etaus" means "extended taus", because the period length
of etaus is much longer than the original taus algorithm, created
by Professor Pierre L'Ecuyer at the University of Montreal, Montreal,
Quebec, Canada.
Period length of etaus.
The period length of etaus is based on the random number generator
state. In the case of etaus, the random number generator state is
three generations of output, plus an array of 1024 states used by
the Bays-Durham shuffle, plus the three states used by the TAUS
algorithm.
The period length is the number of generations it takes before
every output of the random number generator is repeated in sequence
for the same number of generations.
Because of the Bays-Durham shuffle, the period length of etaus is
theoretically 5.41e+2639, or the factorial of 1024. The period
length is so long that it can not be demonstrated on the strongest
super-computer in existence today.
One way to test the period length is to build a database, where the
key is two successive overlapping generations of etaus output. If
there are no duplicate keys after hundreds of trillions of generations,
then the period length is at least as long as the test. If the test
fails, then increase the size of the key to three successive overlapping
generations of etaus output, and rerun the test.
Another way to test the period length is to run the qmatch program
in this repository. qmatch compares 1024 successive outputs of etaus
to an original list of 1024 successive outputs. 99.9999999% of the
time, the comparison fails on the first node in the list.
Test results.
The etaus random number generator has tested successfully in the
following tests.
dieharder -a
TestU01 Crush
National Institute of Standards and Technology STS test suite.
The dieharder test yielded three weak p-values that were above
0.99. That meant that the three weak test results were too
good to be random. There were no fails in the dieharder test.
Upon retesting, the three weak p-values did not appear in
the same three tests, so weak results are subject to chance
with the etaus generator.
The TestU01 Crush test yielded no fails.
Most of the STS tests are easy to pass, and so passing them does
not validate a generator to any great degree. Nevertheless,
etaus passed the STS suite of tests, especially the harder tests.
TestU01 incorporates the STS suite of tests into its own Crush
suite. Dieharder incorporates George Marsaglia's original diehard
suite of tests.
Benchmarking.
The benchmarking program counts the number of ticks taken to call
the random number generator one hundred million times. etaus
performs about one sixth faster than the taus2 and Mersenne Twister
generators in the GNU Scientific Library (GSL).
When testing etaus as input to dieharder -g 200, be cautioned
that the raw input feature of dieharder slows down the test.
It is better to integrate etaus into dieharder as an internal
random number generator in the 600 series of generators.
The same is true with TestU01. It is better to integrate etaus
as an internal random number generator in order to speed up the
test.
When fed as raw input to dieharder through a pipe, the etaus
generator consumes about 20% of the CPU, while dieharder consumes
about 70%.
Initialization.
Initialize the 1024 states in etaus to non-zero random or arbitrary
values. That amounts to initializing etaus to more than 4000 bytes
of data.
If you wish, you may override the initial values of the state array,
so that you may conduct regression tests. You will also have to
initialize the three taus states, the two previous outputs, and the
current output to arbitrary values.
All of the etaus states are available to the programmer through a
public structure. See etaus.h for the structure.
Distributed processing.
etaus is conducive to running on a Beowulf style of supercomputer.
Each of its 1024 states may be manipulated independently in separate
nodes of the supercomputer. The one bottle neck occurs during the
Bays-Durham shuffle, when the state array is being changed.
I see no reason why etaus could not keep pace with the fastest
supercomputer in a scientific experiment.
Supporting subroutines.
The etaus generator has four subroutines that depend on it.
The calling program is responsible for passing valid parameters.
Each subroutine may be called billions of times in a scientific
experiment. Validation in the subroutine would be redundant
in most cases.
etausunif.c produces a uniform random number from 0 - 1. Its only
parameter is the etaus structure.
etausint.c produces a uniform random integer from 0 up to a limit.
It has two parameters, the etaus structure, and the limit. The
limit may be negative or positive.
etauspwr.c produces an unsigned integer of 1 to 32 bits. It has
two parameters, the etaus structure, and the number of bits.
etausbit.c produces a boolean integer (0 or 1). Its only
parameter is the etaus structure.
Utilities.
etausgen.c produces an ASCII stream of ones and zeros to stdout.
etausraw.c feeds random binary data into down stream programs,
such as dieharder or TestU01 test programs..
Porting to Mingw.
etaus is easy to port to Mingw on Windows 10. The make files have
to conform to Windows EXE format. etausinit.c has to be changed
slightly. The date/time routine is different in Mingw, and the
clock routine is not used. Therefore the three states for the
taus algorithm need three permutations of the same date and time.
The Monte Carlo test programs have to change because they compare
results with GNU Scientific Library random number generators. Under
Mingw, the etaus integral is only compared with the mathematical
solution. Timings based on clock ticks are eliminated from the
program.
etaustim.c needs to be eliminated from the test suite. Clock ticks
are not reliable in Mingw.
poischi.c needs a small change under Mingw. The valid range for
the chi square should come from a table, rather than from a GSL
subroutine. The chi square range varies, depending on the value
of lambda.
Read INSTALL for installing etaus.
Read TESTING for running tests in this repository.
The website for etaus is at https://aquila62.github.io.