1\chapter{UNIFORM GENERATORS} 2 3This chapter contains a description of various uniform generators 4already programmed in this library and which were proposed by various 5authors over the past several years, as well as tools for managing 6and implementing additional types of generators. 7Related generators are regrouped in the same module. 8For example, the linear congruential generators (LCGs) are in module 9{\tt ulcg}, the multiple recursive generators (MRGs) are in {\tt umrg}, 10the inversive generators in {\tt uinv}, 11the cubic generators in {\tt ucubic}, etc. 12We emphasize that the generators provided here are not all recommendable; 13in fact, {\em most of them are not}. 14 15The module {\tt unif01} contains the basic utilities for defining, 16manipulating, filtering, combining, and timing generators. 17Each generator must be implemented as an 18object of type {\tt unif01\_Gen}. To implement one's own generator, 19one should create such an object and define all its fields. 20For each generator, the structure {\tt unif01\_Gen} must contain a 21function {\tt GetU01} that returns values in the interval $[0,1)$ 22and a function {\tt GetBits} that returns a block of 32 bits. 23Most of the tests in the {\tt s} modules call the generators 24to be tested only indirectly, through the use of the interface 25functions {\tt unif01\_StripD}, {\tt unif01\_StripL} and 26{\tt unif01\_StripB}. 27These functions drop the $r$ most significant bits of each random number 28generated and returns a number built out of the remaining bits. 29 30It is also possible to test one's own or an external generator 31(that is, a generator that is not predefined in TestU01) very easily with 32the help of the functions {\tt unif01\_CreateExternGen01} and 33{\tt unif01\_CreateExternGenBits} (see page \pageref{externgen} 34of this guide), as long as this generator is programmed in C. 35 36Figure~\ref{fig:usegen} gives simple examples of how to use predefined 37generators. The program creates a LCG with modulus $m = 2^{31}-1$, 38multiplier $a = 16807$, and initial state $s = 12345$, 39generates and adds 100 uniforms produced by this generator, 40prints the sum, and deletes the generator. 41To illustrate the fact that there are different ways of getting the 42uniforms from the generator, we have generated the first 50 by calling 43the {\tt GetU01} function and the next 50 via {\tt unif01\_StripD}. 44These two methods are equivalent. 45The program then instantiates the generator {\tt lfsr113} available in 46module {\tt ulec}, with the vector $(12345, \ldots, 12345)$ as initial seed, 47generates and prints five integers in the range $\{0,\dots,2^{10}-1\}$ 48(i.e., 10-bit integers) obtained by taking five successive output values 49from the generator, stripping out the four most significant bits from 50each value, and retaining the next 10 bits. 51 52For each public identifier used in programs, it is important to 53include the corresponding header file before using it, 54so as to inform the compiler about the type and signature of functions 55and exported variables. For instance, in the following examples, the header 56files \texttt{unif01.h}, \texttt{ulcg.h} and \texttt{ulec.h} contain the 57declarations of \texttt{unif01\_Gen}, \texttt{ulcg\_CreateLCG} and 58\texttt{ulec\_Createlfsr113}, respectively. 59 60Other examples on how to use the facilities of module {\tt unif01} are given 61at the end of its description. 62 63 64\setbox0=\vbox {\hsize = 6.0in 65\smallc 66\verbatiminput{../examples/ex1.c} 67} 68 69\begin{figure} 70\centering 71\myboxit{\box0} 72\caption {Using pre-programmed generators\label {fig:usegen}} 73\end{figure} 74 75 76\iffalse %%%%%%% 77%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 78 79\section {La vitesse des generators} 80 81Les Tableaux \ref{vitesse1}--\ref{vitesse10} donnent une idee 82du temps d'execution moyen 83par appel (en micro-secondes), pour un certain number de generators 84fournis par the modules {\tt u...}. 85Ces values sont en fait le number de secondes 86requises pour un million $(10^6)$ d'appels, 87donne ici a une seconde pres. 88La machine utilisee etait un SUN UltraSparc 150. 89%% 80386 avec coprocesseur 80387, tous deux a 16 MHz. 90Pour fins de comparaison, pour un million d'appels a une procedure 91``bidon'' ne faisant rien, dans le m\^eme contexte, il a fallu 0.26 secondes. 92 93\begin{table}[htb] \centering \tt 94\caption {\rm Vitesse moyenne par appel pour the generators 95 du module ulcg.} 96\label {vitesse1} 97\begin{tabular}{|l|r|c|l|r|} 98\hline 99&&&&\\ 100\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 101 & $\mu$-sec.\\ 102\hline \hline 103&&&&\\ 104 LCG$^1$ & 1.03 && CombLEC2$^2$ & 4.55\\ 105 LCG$^2$ & 2.33 && CombLEC2$^3$ & 20.22\\ 106 LCG$^3$ & 10.91 && CombLEC3$^2$ & 6.60\\ 107 LCGFloat & 0.80 && & \\ 108 BigLCG & 45.24 && CombWH2$^1$ & 2.49\\ 109 LCG2e31 & 0.98 && CombWH2$^2$ & 4.67\\ 110 LCG2e32 & 0.95 && CombWH2$^3$ & 20.40\\ 111 LCG2e31m1HD & 1.73 && CombWH3$^2$ & 7.25\\ 112 CombLEC2$^1$ & 2.22 && & \\ 113&&&&\\ 114\hline 115\end{tabular} 116 117\begin {verse} 118 $^1$ : $(m-1)a + c$ representable en {\tt LONGINT} (implantation directe).\\ 119 $^2$ : implantation utilisee lorsque $a (m\mod a) < m$.\\ 120 $^3$ : implantation utilisee dans the autres cas.\\ 121\end {verse} 122\end {table} 123 124\begin{table}[htb] \centering \tt 125\caption {\rm Vitesse moyenne par appel pour the generators 126 du module umrg.} 127\label {vitesse2} 128\begin{tabular}{|l|r|c|l|r|} 129\hline 130&&&&\\ 131\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 132 & $\mu$-sec.\\ 133\hline \hline 134&&&&\\ 135 MRG$^1$ & 12.36 && MRG$^3$ & 6.35\\ 136 MRG$^2$ & 4.13 && C2MRG & 10.71\\ 137 LagFib & 0.59 && &\\ 138\hline 139\end{tabular} 140 141\begin {verse} 142 $^1$ : implantation generale.\\ 143 $^2$ : implantation plus rapide mentionnee dans {\tt SetMRG}.\\ 144 $^3$ : varie selon que $p - d < 32$ ou non et que $d < 32$ ou non.\\ 145\end {verse} 146\end {table} 147 148 149\begin{table}[htb] \centering \tt 150\caption {\rm Vitesse moyenne par appel pour the generators du 151 module utaus.} 152\label {vitesse3} 153\begin{tabular}{|l|r|c|l|r|} 154\hline 155&&&&\\ 156\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 157 & $\mu$-sec.\\ 158\hline \hline 159&&&&\\ 160 Taus & 0.69 && CombTaus3 & 1.60\\ 161 TausJ & 3.52 && Tez95 & 1.48\\ 162 LongTaus & 1.07 && TezLec91 & 1.17\\ 163 CombTaus2 & 1.17 && Tausme3a & 1.49\\ 164&&&&\\ 165\hline 166\end{tabular} 167 168\end {table} 169 170\begin{table}[htb] \centering \tt 171\caption {\rm Vitesse moyenne par appel pour the generators 172 du module ugfsr.} 173\label {vitesse4} 174\begin{tabular}{|l|r|c|l|r|} 175\hline 176&&&&\\ 177\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 178 & $\mu$-sec.\\ 179\hline \hline 180&&&&\\ 181 GFSR & 0.66 && Toot73 & 0.62\\ 182 TGFSR & 0.81 && Fushimi90 & 0.67\\ 183 Ripley90 & 0.53 && Kirk81 & 0.65\\ 184&&&&\\ 185\hline 186\end{tabular} 187 188\end {table} 189 190\begin{table}[htb] \centering \tt 191\caption {\rm Vitesse moyenne par appel pour the generators 192 du module uinv.} 193\label {vitesse5} 194\begin{tabular}{|l|r|c|l|r|} 195\hline 196&&&&\\ 197\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 198 & $\mu$-sec.\\ 199\hline \hline 200&&&&\\ 201 InvImpl & 14.18 && InvExpl & 14.77\\ 202 InvImpl2a & 22.95 && InvExpl2a & 35.21\\ 203 InvImpl2b & 22.82 && InvExpl2b & 27.46\\ 204 InvMRG & 23.12 && & \\ 205&&&&\\ 206\hline 207\end{tabular} 208 209\end {table} 210 211\begin{table}[htb] \centering \tt 212\caption {\rm Vitesse moyenne par appel pour the generators 213 du module uquad.} 214\label {vitesse6} 215\begin{tabular}{|l|r|c|l|r|} 216\hline 217&&&&\\ 218\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 219 & $\mu$-sec.\\ 220\hline \hline 221&&&&\\ 222 Quadratic & 13.81 && Quadratic2$^1$& 14.77\\ 223 Quadratic2 & 1.63 && & \\ 224&&&&\\ 225\hline 226\end{tabular} 227 228\begin {verse} 229$^1$ : implantation rapide : e = 32.\\ 230\end {verse} 231\end {table} 232 233\begin{table}[htb] \centering \tt 234\caption {\rm Vitesse moyenne par appel pour the generators 235 du module ulec.} 236\label {vitesse7} 237\begin{tabular}{|l|r|c|l|r|} 238\hline 239&&&&\\ 240\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 241 & $\mu$-sec.\\ 242\hline \hline 243&&&&\\ 244 CombLec88 & 2.98 && CombMRG96 & 5.47\\ 245 MRG93 & 3.31 && CombMRG96d & 11.22\\ 246 CombLec88Float & 1.38 && CombMRG96Float & 2.60\\ 247 & && CombMRG96dFloat & 5.13\\ 248&&&&\\ 249\hline 250\end{tabular} 251 252\end {table} 253 254\begin{table}[htb] \centering \tt 255\caption {\rm Vitesse moyenne par appel pour the generators 256 du module ucarry.} 257\label {vitesse8a} 258\begin{tabular}{|l|r|c|l|r|} 259\hline 260&&&&\\ 261\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 262 & $\mu$-sec.\\ 263\hline \hline 264&&&&\\ 265 AWC & 0.85 && MWC$^1$ & 13.03\\ 266 SWC & 0.85 && SWC$^1$ & 3.79\\ 267&&&&\\ 268\hline 269\end{tabular} 270 271\begin {verse} 272 $^1$ : implantation generale, e = 32.\\ 273\end {verse} 274\end {table} 275 276\begin{table}[htb] \centering \tt 277\caption {\rm Vitesse moyenne par appel pour the generators 278 du module umarsa.} 279\label {vitesse8} 280\begin{tabular}{|l|r|c|l|r|} 281\hline 282&&&&\\ 283\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 284 & $\mu$-sec.\\ 285\hline \hline 286&&&&\\ 287 KISS & 0.76 && Combo & 1.15\\ 288 Marsa90a & 0.87 && ECG1 & 1.34\\ 289 Marsa90b & 0.83 && ECG2 & 1.31\\ 290 Mother0 & 1.77 && ECG3 & 1.39\\ 291 &&& ECG4 & 1.36 \\ 292% Mother1$^1$ & 5.95 && & \\ 293&&&&\\ 294\hline 295\end{tabular} 296\end {table} 297 298\begin{table}[htb] \centering \tt 299\caption {\rm Vitesse moyenne par appel pour the generators 300 du module unumrec.} 301\label {vitesse9} 302\begin{tabular}{|l|r|c|l|r|} 303\hline 304&&&&\\ 305\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 306 & $\mu$-sec.\\ 307\hline \hline 308&&&&\\ 309 Setran0 & 2.33 && Setran2 & 5.25\\ 310 Setran1 & 2.91 && & \\ 311&&&&\\ 312\hline 313\end{tabular} 314 315\end {table} 316 317\begin{table}[htb] \centering \tt 318\caption {\rm Vitesse moyenne par appel pour the generators 319 des modules uvaria et ufile.} 320\label {vitesse10} 321\begin{tabular}{|l|r|c|l|r|} 322\hline 323&&&&\\ 324\multicolumn{1}{|c|}{\rm Generator} & $\mu$-sec. && {\rm Generator} 325 & $\mu$-sec.\\ 326\hline \hline 327&&&&\\ 328 Tindo & 64.31 && ACORN & 75.33\\ 329 CSD & 6.03 && ReadFile & 13.82\\ 330&&&&\\ 331\hline 332\end{tabular} 333 334\end {table} 335 336\fi %%%%%%%%%%%%%%%%%%%% 337