% \iffalse % File: lcg.dtx %% Copyright (c) 2001--2013 Erich Janka (erich.janka@gmail.com) %% %% This package may be distributed and/or modified under the terms of the %% LaTeX Project Public License, as described in lppl.txt in the base %% LaTeX distribution, either version 1.2 or (at your option) %% any later version. %% The latest version of this license is in %% http://www.latex-project.org/lppl.txt %% %% This program consits of the files lcg.dtx and lcg.ins % %\NeedsTeXFormat{LaTeX2e} %\ProvidesPackage{lcg}[2013/08/09 v1.3 generating random numbers] %\RequirePackage{keyval} % %<*driver> \documentclass{ltxdoc} \usepackage[first=10, last=20]{lcg} \begin{document} \GetFileInfo{lcg.sty} \title{The \texttt{lcg} package} \author{Erich Janka\\ \texttt{erich.janka@gmail.com}} \date{2013/08/09 (v1.3)} \maketitle \DocInput{lcg.dtx} \end{document} % % % \fi % % \iffalse %<*lcg> % \fi % % \newcommand{\mod}{\;\;\mbox{mod}\;\;} % \newcommand{\key}[1]{\meta{#1}} % \newcommand{\cntr}[1]{\texttt{#1}} % % \begin{abstract} % % This Package contains macros to generate (pseudo) random numbers % with \LaTeX\ by a simple linear congruential generator. % The user can specify a range of integers % containing the generated random numbers. % % To pass options to the package, the \meta{key}=\meta{value} % scheme of the \texttt{keyval} package is used. % % If no options are specified, random numbers will be % generated in the interval from $1$ to $2^{31}-1 \;\;(= 2147483647)$. % Let $S$ be the smallest and $L$ the largest number of the specified range, % then the following inequalities must hold because of % limitations of \LaTeX: % % $$ -2^{31}+1 \leq S \leq L \leq 2^{31}-1 \qquad\mbox{and}\qquad % L-S \leq 2^{31}-2 $$ % % The generated random numbers will be stored in a \LaTeX\ % counter definable by the user. % \end{abstract} % % \section{User Interface} % % The \texttt{lcg} package is loaded with\\[1ex] % \hspace*{2ex}\cmd{\usepackage\oarg{list of options}\{lcg\}}.\\[1ex] % The optional Argument is a comma separated list of entries of % the kind \key{key}=\key{value} or \key{key}. In the second case % the key will be set to a standard value. % For example the line\\[1ex] % \hspace*{2ex}\cmd{\usepackage[first=10, last=20]\{lcg\}}\\[1ex] % loads the package and generates the \LaTeX\ counter \cntr{rand} % which will hold pseudo random numbers from $10$ to $20$. % All available keys and their standard values are introduced below. % \begin{macro}{\rand} % Each call of the command \cmd{\rand} will write a new random number % to the counter provided by the user with the key \key{counter} or % to the standard counter of this package---\cntr{rand}. Now % it's possible to do whatever can be done with counters. The command % evokes a linear congruential random number generator described below. % \end{macro} % \begin{macro}{\reinitrand} % The command \cmd{\reinitrand}\oarg{list of options} has % one optional argument which is identical to the argument of % \cmd{\usepackage}, % i.~e. the same keys in the comma separated list are allowed. % The effect is that specified keys will be set and all others % will be reset to their standard values. % \end{macro} % \begin{macro}{\chgrand} % The syntax of the command \cmd{\chgrand} is identical to \cmd{\reinitrand}. % The difference is that \cmd{\chgrand} will set the specified keys but % won't effect any other key. % \end{macro} % % \subsection{The Options} % % This section deals with the list of all available keys % and their standard values. % \begin{macro}{counter} % This key sets the name of the \LaTeX\ counter where % the random numbers will be stored. % If the counter already exists (maybe somebody likes % random page numbers), \LaTeX\ will prompt a % warning and will use it. If the counter doesn't exist, % it will be defined by this package and set to $0$.\\ % \textbf{Standard value:} rand % \end{macro} % \begin{macro}{first} % This key sets the left boarder of the range within % random numbers will be generated. % Its value can be any number from $-2^{31}+1$ to $2^{31}-1$, % as long as it is not greater than the value of the key \key{last} % and the difference to the value of \key{last} doesn't exceed % $2^{31}-2$.\\ % \textbf{Standard value:} $1$ % \end{macro} % \begin{macro}{last} % This key sets the right boarder of the range within % random numbers will be generated. Its value can be any % number from $-2^{31}+1$ to $2^{31}-1$, % as long as it is not less than the value of the key \key{first} % and the difference to the value of \key{first} doesn't exceed % $2^{31}-2$.\\ % \textbf{Standard value:} $2^{31}-1$ % \end{macro} % \begin{macro}{seed} % The value of this key is the starting value % for the algorithm generating the random numbers % and must be within the range $1$ to $2^{31}-1$. % If the value is smaller than $1$, % the random number generator will % be initialized with the time, the page number and % the actual line of the file. This key allows % reproduction of the sequences of random numbers.\\ % \textbf{Standard value:} $0$ % \end{macro} % \begin{macro}{quiet} % When using the \texttt{lcg} package it sends some lines of % information to the screen and the \texttt{log}-file: % \begin{itemize} % \setlength{\itemsep}{-3pt} % \item[--] The name of the counter holding the generated random numbers % \item[--] The lower bound of the range of random numbers % \item[--] The upper bound of the range of random numbers % \item[--] The initial value of the random number generator % \end{itemize} % To supress this output this key % can be used. If the value starts with the letter \emph{y}, \emph{Y}, % \emph{j} or \emph{J} % there will be no output whereas words beginning % with the letters \emph{n} or \emph{N} won't supress it.\\ % \textbf{Standard value:} $y$ % \end{macro} % % \section{Example} % % This documentation loaded the package with: % \begin{verbatim} % \usepackage[first=10, last=20]{lcg}\end{verbatim} % The lines % \begin{verbatim} % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand} % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand} % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand}\end{verbatim} % generate these numbers (all between 10 and 20): % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand} % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand} % \rand\arabic{rand} \rand\arabic{rand} \rand\arabic{rand} % % Now the counter \cntr{die} should simulate a die and hold % random numbers from $1$ to $6$. In addition it is demonstrated % how to switch off the output to the screen and to the \texttt{log}-file. % This can achieved with one of the following lines: % \begin{verbatim} % \reinitrand[last=6, counter=die, quiet]\end{verbatim} % \reinitrand[last=6, counter=die] % After that, the numbers % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die} % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die}. % are a product of: % \begin{verbatim} % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die} % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die}\end{verbatim} % As one can see, the key \meta{first} has been reset to $1$. % % The following lines will change the range to $-6$ to $+6$ % without modifying any other option: % \begin{verbatim} \chgrand[first=-6]\end{verbatim} \chgrand[first=-6] % Here the numbers % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die} % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die} % are stored in a user defined counter and brought to paper % by: % \begin{verbatim} % \rand\arabic{die} \rand\arabic{die} \rand{arabic}{die} % \rand\arabic{die} \rand\arabic{die} \rand\arabic{die}\end{verbatim} % % At last, random numbers between $1$ and $12$ will % be generated and stored in the standard counter \cntr{rand}. % The seed will be set to $1234$. There will also be a warning because % the name of the counter is set to \texttt{rand} which was already % defined when calling the package: % \begin{verbatim} \reinitrand[last=12, seed=1234]\end{verbatim} % \reinitrand[last=12, seed=1234] % \begin{verbatim} % \rand\Roman{rand} \rand\Roman{rand} \rand\Roman{rand} \end{verbatim} % These lines produce: \rand\Roman{rand} \rand\Roman{rand} \rand\Roman{rand}. % When using other formats than \texttt{arabic} for printing, % the desired numbers might not appear on the screen % because these formats don't support the full range of $2^{31}-1$. % % % \section{The Linear Congruential Generator} % % The linear congruential generator used produces % a sequence of numbers $I_j$ in the range from % $1$ to $m$ by following rule: % $$ I_{j+1} = a I_j \mod m $$ % where $I_0$ is set to a arbitrary starting value (called ``seed''). % The quality of this generator depends on the choice of the % parameters $a$ and $m$. % Another problem is that when implementing the algorithm as above, % the multiplication might leave the range \LaTeX\ can deal with. % The solution is Schrage's method [\textsc{W.~Press} et~al. % \emph{Numerical Recipies in \texttt{C}}\@. % 2nd edition. Cambridge University Press 1992] which allows % to perform the multiplications without leaving the given range. % This is done by introducing two variables $r$ and $q$: % $$ % m = a q + r \qquad\mbox{with}\qquad % q = \left[m/a\right]\quad\mbox{and}\quad r = m \mod a % $$ % where $[\,\cdot\,]$ denotes the integer part of the argument. % If $z$ is an integer and $0 \leq r < q$ and $0 < z < m-1$, % then the following (in)equalities hold: % \begin{eqnarray*} % & 0 \leq a \cdot (z \mod q) \leq m-1\\ % & 0 \leq \left[m/a\right] \leq m-1\\ % & a z \mod m = \left\{ % \begin{array}{ll} a \cdot (z \mod q ) - % \left[z/q\right] & \mbox{if the term is } \leq 0\\ % a \cdot (z \mod q ) - % \left[z/q\right] + m & \mbox{otherwise} % \end{array}\right. % \end{eqnarray*} % % To exploit the whole possible range and guarantee good performance, % $a$ and $m$ are set as follows: % $a = 7^5 \; = 16807$ and $m = 2^{31}-1 \; = 2147483647$ and % this gives $q=127773$ and $r=2836$. % % % \section{The Code} % % \subsection{Checking for possible conflicts} % % The following lines check if the commands provided by % this package are already defined: % % \begin{macrocode} \@ifundefined{rand}{} {\PackageWarning{lcg}{Command `rand' already defined}} \@ifundefined{r@ndcountername}{} {\PackageWarning{lcg}{Command `r@ndcountername' already defined}} % \end{macrocode} % Checking internal commands: % \begin{macrocode} \@ifundefined{r@nd}{} {\PackageWarning{lcg}{Command `r@nd' already defined}} \@ifundefined{initr@nd}{} {\PackageWarning{lcg}{Command `initr@nd' already defined}} \@ifundefined{cutr@nger@nd}{} {\PackageWarning{lcg}{Command `cutr@nger@nd' already defined}} \@ifundefined{@rderr@nd}{} {\PackageWarning{lcg}{Command `@rderr@nd' already defined}} \@ifundefined{ProcessOptionsWithKVr@nd}{} {\PackageWarning{lcg}{Command `ProcessOptionsWithKVr@nd' already defined}}% \@ifundefined{qui@t}{} {\PackageWarning{lcg}{Command `qui@t' already defined}} \@ifundefined{firstletterr@nd}{} {\PackageWarning{lcg}{Command `firstletterr@nd' already defined}} % \end{macrocode} % Checking the used counters: % \begin{macrocode} \@ifundefined{c@f@rst}{} {\PackageWarning{lcg}{Counter `f@rst' already defined}} \@ifundefined{c@l@st}{} {\PackageWarning{lcg}{Counter `l@st' already defined}} \@ifundefined{c@cr@nd}{} {\PackageWarning{lcg}{Counter `cr@nd' already defined}} \@ifundefined{f@rst}{} {\PackageWarning{lcg}{Existing command `f@rst' conflicts with counter `f@rst'}} \@ifundefined{l@st}{} {\PackageWarning{lcg}{Existing command `l@st' conflicts with counter `l@st'}} \@ifundefined{cr@nd}{} {\PackageWarning{lcg}{Existing command `cr@nd' conflicts with counter `cr@nd'}} % \end{macrocode} % % % \subsection{Macros for (re)initialization} % % \begin{macro}{init} % Set starting values for the parameters and counters % to standard values or according to the provides keys % \begin{macrocode} \def\initr@nd{% \def\r@ndcountername{rand}% \newcount \f@rst \newcount \l@st \newcount \cr@nd \pr@keysr@nd% \ProcessOptionsWithKVr@nd{Init}% \p@stkeysr@nd% \@utputr@nd% } % end of \def\initr@nd % \end{macrocode} % \end{macro} % \begin{macro}{reinit} % Sets the provided keys and resets all other options. % \begin{macrocode} \def\reinitrand{\@ifnextchar[\@reinitr@nd{\@reinitr@nd[]}}% \def\@reinitr@nd[#1]{% \pr@keysr@nd% \setkeys{Init}{#1}% \p@stkeysr@nd% \@utputr@nd% }% end of \def\reinitrand % \end{macrocode} % \end{macro} % % \begin{macro}{chgrand} % Sets the provided keys and doesn't change any other option. % \begin{macrocode} \def\chgrand{\@ifnextchar[\@chgr@nd{\@chgr@nd[]}} \def\@chgr@nd[#1]{% \@tempcnta = \z@ \@tempcntb = \z@ \setkeys{Init}{#1}% \p@stkeysr@nd% \@utputr@nd% } % end of \def\chgrand % \end{macrocode} % \end{macro} % % % \subsection{The keys} % % \begin{macro}{use keys} % The following lines are from the \texttt{geometry} package % written by \textsc{Hideo Umeki} (who borrowed it from the % \texttt{hyperref} package written by \textsc{Sebastian Rahtz}). % It enables the usage of the \meta{key}=\meta{value} scheme of the % keyval package. % % \begin{macrocode} \def\ProcessOptionsWithKVr@nd#1{% \let\@tempa\@empty \@for\CurrentOption:=\@classoptionslist\do{% \@ifundefined{KV@#1@\CurrentOption}% {}{\edef\@tempa{\@tempa,\CurrentOption,}}} \edef\@tempa{% \noexpand\setkeys{#1}{\@tempa\@ptionlist{\@currname.\@currext}}} \@tempa \AtEndOfPackage{\let\@unprocessedoptions\relax}} % \end{macrocode} % \end{macro} % % \begin{macro}{first} % \begin{macrocode} \define@key{Init}{first}[1]{\f@rst = #1} % \end{macrocode} % \end{macro} % \begin{macro}{last} % \begin{macrocode} \define@key{Init}{last}[2147483647]{\l@st = #1} % \end{macrocode} % \end{macro} % \begin{macro}{counter} % \begin{macrocode} \define@key{Init}{counter}[rand]{\def\r@ndcountername{#1}} % \end{macrocode} % \end{macro} % \begin{macro}{seed} % \begin{macrocode} \define@key{Init}{seed}[\z@]{% seed for random number generator \ifnum #1 < \z@% \PackageWarning{lcg}{Seed should be > 0 -- Seed will be initialized with the actual time}% \cr@nd = \z@% \else% \cr@nd = #1 \typeout{Random number generator initialized to #1}% \fi% } % \end{macrocode} % \end{macro} % \begin{macro}{quiet} % \begin{macrocode} \define@key{Init}{quiet}[y]{ \def\qui@t{\expandafter\firstletterr@nd #1\delimiter} \if \qui@t y% nothing to do \else\if\qui@t Y \def\qui@t{y} \else\if\qui@t j \def\qui@t{y} \else\if\qui@t J \def\qui@t{y} \else\if\qui@t n \def\qui@t{n} \else\if\qui@t N \def\qui@t{n} \else \PackageWarning{lcg}{Value of key must be or } \def\qui@t{y} \fi\fi\fi\fi\fi\fi } % \end{macrocode} % \end{macro} % % \subsection{Macros called by other macros} % % \begin{macro}{pr@keys} % The command \cmd{\pr@keysr@nd} is used to define and initialize % all parameters (counters) needed by this package (before % the keys are evaluated). % Random numbers will be generated from $\mathtt{f@rst}$ to % $\mathtt{f@rst} + \mathtt{l@st} - 1$, % \cntr{cr@nd} will hold the random numbers % (full range: $1$ to $2^{31}-1$) and \cntr{rand} % will hold the random numbers (user defined range). % The counters are also initialized to standard values. % If the counter \cntr{cr@nd} equals zero, the seed will be % initialized according to the actual time by the command \cmd{\r@nd}: % % \begin{macrocode} \def\pr@keysr@nd{% \f@rst = \@ne % 1 \l@st = 2147483647 % 2147483647 \cr@nd = \z@ % 0 \@tempcnta = \z@ \@tempcntb = \z@ \def\r@ndcountername{rand}% \def\qui@t{n} } % end of newcommand\def\pr@keysr@nd % \end{macrocode} % \end{macro} % % \begin{macro}{p@stkeys} % The command \cmd{\p@stkeysr@nd} is executed after the % keys are evaluated as last step of the initialization. % The setting of the counter \cntr{l@st} depends on weather % the key \key{last} is set or not. % and the counter (user defined or standard name) is created. % \begin{macrocode} \def\p@stkeysr@nd{% \@rderr@nd% last < first -> swap \cutr@nger@nd% range too big -> cut \@ifundefined{c@\r@ndcountername}{\newcounter{\r@ndcountername}}% {% \PackageWarning{lcg}{Using an already existing counter \r@ndcountername}% }% \setcounter{\r@ndcountername}{0}% } % end of \def\p@stkeysr@nd % \end{macrocode} % \end{macro} % % \begin{macro}{firstletter} % This macro is used to determine the first letter of the value % of the key \key{quiet}. % \begin{macrocode} \def\firstletterr@nd#1#2\delimiter{#1} % \end{macrocode} % \end{macro} % % \begin{macro}{@utput} % Output to log-file/screen % \begin{macrocode} \def\@utputr@nd{% \if \qui@t y% do nothing \else \typeout{Smallest possible random number: \the\f@rst}% \typeout{Largest possible random number: \the\l@st}% \typeout{The pseudo random numbers will be stored in the LaTeX counter `\r@ndcountername'}% \fi } % \end{macrocode} % \end{macro} % % \begin{macro}{@rder} % If the value of the key \key{last} is less than % the value of \key{first}, they will be exchanged. % \begin{macrocode} \def\@rderr@nd{% \ifnum \l@st < \f@rst% \PackageWarning{lcg}{Key `last' less than key `first' -- swapped}% \@tempcnta = \f@rst \f@rst = \l@st \l@st = \@tempcnta \fi% }% end of \def\@rderr@nd % \end{macrocode} % \end{macro} % % \begin{macro}{cutr@nge} % If the given range of random numbers exceeds the possibilities % of \LaTeX\ (the limit is $2^{31}-1$), then the value of the \TeX-counter % \cntr{@tempcnta} will be less than zero and the right border will be adjusted. % \begin{macrocode} \def\cutr@nger@nd{% \ifnum\l@st<\z@\else \@tempcntb = -2147483646 % -2^31 + 2 \@tempcnta = \f@rst \advance \@tempcntb \l@st \multiply \@tempcntb \m@ne \advance \@tempcnta \@tempcntb \ifnum \@tempcnta < \z@% \PackageWarning{lcg}{Range contains too many numbers -- right border reset to largest possible value}% \advance \l@st \@tempcnta \fi% \fi% }% end of \checkr@ange % \end{macrocode} % \end{macro} % % % \subsection{Macros for random number generation} % % \begin{macro}{rand} % The command \cmd{\rand} calls the internal command % \cmd{\r@nd} which stores s random number (full range) % within the counter \cntr{cr@nd}. % If the condition % $$ % \mathtt{cr@nd} \leq (\mathtt{l@st}-\mathtt{f@rst}+1) % \cdot \frac{2^{31}-1}{\mathtt{l@st}-\mathtt{f@rst}+1} % $$ % holds, \cntr{cr@nd} will be transformed % to the given range: % $$ % \mathtt{f@rst}+ \mathtt{cr@nd} - (\mathtt{l@st}-\mathtt{f@rst}+1) % \cdot \frac{\mathtt{cr@nd}}{\mathtt{l@st}-\mathtt{f@rst}+1} % $$ % and the result stored in the corresponding counter % and otherwise \cmd{\rand} calls itself till the condition % is satisfied. It's important % to notice that the result of the division of two integers is % again an integer (the fraction part is lost)! % % \begin{macrocode} \def\rand{% \r@nd% \@tempcnta \@tempcntb \@tempcnta = \f@rst \@tempcntb = \l@st \multiply \@tempcnta \m@ne \advance \@tempcntb \@tempcnta \advance \@tempcntb \@ne %l@st-f@rst+1 \@tempcnta = 2147483647 \divide \@tempcnta \@tempcntb \multiply \@tempcnta \@tempcntb \ifnum \cr@nd > \@tempcnta \rand% \else \setcounter{\r@ndcountername}{\cr@nd}% \@tempcnta = \cr@nd \divide \@tempcnta \@tempcntb \multiply \@tempcnta \@tempcntb \multiply \@tempcnta \m@ne \addtocounter{\r@ndcountername}{\@tempcnta}% \addtocounter{\r@ndcountername}{\f@rst}% \fi } % end of \rand % \end{macrocode} % \end{macro} % % \begin{macro}{r@nd} % The command \cmd{\r@nd} generates pseudo random numbers within % the range $1$ to $2^{31}-1$ Schrage's method and stores them % in the counter \cntr{cr@nd}: % % \begin{macrocode} \def\r@nd{% \ifnum \cr@nd < \@ne% then ... initialize generator \cr@nd = \the\time \advance \cr@nd \inputlineno \multiply \cr@nd \value{page} \advance \cr@nd \the\year \multiply \cr@nd \the\month \multiply \cr@nd \the\day \advance \cr@nd \inputlineno \if \qui@t y% \else \typeout{Random number generator initialized to \the\cr@nd}% \fi \r@nd% \else % else ... generate new number \@tempcnta = \cr@nd \divide \@tempcnta 127773 % \@tempcnta = floor(z/q) \@tempcntb = \@tempcnta % \@tempcntb = floor(z/q) \multiply \@tempcnta -2836 % \@tempcnta = -r*floor(z/q) \multiply \@tempcntb -127773 % \@tempcntb = -q*floor(z/q) \advance \cr@nd \@tempcntb % cr@nd = z mod q \multiply \cr@nd 16807 % cr@nd = a * (z mod q) \advance \cr@nd \@tempcnta % cr@nd = a*z mod m \ifnum \cr@nd < \z@% \advance \cr@nd 2147483647 % cr@nd = (a*z mod m) > 0 \fi \global\cr@nd=\cr@nd % persist the change outside current scope \fi }% end of \r@nd % \end{macrocode} % \end{macro} % % % \subsection{Initialization} % % \begin{macrocode} \initr@nd % initialize the package % \end{macrocode} % % \iffalse % % \fi