Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/unix/volume28/mrandom-3.0/part04

Text File | 1994-05-06 | 58.8 KB | 1,584 lines

Newsgroups: comp.sources.unix
From: [e-mail] (Clark D. Thomborson)
Subject: v28i030: mrandom-3.0 - random number generator with persistent state, Part04/06
References: <[e-mail]>
Sender: [e-mail]
Approved: [e-mail]

Submitted-By: [e-mail] (Clark D. Thomborson)
Posting-Number: Volume 28, Issue 30
Archive-Name: mrandom-3.0/part04

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 4 (of 6)."
# Contents:  doc/mrandom.tex
# Wrapped by [e-mail] on Fri May  6 21:42:56 1994
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'doc/mrandom.tex' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'doc/mrandom.tex'\"
else
echo shar: Extracting \"'doc/mrandom.tex'\" \(56912 characters\)
sed "s/^X//" >'doc/mrandom.tex' <<'END_OF_FILE'
X% mrandom.tex 3.1 5/28/93
X\documentstyle[titlepage,latexinfo]{article}
X\pagestyle{empty}
X
X\begin{document}
X\begin{center}
X\vspace{1in}
X{\large
XMassachusetts Institute of Technology\\
X}
X77 Massachusetts Avenue \\
XCambridge, MA 02139 \\
X\end{center}
X
X\vspace{1in}
X\begin{center}
X{\Large\bf
Xmrandom 3.0 User's Manual}
X\end{center}
X\vskip .1 in
X\begin{center}
Xby
X\end{center}
X\vskip .1in
X\begin{center}
X{\large \em Robert Plotkin}
X\vskip .5 in
XDepartment of Electrical Engineering and Computer Science
X\vskip 3.0 in
XMay 1993
X\end{center}
X
X\clearpage
X\pagestyle{headings}
X\pagenumbering{roman}
X\tableofcontents
X\clearpage
X\listoffigures
X\clearpage
X\pagenumbering{arabic}
X
X\section{Introduction}
X
XThe mrandom package contains a library of routines for using random
Xnumber generators (RNGs) in C in the Unix 4.3bsd environment.  This
XUser's Manual is designed as a guide for programmers who wish to use the
Xmrandom package within their own programs.  The current version of
Xmrandom (version 3.0) is a major rewrite of mrandom version 2.1,
Xreleased by Clark Thomborson in July 1992 (available via anonymous
X\code{ftp} from \code{theory.lcs.mit.edu}).  The package now provides:
X
X\begin{itemize}
X\item A standardized interface to many simultaneously-active RNGs,
X\item A standardized, and unbiased, method for generating random
Xintegers in the range 0..\code{m}-1,
X\item A standardized method for generating floating point numbers
Xuniformly distributed in [0.0, 1.0),
X\item Two standardized methods for generating pseudorandom bit
Xstreams,
X\item Time-efficient vectorized calls, returning multiple uniform
Xvariates,
X\item Buffered and unbuffered calls for efficient generation of
Xpseudorandom generates in both large and small quantities,
X\item The ability to ``split'' RNGs to produce parallel output streams
Xusing the ``leapfrog'' method,
X\item A shorthand notation for completely specifying the
Xalgorithm and current state of an RNG, in an 80-character human-
Xreadable ASCII string,
X\item A method for reconstructing an RNG state from its shorthand
Xnotation,
X\item A standardized method for adding new RNGs to the package,
Xand
X\item A file-I/O interface allowing fast saves and restarts of RNG state
Xvectors.
X\end{itemize}
X
XYou can obtain the complete distribution of mrandom by anonymous ftp
Xfrom \code{theory.lcs.mit.edu}.  Take the file \file{mrandom.tar.Z} from
Xthe directory \code{/pub/cthombor/Mrandom/V3.0}.  The distribution
Xcontains all source code, instructions, and this manual.
X
XIn addition, the mrandom package includes an unsupported set of routines
Xfor testing the statistical properties of the RNGs in the package.  The
Xroutines are packaged in an executable called \code{mrtest}.
XInformation about \code{mrtest} is available in the \code{doc/mrtest}
Xdirectory of the distribution.  Although \code{mrtest} is included in
Xthe current distribution, it is not supported.
X
XQuestions, comments, bug reports, etc. should be sent to Clark
XThomborson at \code{[e-mail]}.
X
X\section{Files in the Distribution Directory}
XThe mrandom source code distribution includes the following
Xfiles:
X
X\begin{description}
X\item[makefile] The makefile for creating the \code{mrtest} program and the \code{mrandom.a}
Xlibrary.
X\item[README] General information about the mrandom package, including
Xchanges to the last version.
X\item[mrandom.c mrandom.h] The source and header files for the main
Xmrandom module.
X\item[bentley.c bentley.h] The source and header files for Bentley's
X  version of the generator described in Knuth Vol 2, Section 3.6.
X\item[pcrand.c pcrand.h] The source and header files for the Portable Combined
XRNG.
X\item[ran0.c ran0.h ran1.c ran1.h ran2.c ran2.h] The source and header
Xfiles for Press and Teukolsky's ran0, ran1, and ran2.
X\item[ultra.c ultra.h] The source and header files for Marsaglia's Ultra
Xgenerator.
X\item[mrtest.c] The mrtest source file.
X\item[xsq.c xsq.h] Code used by mrtest.
X\item[rngs.h] The header file for the UNIX RNGs and the trivial RNG.
X\item[newrng.c newrng.h] Source and header file templates for a new RNG.
X\item[mrandom.3] The man pages for mrandom.
X\item[mrtest.1] The man pages for mrtest.
X\item[script] A test script for mrtest.
X\item[mrandom.tex] The latex source for this manual.
X\item[latexinfo.sty] The style file needed to latex this manual.
X\item[mrandom.txt] Plain ASCII text version of this manual.
X\item[mrandom.ps] PostScript version of this manual.
X\end{description}
X
X\section{Installing mrandom}
X\label{sec:install}
XPreparing the mrandom package for use by other programs is
Xsimple.  Merely position yourself in the directory which contains the
Xmrandom files and type:\\
X\begin{example}
Xmake all\\
X\end{example}
XThis will compile all necessary source files and create the
X\code{mrandom.a} library, as well as the \code{mrtest} binary executable.
X
XYou can also make either the \code{mrandom.a} library or the \code{mrtest}
Xexecutable by typing:\\
X\begin{example}
Xmake mrandom.a\\
X\end{example}
Xor\\
X\begin{example}
Xmake mrtest\\
X\end{example}
X\noindent
Xrespectively.
X
XTo save disk space, various intermediate object files can be removed
Xwith:\\
X\begin{example}
Xmake clean\\
X\end{example}
XThe system can be restored to its original state with:\\
X\begin{example}
Xmake realclean\\
X\end{example}
XThe mrandom package is written in ANSI C, and should be
Xeasily portable to any UNIX-based system supporting a C language
Xcompiler.  However, when compiling on a new system, confirm that
Xthe \code{long} type is represented in 32 bits.
X
X\section{What is an RNG?}
X
XWithin the mrandom package, an RNG is represented by the \code{RNGdata}
Xstructure.  An RNG has several abstract characteristics which are
Xdescribed in this section.  For a more detailed description of the
Xrepresentation of the \code{RNGdata} structure in C, see
XAppendix \ref{app:rngdata}.
X
XAssociated with every RNG is:
X\begin{itemize}
X\item an algorithm number, which determines which algorithm the RNG
Xuses to produce pseudorandom generates.  For descriptions of the
Xalgorithms which are currently installed in the package, see Appendix
X\ref{app:installedrngs}.
X\item an ``mrandom algorithm number,'' which determines which
Xalgorithm the \code{mrandomrv} routine will use to produce
Xrestricted-range integers when called with the RNG.  (See the
Xdescription of \code{mrandomrv} in Section \ref{sec:mrandomrv} for more
Xinformation.)
X\item a state vector, which contains the current state of the RNG.
X\item the size of the state vector.
X\item a seed vector, which contains the seeds which were used to
Xseed the RNG.
X\item the size of the seed vector.
X\item a count of the number of times the RNG has been called since
Xit was initialized.
X\item two buffers
X\begin{itemize}
X\item a bit buffer for bit generates
X\item a main buffer for all other generates.
X\end{itemize}
XSee Section \ref{sec:genproc} for a description of how the two buffers work.
X\item a split value, which determines how many generates to skip
Xbetween values which are returned from the RNG.  For a detailed
Xdescription of the split value, see Section \ref{sec:examandmodify}.
X\item a string containing the human-readable name of the RNG.
X\item the range of the RNG, such that the RNG is capable of
Xproducing integers with a maximum value of range-1.
X\end{itemize}
X
X\section{Using the mrandom package}
X
X\subsection{Overview of the Library}
XThis section describes the mrandom library.  The procedures
Xin the library are gathered into the following groups:
X\begin{itemize}
X\item functions for initializing and de-initializing (killing)
XRNGs
X\item functions for returning generates from RNGs
X\item functions for saving and restarting RNGs
X\item a function for seeding RNGs
X\item a function for checking the integrity of RNG state vectors
X\item a function for producing a human-readable ASCII description
Xof an RNG
X\item functions for examining and modifying characteristics of RNGs
X\end{itemize}
X
X\subsection{Return codes from mrandom routines}
XMost mrandom routines follow one of two conventions for return
Xvalues.
X
X\noindent
XFor those routines which return pointers to an \code{RNGdata}
Xstructure:
X\begin{itemize}
X\item A valid pointer to an \code{RNGdata} structure is returned upon
Xsuccess.
X\item A null pointer is returned upon failure.
X\end{itemize}
XFor routines which produce vectors of pseudorandom generates:
X\begin{itemize}
X\item The first cell of the vector is returned upon success.
X\item The program aborts upon error.
X\end{itemize}
XFor all other routines:
X\begin{itemize}
X\item A 0 or -1 is returned upon failure.
X\end{itemize}
XDetails are provided in the description of the mrandom library
Xin Section \ref{sec:library}.
X
X\subsection{Linking}
XIn order to use the mrandom library of routines in your programs
Xyou must:
X\begin{itemize}
X\item Link the \code{mrandom.a} library with your program.  This will
Xtypically involve merely including the library on your compiler's
Xcommand line, such as:\\
X\begin{example}
Xcc myprog.c mrandom.a\\
X\end{example}
XSince mrandom uses some UNIX mathematical functions, you may also need
Xto link a math library with your program, as in the following:\\
X\begin{example}
Xcc myprog.c mrandom.a -lm\\
X\end{example}
XCheck the documentation for your C compiler for details.
X\item Include the following line at the top of your source file:
X\begin{example}
X#include "mrandom.h"
X\end{example}
X\end{itemize}
X
X\subsection{The mrandom library}
X\label{sec:library}
X
X\subsubsection{Initialization and De-Initialization}
X\label{sec:initkill}
X
XIn order to use an RNG, it must first be initialized.  This
Xis accomplished by first declaring a pointer to an \code{RNGdata}
Xstructure, and then calling \code{init_rng}, which allocates memory for
Xthe RNG and readies it for use by the other routines in the
Xpackage.\\
X
X\begin{example}
X    RNGdata *init_rng(alg,mrandom_alg,seed,count1,count2,bufsize)
X    long alg;
X    long mrandom_alg;
X    long *seed;
X    long count1, count2;
X    long bufsize;
X
X    int kill_rng(rng)
X    RNGdata *rng;\\
X\end{example}
X
X\code{init_rng} returns a pointer to an initialized RNG.  A pointer
Xreturned by \code{init_rng} is valid for use by all other mrandom routines.
X
X\code{alg} is the number of the algorithm to be used by the RNG.  (See
XAppendix \ref{app:installedrngs}.)
X
X\code{mrandom_alg} is the algorithm to be used by \code{mrandomrv} when
Xcalled with the RNG.  (See Section \ref{sec:mrandomrv}.)
X
X\code{seed} is a pointer to a seed vector to be used to seed the RNG.
X(See Section \ref{sec:seedproc}.)
X
X\code{count1} and \code{count2} determine the number of initial values
Xto be generated by the RNG and then discarded, according to the formula:\\
X
Xnumber to discard = \code{count1 + BILLION*count2},\\
X
X where \code{BILLION} is defined in \file{mrandom.h} as the decimal
Xconstant 1000000000.
X
X\code{bufsize} is the size of the RNG's main buffer.  A non-positive value of
X\code{bufsize} will be interpreted as a value of 1.  (See Section
X\ref{sec:genproc} for more information on buffering.)
X
X\code{kill_rng} destroys the RNG, making it invalid for use.  This
Xprocedure de-allocates the space used by the RNG, and should therefore
Xbe used to kill RNGs which will no longer be used.
X
XDo {\em not} use an \code{RNGdata} pointer which points to an active RNG
Xto store the return value of \code{init_rng}.  In order to initialize an
XRNG, you should either:
X\begin{itemize}
X\item Declare a new \code{RNGdata} pointer, and then use it to store the
Xreturn value of \code{init_rng}, as shown in Figure \ref{fig:properinit}.
X
X\begin{figure}
X\begin{example}
XRNGdata *rng;
Xlong seed[1];
X
Xrng=init_rng(2, 0, seed, 10000, 0, 8192);
X\end{example}
X\caption{Proper initialization of an RNG}
X\label{fig:properinit}
X\end{figure}
X
X\item Use \code{kill_rng} to de-initialize an \code{RNGdata} pointer
Xwhich points to an active RNG, and then use that pointer to store to the
Xreturn value of \code{init_rng}, as shown in Figure
X\ref{fig:properreinit}.  Figure \ref{fig:improperreinit} shows how an
XRNG should {\em not} be re-initialized.
X\begin{figure}
X\begin{example}
XRNGdata *myrng;
Xlong seed[1];
X
Xseed[0]=12345;
Xmyrng=init_rng(2, 0, seed, 10000, 0, 8192);
Xkill_rng(myrng);
Xmyrng=init_rng(3, 0, seed, 5000, 0, 2048);
X\end{example}
X\caption{Proper re-initialization of an RNG}
X\label{fig:properreinit}
X\end{figure}
X\end{itemize}
X
X\begin{figure}
X\begin{example}
XRNGdata *myrng;
Xlong seed[1];
X
Xseed[0]=12345;
Xmyrng=init_rng(2, 0, seed, 10000, 0, 8192);
Xmyrng=init_rng(3, 0, seed, 5000, 0, 2048);
X\end{example}
X\caption{Improper re-initialization of an RNG}
X\label{fig:improperreinit}
X\end{figure}
X
X\subsubsection{Procedures for Generating Pseudorandom Numbers}
X\label{sec:genproc}
XAn initialized RNG can be used to generate pseudorandom
Xnumbers by using a variety of routines described in this section.
X
XRoutines are provided for producing generates of four types:
X\begin{tex}
X\begin{itemize}
X\item{double precision floating point generates in the range [0,1)}
X\item{single precision floating point generates in the range [0,1)}
X\item{long integer generates in the range $0..r-1$, where r is the range
Xof the RNG being used to produce generates}
X\item{long integer generates in the range $0..\code{m}-1$, for any $1
X\leq \code{m} < \code{range\_rng(rng)}$}
X\end{itemize}
X\end{tex}
X
XNote that although both single and double precision floats can be
Xreturned by the generate-producing routines, the actual precision of the
Xgenerates produced is determined by the precision of the underlying
Xgenerator being used.  In other words, the difference between routines
Xwhich return generates of type \code{double} and those which return
Xgenerates of type \code{float} is merely in the ``packaging'' of the
Xgenerates, not in the precision they provide.  Information about the
Xprecision of the RNGs currently installed in the package is in Appendix
X\ref{app:installedrngs}; such information can also be obtained at
Xrun-time through the \code{range_rng} routine (see Section
X\ref{sec:examandmodify}).  The current version of the package only
Xsupports RNGs with precisions of no more than 32 bits.
X
XBoth buffered and unbuffered routines are provided.  Unbuffered routines
Xcall the underlying RNG only as many times as are needed to produce the
Xrequested number of generates, while buffered routines maintain buffers
Xof generates, so that generates may be produced efficiently even when
Xrequested in small quantities.  Roughly, buffered routines are
Xpreferable when generates are requested one at a time or in small
Xquantities, while unbuffered routines are preferable when generates are
Xrequested in large quantities.  Some other differences between buffered
Xand unbuffered routines are discussed later in this section.  The size
Xof the buffer used by an RNG is determined at the time of the RNG's
Xinitialization; effective buffer sizes will vary from application to
Xapplication.
X
XThe name of a routine denotes the type of the value which the routine
Xreturns and whether the routine is buffered or unbuffered. The first
Xletter of a routine denotes the type of value which it returns: ``d''
Xfor double precision and ``f'' for single precision floating point in
Xthe range [0,1); ``l'' for long integer in the range
X0..(\code{range_rng(rng)}-1), and ``b'' for bit (either a 0 or a 1).  If
Xthe second letter of the routine's name is an ``x'', then the routine is
Xunbuffered.  Otherwise, the routine is buffered.
X
XFor convenience in user programming, we also provide a number of macros
Xthat supply default parameter values.  The last two letters of all our
Xfundamental routines is ``rv''.  This means that they must be provided
Xwith both a pointer to an \code{RNGdata} structure and a vector to fill
Xwith generates from the RNG.  Macros whose names do not contain an ``r''
Xhave the \code{RNGdata} pointer omitted from their parameter list; they
Xuse the most-recently initialized or restarted RNG to produce generates.
XMacros whose names do not contain a ``v'' have the vector and number of
Xgenerates omitted from their parameter list; they produce and return a
Xsingle generate.
X
XAll generating routines abort with a message to \code{stderr} if called
Xwith an invalid \code{RNGdata} pointer.\\
X
X\noindent
X{\bf Buffering\\}
X
XThe operation of the buffered routines and their interaction with the
Xunbuffered routines requires some elaboration.  Each RNG maintains two
Xseparate buffers: one for buffering bit values (the ``bit buffer''), and
Xone for buffering all other values (the ``main buffer'').  The size of
Xthe main buffer of an RNG is determined at the time of the RNG's
Xinitialization, while the size of the bit buffer is currently fixed at
X32 bits.
X
XConsider a freshly-initialized RNG with a main buffer size of 1000.  A
Xrequest is made for a single generate of type \code{long}.  The RNG's
Xbuffer gets filled with 1000 generates, and the first such generate is
Xreturned to the user.  So the buffer now contains 999 generates.  If
Xanother generate of type \code{long}, \code{double}, or \code{float}, is
Xrequested, a generate will be pulled from the buffer and returned to the
Xuser after being converted to the proper type.  If the user continues to
Xrequest generates in this way and the main buffer becomes depleted, it
Xwill be filled again with 1000 generates, and so on.
X
XThe unbuffered routines do not interfere with either of the RNG's
Xbuffers.  Again, consider our RNG, with its buffer filled with 1000
Xgenerates.  The user now makes a request for a single unbuffered
Xgenerate.  The underlying RNG will then be called once, returning a
Xsingle generate, leaving our buffer of 1000 generates untouched, and
Xstill ready to be accessed by the buffered routines.  If, in a
Xparticular application, it is necessary to always use consecutive
Xgenerates from an RNG, then that RNG should always be called {\em
Xeither} with buffered or unbuffered routines, but not with a combination
Xof both.
X
XThe bit buffer of an RNG operates similarly to the main buffer, with one
Xkey difference: the bit buffer is filled by sequentially retrieving
Xgenerates from the main buffer.  Once again, consider our RNG, with its
Xbuffer filled with 1000 generates, and with its bit buffer empty.  A
Xsingle bit is then requested.  Thirty-two generates will be pulled from
Xthe main buffer, transformed into thirty-two one-bit 0-1 values, then
Xstored in the bit buffer.  (For users who are more concerned with speed
Xthan accuracy, we also provide a ``fast'' bit-buffer call, in which a
Xsingle 32-bit generate from the main buffer is transformed into
Xthirty-two 0-1 variates.  See the descriptions of \code{bxrandom_f} and
X\code{brandom_f}, below.)\\
X
X\pagebreak
X\noindent
X{\bf Unbuffered and buffered calling procedures\\}
X
X\begin{example}
X    double dxrandomrv(rng, n, v)
X    double drandomrv(rng, n, v)
X    RNGdata *rng;
X    long n;
X    double v[];
X
X    float fxrandomrv(rng, n, v)
X    float frandomrv(rng, n, v)
X    RNGdata *rng;
X    long n;
X    float v[];
X
X    long lxrandomrv(rng, n, v)
X    long lrandomrv(rng, n, v)
X    RNGdata *rng;
X    long n;
X    long v[];
X
X    int bxrandomrv(rng, n, v)
X    int brandomrv(rng, n, v)
X    RNGdata *rng;
X    long n;
X    int v[];
X
X    int bxrandomrv_f(rng, n, v)
X    int brandomrv_f(rng, n, v)
X    RNGdata *rng;
X    long n;
X    double v[];\\
X\end{example}
X
XThese routines fill the vector \code{v} with \code{n} generates from
X\code{rng}, and return the first generate produced (i.e. \code{v[0]}).
X
XIf \code{rng} is a null pointer, then the most-recently initialized or
Xrestarted RNG is used to produce generates.  If \code{n} is 0, then the
X\code{v} parameter need not be provided, and a single generate is
Xproduced and returned.
X
X\code{bxrandomrv} uses one generate from \code{rng} to generate each
Xbit.  This routine is slower than \code{bxrandomrv_f}, but returns bits
Xof higher quality.
X
X\begin{tex}
X\code{bxrandomrv\_f} uses each generate from \code{rng} to produce 32
Xbits.  Therefore, requests for bits in other than multiples of 32 will
Xresult in bits from the stream being ``lost'' between calls.  The
Xroutine returns -1 if it is called with an RNG whose range is not $2^{32}$.
XThis routine is faster than \code{bxrandomrv}, but we do not recommend
Xits use, since we know of no one who has rigorously tested such a bit
Xstream.  We gain confidence in our slower \code{bxrandomrv} bit stream,
Xin comparison, every time the underlying generator passes a test
Xsensitive to correlations in the leading digit of its floating point
Xoutput, or to the most significant bit of its fixed point output.
X\end{tex}
X
X\code{brandomrv_f}, the buffered version of \code{bxrandomrv_f}, does not
Xexhibit the same property of ``losing bits'' as does \code{bxrandomrv_f}, since
Xbits which are not used in one call to \code{brandomrv_f} are stored in the bit
Xbuffer and are available for use upon future calls.\\
X
X\begin{example}
X    int flush_rng(rng)
X    RNGdata *rng;\\
X\end{example}
X
X    Flushes both of the RNG's buffers.\\
X
X\noindent
X{\bf Procedure for generating integers in a restricted range\\}
X\label{sec:mrandomrv}
X
X\begin{example}
X    long mrandomrv(rng, m, n, v)
X    RNGdata *rng;
X    long m,n,v[];\\
X\end{example}
X
X\begin{tex}
X\code{mrandomrv} fills the vector \code{v} with \code{n} generates in
Xthe range $0..\code{m}-1$ using \code{rng}, where $1 \leq \code{m} \leq
X\code{range\_rng(rng)}$.  If $\code{range\_rng(rng)} < \code{m}$, the
Xprogram aborts with an error.
X\end{tex}
X
XThe algorithm used by \code{mrandomrv} to fill \code{v} is set by
X\code{init_rng} or by \code{mralg_rng}.  (See Section \ref{sec:initkill}
Xand Section \ref{sec:examandmodify}.)
X
X\begin{tex}
XAlgorithm 0 is Thomborson's unbiased method, which produces unbiased
Xlong integers in the range [0..\code{m}).  The algorithm discards any
Xoutputs from \code{rng} which are larger than $r-(r \bmod \code{m})$, where
Xr is equal to \code{range\_rng(rng)}.  At worst, this code will discard
X(on long-term average) at most one value of r for every one that is
Xuseful.  This worst case is only encountered for extremely large
X\code{m}; for fixed and moderate \code{m}, this code will rarely discard a
Xvalue, and thus will run essentially as fast as algorithm 1.  When the
Xvalue of \code{m} changes on each call to \code{mrandom}, however, this
Xcode is slower than algorithm 1, due to the necessity of recomputing
X$r-(r \bmod \code{m})$.
X
XThe program aborts with an error message to \code{stderr} if \code{rng}
Xis behaving so non-randomly that Algorithm 0 must make an excessive
Xnumber of calls to \code{rng} in order to produce the requested number of
Xgenerates.
X
XThe program aborts with an error to \code{stderr} if \code{mrandomrv} is
Xasked to use Algorithm 0 with a value of \code{m} for which $\code{m} >
X\code{range\_rng(rng)}$. \\
X
X
XAlgorithm 1 is the standard \code{(long)(m*dxrandomr(rng))}.  This
Xalgorithm may be biased: for large \code{m}, some results may be be more
Xlikely than others.  The bias is $\frac{r \bmod \code{m}}{\code{m}}$, which is
Xupper-bounded by 0.1\% if \code{m} is less than a million and the range
Xr of \code{rng} is at least a billion.
X
XWe do not support, and indeed we actively discourage, generating
Xrestricted-range integers with \code{lrandomr(rng)\%m}.  Many RNGs have
Xpoor behavior under this transformation, most noticeably when \code{m}
Xis a power of 2.  When \code{m} is not a power of 2, fixed-point
Xdivision required by an ``\code{\%}'' operation is time-consuming on many
Xworkstations.\\
X\end{tex}
X
X\noindent
X{\bf NOTES}
X
X\begin{tex}
XThe \code{mrandomrv} procedure is capable of generating long integers in
Xthe full range of any RNG for which $1 \leq \code{range\_rng(rng)} \leq
X2^{32}$.  In order to accomplish this, with the parameter \code{m} a
Xsigned long integer, the following mapping is used:
X
X\begin{tabbing}
XRange(\code{mrandom(m)}) = \=    $0..\code{m}-1$ \hspace{.5in} \= if $1 \leq
X\code{m} < 2^{31}$\\
X\> $0.. 2^{32}-1$ \> if $\code{m}=0$\\
X\> $0..(2^{31}-\code{m}-1)$ \> if $-2^{31} \leq \code{m} < 0$
X\end{tabbing}
X\end{tex}
X
XMacros are defined for easy calling of \code{mrandomrv} with various
Xdefault parameters.  See Section \ref{sec:genproc} for the naming
Xconventions followed by the macros.
X
X\subsubsection{Saving and restarting RNGs}
X\label{sec:saverestart}
X
XRNGs may be saved to disk files in a human-readable ASCII format and
Xlater restarted.  RNG buffers are not saved, and therefore all restarted
XRNGs have empty buffers, and any data remaining in an RNG's buffer at
Xthe time of its state-save will {\em not} be reconstructed.\\
X
X\begin{example}
X    int save_rng(rng, filename)
X    RNGdata *rng;
X    char *filename;
X
X    RNGdata *restart_rng(filename)
X    char *filename;\\
X\end{example}
X
X\code{save_rng} saves \code{rng} to the ASCII file named \code{filename}.
X
X\code{restart_rng} restarts an RNG from a previously saved statefile.
XThe restarted RNG will begin where the saved RNG ``left off.''  As with
X\code{init_rng}, the \code{RNGdata} pointer used to store the restarted
XRNG {\em must} be either a freshly declared pointer or a pointer to a
Xfreshly killed RNG (see Section \ref{sec:initkill}).
X
XRNGs may store their state and seed vectors in any of a number of
Xformats, and this is reflected in the format of the state file.  Figure
X\ref{fig:samplestatefile1} shows a sample state file of an RNG using
Xthe Knuth/Bentley lagged-Fibonnacci generator prand (see Appendix
X\ref{app:installedrngs}), which stores its state and seeds as 32-bit
X\code{long int}s.  Figure \ref{fig:samplestatefile2} shows a sample
Xstate file of an RNG using 4.3bsd \code{nrand48}, which stores its state
Xand seeds as 16-bit \code{int}s.
X
X\begin{figure}
X\begin{example}
XRNG statefile for algorithm 2, (Knuth/Bentley prand: lagged Fibbonacci)
XBuffer size = 1024 bytes
XInitial seed table =
X   00000927
XNumber of calls to underlying RNG after seeding = 0 billion + 2000
XNext value in this pseudorandom sequence = 0b64d0ea
XThis RNG returns every 1 generates
XThis RNG uses mrandom algorithm 0
XRNG state table =
X   0911c27a 10641ca0 2ba00807 1aabed0a
X   273ff367 1ab88564 2ae76a9e 2a7e6bc0
X   35c7568e 201b6b04 3ad90695 303208b2
X   1e718896 054c9886 00e8c93f 130a41cb
X   11de97bf 0da54e15 2f4fcca0 0ebb1f70
X   01c195c3 3283980e 37dee108 0893a89b
X   326849b0 167bb45e 19cc9765 33d97b51
X   36b425d1 35704e34 29a638ca 280a086f
X   11dfa5d6 14dcbcc4 2610bdf4 02534109
X   2817daf4 0bcf76ab 19b0a07d 0eebf7f6
X   113c003e 31b996b0 12bab234 05eddb36
X   1ed71381 377742a3 3878e079 2668c922
X   22cc8033 22368c85 18e960ea 2002b06f
X   22ff23e8 251187dc 340c3dcd 00000023
X   00000004
X\end{example}
X\caption{A sample RNG state file for the Knuth/Bentley prand().}
X\label{fig:samplestatefile1}
X\end{figure}
X
X\begin{figure}
X\begin{example}
XRNG statefile for algorithm 4, (4.3bsd nrand48.c: 48-bit multiplicative)
XBuffer size = 8192 bytes
XInitial seed table =
X   0096   b43f   0034   bf15
X
XNumber of calls to underlying RNG after seeding = 0 billion + 11000
XNext value in this pseudorandom sequence = 04a3689e
XThis RNG returns every 1 generates
XThis RNG uses mrandom algorithm 0
XRNG state table =
X   07c5   8f2d   0000   a7d6
X\end{example}
X\caption{A sample RNG state table for {\tt nrand48}}
X\label{fig:samplestatefile2}
X\end{figure}
X
XA few examples of how to save and restart RNGs are displayed in Figure
X\ref{fig:saverestart}.
X
X\begin{figure}
X\begin{example}
X/* Proper way to re-initialize an active RNG */
Xmrandom(rng,10,n,v);
Xkill_rng(rng);
Xrng=restart_rng("mystatefile");
X
X/* Proper way to restart an inactive RNG */
XRNGdata *rng;
Xrng=restart_rng("mystatefile");
X
X/* Improper way to restart an active RNG */
Xmrandom(rng,10,n,v);
Xrng=restart_rng("mystatefile");
X\end{example}
X\caption{Examples of saving and restarting RNGs}
X\label{fig:saverestart}
X\end{figure}
X
X\subsubsection{Seeding}
X\label{sec:seedproc}
X
XEach RNG is initially seeded during initialization by
X\code{init_rng}.  An RNG may also be reseeded at any time after
Xinitialization.\\
X
X\begin{example}
X    void seed_rng(rng,seed)
X    RNGdata *rng;
X    long *seed;\\
X\end{example}
X
X\code{seed_rng} seeds \code{rng} with the seed table pointed to by \code{seed}.
XThe RNG's counter is reset to 0 and its buffers are flushed.
X
X\subsubsection{Checking RNG integrity}
X    An RNG can be checked to see if it has been corrupted or is
Xotherwise not in proper condition for use.\\
X
X\begin{example}
X    int check_rng(rng);
X    RNGdata *rng;\\
X\end{example}
X
X\code{check_rng} checks the integrity of the RNG, in order to determine
Xwhether it can be used by the other mrandom library routines.
X
X\subsubsection{Obtaining a human-readable description of the RNG}
X
X\begin{example}
X    char *describe_rng(rng,rngid)
X    RNGdata *rng;
X    char rngid[RNGIDSTRLEN];\\
X\end{example}
X
X\code{describe_rng} places a human-readable description of \code{rng} in
Xthe string \code{rngid}.  The string has the following format:\\
X
X\begin{example}
XRNG state identifier is (alg, mralg: seed1, seed2; count1,count2;
Xbufsize, split)\\
X\end{example}
X
Xwhere
X
X\begin{itemize}
X\item \code{alg} is the number of the algorithm used by \code{rng} to generate
Xpseudorandom numbers.  (See Appendix \ref{app:installedrngs}.)
X\item \code{mralg} is the number of the algorithm used by
X\code{mrandomrv} when called with \code{rng}.  (See Section
X\ref{sec:mrandomrv}.)
X\item \code{seed1} and \code{seed2} are the first and second entries in
Xt\code{rng}'s seed table.  If \code{rng}'s seed table has more than two
Xentries, only the first two are included in its description.  (See
XSection \ref{sec:seedproc}.)
X\item \code{count1} and \code{count2} represent \code{rng}'s counter.
X(See Section \ref{sec:initkill}.)
X\item \code{bufsize} is the number of entries in \code{rng}'s buffer.
X(See Section \ref{sec:genproc}.)
X\item \code{split} is \code{rng}'s current split value.  (See Section
X\ref{sec:examandmodify}.)
X\end{itemize}
X
X\code{describe_rng} exits with a message to \code{stderr} if called
Xwith an invalid \code{RNGdata} pointer.
X
X\subsubsection{Procedures for examining and modifying RNG parameters}
X\label{sec:examandmodify}
X
XProcedures are available for examining and modifying an RNG's parameters
Xonce it has been initialized.\\
X
X\begin{example}
X    int mralg_rng(rng, new_value)
X    RNGdata *rng;
X    long new_value;
X
X    int split_rng(rng, new_value)
X    RNGdata *rng;
X    long new_value;
X
X    double range_rng(rng)
X    RNGdata *rng;\\
X\end{example}
X
X\code{mralg_rng} sets \code{rng}'s mrandom algorithm number (See Section
X\ref{sec:mrandomrv} for information on mrandom algorithm numbers).  It
Xreturns 0 if \code{new_value} is an invalid value.
X
X\code{split_rng} sets the split value of \code{rng}.  It returns 0 if
X\code{new_value} < 0.  An RNG's split value is set to \code{SPLIT_DEF}
Xupon initialization.  \code{SPLIT_DEF} is \code{#define}d in
X\file{mrandom.h}, and currently has a value of 0.
X
XThe function of the split value is to simulate one ``branch'' of a
Xgenerator which has been ``split'' into two or more generators.  This is
Xbest illustrated with an example.  Consider an (apparently non-random)
XRNG which returns the raw sequence:
X\begin{center}
X0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...\\
X\end{center}
XThe split value indicates how many elements of the sequence to skip
Xbetween generates.  For example, if our sample RNG were given a split
Xvalue of 1 immediately after initialization, it would then return the following
Xsequence:
X\begin{center}
X0 2 4 6 8 10 ...\\
X\end{center}
XA split value of 2 after initialization would produce:
X\begin{center}
X0 3 6 9 12 15 ...\\
X\end{center}
XAn RNG may be split at any time after its initialization.  So, for
Xexample, our sample RNG might be initialized and then made to generate
Xthe following values:
X\begin{center}
X0 1 2 3 4 5\\
X\end{center}
Xbefore being split with a split value of 3, producing the following
Xgenerates:
X\begin{center}
X6 10 14 18 22 ...\\
X\end{center}
XSplitting can be used to create several ``leapfrogged'' RNGs from one
XRNG, as shown in Figure \ref{fig:leapfrog}.
X
X\begin{figure}
X\begin{example}
XRNGdata *rngs[10];
Xlong seed;
Xint i;
X
Xseed=12345;
Xfor (i=0; i<10; i++) \{
X  /* RNG #i gets cycled i times */
X  rng[i]=init_rng(2,0,&seed,i,0,1024);
X  split(rng[i],9);
X\}
X\end{example}
X\caption{Creating ``leapfrogged'' RNGs}
X\label{fig:leapfrog}
X\end{figure}
X
XThis operation may be useful in parallel codes, as in testing an RNG for
Xlong-range correlations.  Unfortunately, our current implementation is
Xinefficient for leapfrogging large numbers of RNGs.  A more efficient
Xmethod may be included in a future version of mrandom.
X
XThe split value affects all of the pseudorandom number generating
Xroutines (See Section \ref{sec:genproc}).
X
X\code{range_rng} returns the range of \code{rng}.\\
X
X\noindent
X{\bf NOTES}
X
XThese procedures exit with a message to \code{stderr} if
X\code{rng} does not point to a valid \code{RNGdata} structure.
X
X\section{Adding new RNGs to the Package}
X
XThis section is designed for the programmer who wishes to add new RNGs
Xto the mrandom package.  The section first describes the routines which
Xmust be provided by the programmer to serve as an interface between the
XRNG and the mrandom package.  It then describes the RNG parameters which
Xmust be defined in a header file for the RNG, and how these parameters
Xare to be incorporated into the code for mrandom itself.  Finally, it
Xdescribes how to remake the mrandom package after adding or modifying
XRNGs.  Appendix \ref{app:installedrngs} contains descriptions of the ten
XRNGs installed in the current version of the package.
X
X\subsection{Routines Provided by the Programmer}
X\label{sec:progroutines}
X\subsubsection{Introduction}
X
XThis section describes routines which must be provided by each RNG in
Xthe package.
X
XThe routines provided by the programmer must manipulate an
X\code{RNGdata} structure.  In order to facilitate this, two macros are
Xavailable for accessing an RNG's state and seed vectors:
X\begin{itemize}
X\item \code{RNGstate} refers to the RNG's state vector.
X\item \code{RNGseed} refers to the RNG's seed vector.
X\end{itemize}
XThese vectors are one-dimensional C arrays, e.g.
X\code{RNGstate[0]} is the first element in the RNG's state vector,
X\code{RNGstate[1]} is the second element, etc.  In order to make use of
Xthese macros, the name of the \code{RNGdata} pointer in your routines'
Xparameter lists {\em must} be \code{rng}, as shown in the examples in
Xthis section.
X
XThe names used as examples in this section begin with ``\code{myrng}'';
Xhowever, there are no restrictions on naming of routines provided by an
XRNG.  However, for ease of readability and consistency, we suggest that
Xthe naming conventions used in this section be followed.
X
XThe routines described in this section should be included in a single
X\code{.c} file.  A template for such a source file, called
X\file{newrng.c}, is included in the distribution and displayed in Figure
X\ref{fig:newrng.c}.
X
XRemember that all RNG state information must be included in the
X\code{RNGstate} field of the \code{RNGdata} structure.  In particular,
Xdo {\em not} use global or static variables to hold RNG state
Xinformation.  Doing so will make it impossible to run several
Xinstantiations of your RNG simulataneously.
X
X\begin{figure}
X\begin{example}
X/* newrng.c */
X/* RNG source file template */
X/* Robert Plotkin
X/* 5/3/93 */
X
X#include "newrng.h"
X
X/* Generating procedure */
X/* Only one of the following two procedures should be */
X/* defined, depending on the kind of value that */
X/* your RNG returns */
X
Xlong newrng_lgen(rng)
XRNGdata *rng;
X\{
X/* Your generating procedure goes here */
X\}
X
Xdouble newrng_dgen(rng)
XRNGdata *rng;
X\{
X/* Your generating procedure goes here */
X\}
X
X/* Seeding procedure */
Xvoid newrng_seed(rng,seed)
XRNGdata *rng;
Xlong *seed;
X\{
X/* Your seeding procedure goes here */
X\}
X
X/* Checking procedure */
Xint newrng_check(rng)
XRNGdata *rng;
X\{
X/* Your checking procedure goes here */
X\}
X\end{example}
X\caption{RNG source file template}
X\label{fig:newrng.c}
X\end{figure}
X
X\subsubsection{Seeding Routine}
X
X\begin{example}
X    void myrng_seed(rng, seed)
X    RNGdata *rng;
X    long *seed;\\
X\end{example}
X
XThis procedure is used for seeding the RNG.  The interpretation of the
X\code{seed} parameter is left entirely to the programmer.  It may, for
Xexample, point to a single integer or to an array of 5,000 integers.
XOne of the RNGs currently installed in the package interprets the
X\code{seed} parameter as pointing to three 16-bit integers.  Obviously,
XRNGs which are capable of being seeded with a variable number of seeds
Xneed to be passed a seed pointer which contains adequate information
Xabout the number of seeds to which it points.
X
XAlthough the seeding procedure is passed an entire \code{RNGdata}
Xstructure as a parameter, it should only manipulate the \code{RNGstate}
Xfield of that structure.  (See Appendix \ref{app:rngdata} for information
Xon the \code{RNGdata} structure.)  Many RNG seeding procedures will simply
Xcopy the seed parameter into \code{RNGstate}, as shown in Figure
X\ref{fig:sampleseed}.
X
X\begin{figure}
X\begin{example}
X    void myrng_seed(rng, seed)
X    RNGdata *rng;
X    long *seed;
X    \{
X    RNGstate[0]=seed[0];
X    RNGstate[1]=seed[1]; /* This RNG uses two long seeds */
X    \}
X\end{example}
X\caption{A sample seeding procedure}
X\label{fig:sampleseed}
X\end{figure}
X
XOther seeding procedures may fill \code{RNGstate} with the results
Xof some complicated function performed on the initial seed table.
X
X\subsubsection{Pseudorandom Number Generating Procedure}
X
X\begin{example}
Xlong myrng_lgen(rng)
XRNGdata *rng;
X
Xdouble myrng_dgen(rng)
XRNGdata *rng;\\
X\end{example}
X
XThe programmer must provide {\em one} procedure, matching one of the two
Xprototypes given above, which returns a
Xsingle generate from the RNG.  The routine may return either:
X\begin{itemize}
X\item a double precision floating point number in the range [0,1), or
X\item a long (32-bit) integer in the range 0..\code{range_rng(rng)}-1
X\end{itemize}
X
X\noindent
XIt is pointless for the programmer to provide procedures of both types.
XIf this is done, only one of them will be accessible by any user code,
Xdepending on the value given to \code{RNGreturns}, \code{RNGdgen}, and
X\code{RNGlgen} (see Section \ref{sec:rngheaders}).
X
XAlthough the generating procedure is passed an entire \code{RNGdata}
Xstructure, it should only manipulate the \code{RNGstate} field of the
Xstructure.  A sample generating procedure is displayed in Figure
X\ref{fig:samplegen}.
X
X\begin{figure}
X\begin{example}
Xlong myrng_lgen(rng)
XRNGdata *rng;
X\{
XRNGstate[0]*=12345+6789;
Xreturn(RNGstate[0]);
X\}
X\end{example}
X\caption{A sample generating procedure}
X\label{fig:samplegen}
X\end{figure}
X
X\subsubsection{RNG Checking Procedure}
X
X\begin{example}
Xint myrng_check(rng)
XRNGdata *rng;\\
X\end{example}
X
XThe programmer must provide a procedure to check the
Xintegrity of the \code{RNGdata} structure.  The procedure returns a value
Xof 1 if the RNG is fit for use, and returns 0 otherwise.  The
Xcoding of the procedure is entirely RNG-specific, and may be
Xextremely simple or extremely complicated, depending on the nature
Xof the RNG and the extent of integrity desired.  On one extreme is
Xthe procedure which always declares success, and on the other
Xextreme is the perfect (and slow) procedure which creates a new
XRNG, seeds it with the seeds of the RNG to be checked, cycles it
Xthrough the number of generates which were produced by the RNG to
Xbe checked, and compares the state tables of the two RNGs.
XClearly, the procedure should not modify the RNG in any way.  When
Xwriting a checking procedure it might be useful to examine those
Xincluded in the existing package.
X
X\subsection{RNG Header Files}
X\label{sec:rngheaders}
X
XFor each RNG included in the package, there must be a
Xcorresponding header file.  The header file contains information
Xabout the RNG which is used by the mrandom library routines.
XThis section describes the information contained in RNG header
Xfiles, and describes how to use such header files to incorporate
Xnew RNGs into the mrandom package.  A template for such a header file,
Xcalled \file{newrng.h}, is included in the distribution and displayed in
XFigure \ref{fig:newrng.h}.
X
X\begin{figure}
X\begin{example}
X/* newrng.h */
X/* RNG header file template */
X/* Robert Plotkin
X/* 5/3/93 */
X
X#include "mrandom.h"
X
X/* Information for mrandom */
X#define RNGstatesize_n
X#define RNGseedsize_2
X#define RNGrange_2
X#define RNGname_2
X#define RNGreturns_2
X#define RNGstatetype_2
X#define RNGdgen_2
X#define RNGlgen_2
X#define RNGseed_2
X#define RNGcheck_2
X
X/* mrandom interface routines */
Xlong newrng_gen(/* RNGdata * */);
Xvoid newrng_seed(/* RNGdata *, long * */);
Xint newrng_check(/* RNGdata * */);
X\end{example}
X\caption{RNG header file template}
X\label{fig:newrng.h}
X\end{figure}
X
X\subsubsection{Information in Header Files}
X\label{sec:headers}
X
XEach header file should begin with the following directives:\\
X
X\begin{example}
X#ifndef MRANDOM
X#include "mrandom.h"
X#endif\\
X\end{example}
X
X\pagebreak
X\noindent
X{\bf Definition of RNG parameters\\}
X
XThe next set of lines in the file should contain \code{#define}
Xstatements which assign values to the RNG's parameters.  The names used
Xin the \code{#define} statements must contain the RNG's number.  There
Xare currently ten RNGs included in the package, labeled 0 through 9.
XThe next RNG included in the package should be labeled number 10, and so
Xon.  The ``\code{n}'' in each parameter name in the following list
Xshould be interpreted as the RNG's number.
X
X\begin{description}
X\item[\code{RNGname_n}] A string constant containing the name of the RNG,
Xterminated with a newline character.
X\item[\code{RNGstatesize_n}] The number of entries in the RNG's state
Xtable.  Each entry is a (32-bit) \code{long}.  If the RNG is
Xcapable of using state tables of varying sizes, \code{RNGstatesize_n}
Xshould be defined as the maximum possible size.
X\item[\code{RNGseedsize_n}] The number of entries in the RNG's seed table.
XEach entry is a (32-bit) \code{long}.  If the RNG is capable of
Xusing seed tables of varying sizes, \code{RNGseedsize_n} should be
Xdefined as the maximum possible size.
X\item[\code{RNGrange_n}]
X\begin{tex} The range of the RNG, expressed as a double
Xprecision floating point number.  The range of the RNG is one more
Xthan the maximum value the RNG is capable of generating.  For RNGs
Xwhich produce double precision generates with a precision of p
X(i.e. in the range $[0,(\code{RNGrange}-1.0)/(1<<p))$, \code{RNGrange}
Xshould be defined as $2^{p}$.  For example, an RNG which produces 8-byte
XIEEE floating-point generates using single-precision IEEE arithmetic
X(24-bit mantissas) has a range of 16777216.0.
X\end{tex}
X\item[\code{RNGreturns_n}] A number signifying the type of the generate
Xreturned by the RNG.  An RNG can return a value of one of two types:
X\begin{itemize}
X\item a \code{long} in the range 0..\code{RNGrange}-1
X\item a \code{double} in the range [0,1)
X\end{itemize}
XRNGs which return values of type \code{long} and \code{double} return
Xtypes \code{RET_LONG} and \code{RET_DOUBLE}, respectively, as defined in
X\file{mrandom.h}.
X\item[\code{RNGstatetype}] A number signifying the interpretation of the
Xvalues stored in the RNG's state and seed vectors.  This value is used
Xby the routines that read and write the ASCII state files, thereby
Xallowing portability of state files across machines with different byte
Xorderings (see Section \ref{sec:saverestart}).  The following values
Xare currently supported:
X\begin{tex}
X\begin{center}
X\begin{tabular}{l l}
XValue & Type\\
X\hline\\
X\code{STATE\_CHAR} & 8-bit character\\
X\code{STATE\_INT} & 16-bit integer\\
X\code{STATE\_LONG} & 32-bit long integer\\
X\end{tabular}
X\end{center}
X\end{tex}
XThe values of \code{STATE\_FLOAT} (IEEE-standard 32-bit float) and
X\code{STATE\_DOUBLE} (IEEE-standard 64-bit float) are not currently
Xsupported and are reserved for future use.
X
X\item[\code{RNGdgen_n} and \code{RNGlgen_n}] The label of the procedure to be
Xused for generating pseudorandom numbers.  If the RNG returns
X\code{double}s, then \code{RNG_dgen} should be defined as the label of
Xthe RNG generating procedure, and \code{RNG_lgen} should be defined as
X0.  If the RNG returns \code{long}s, then \code{RNG_lgen} should be
Xdefined as the label of the RNG generating procedure, and
X\code{RNG_dgen} should be defined as 0.
X\item[\code{RNGseed_n}] The label of the procedure to be used for seeding
Xthe RNG.
X\item[\code{RNGcheck_n}] The label of the procedure to be used for
Xchecking the integrity of the RNG.
X\end{description}
X
X\noindent
X{\bf Procedure prototypes\\}
X
XFinally, the header file must contain function prototypes for
Xthe three procedures provided by the RNG, so that the procedures
Xcan be accessed by the main mrandom code.  For example:\\
X
X\begin{example}
Xlong myrng_gen();
Xvoid myrng_seed();
Xint myrng_check();
X\end{example}
X
X\subsection{Modifying the mrandom code}
XOnly a few lines of \file{mrandom.h} and \file{mrandom.c} need to be
Xmodified when adding a new RNG to the package.
X
X\begin{itemize}
X\item The number of RNGs currently installed in the package is defined as
X\code{NUM_RNGS} in \file{mrandom.h}.  The current value is 10.  This
Xvalue should be incremented when a new RNG is added to the package.
X\item The header file for the new RNG needs to be \code{#include}d in
X\file{mrandom.c}.  The \code{#include} directive should be included in the
Xsection marked by the comment ``\code{Header files for RNGs currently included in package.}''
X\item Several additions need to be made in \file{mrandom.c} in the
Xsection marked by the comment ``\code{Arrays to hold information about
XRNGs.}''  This section of the code declares and initializes several
Xarrays which hold information about the RNGs included in the
Xpackage.
X\pagebreak
XWhen installing a new RNG, the appropriate \code{#define}d values need
Xto be inserted at the end of each initialization list.  For example, the
Xdeclaration of \code{RNGname\_a} currently reads:\\
X
X\begin{example}
Xchar RNGname\_a[NUM\_RNGS][RNGIDSTRLEN]=\{RNGname\_0, RNGname\_1,
X      RNGname\_2, RNGname\_3, RNGname\_4, RNGname\_5, RNGname\_6,
X      RNGname\_7, RNGname\_8, RNGname\_9\};\\
X\end{example}
XAfter adding a new RNG to the package, this declaration would read:\\
X\begin{example}
Xchar RNGname\_a[NUM_RNGS][RNGIDSTRLEN]=\{RNGname\_0, RNGname\_1,
X      RNGname\_2, RNGname\_3, RNGname\_4, RNGname\_5, RNGname\_6,
X      RNGname\_7, RNGname\_8, RNGname\_9,
X      /* RNG #10 added -> */ RNGname\_10\};\\
X\end{example}
XThe arrays \code{statesize\_a}, \code{seedsize\_a}, \code{range\_a},
X\code{returns\_a}, \code{statetype\_a}, \code{seed\_a}, \code{dgen\_a},
X\code{lgen\_a}, and \code{check\_a} need to be similarly modified.
X\end{itemize}
X
X\subsection{Remaking the mrandom Package}
X    Once you have added an RNG to the package as described in the
Xprevious sections, you will need to remake the mrandom package.  To do
Xthis:
X\begin{itemize}
X\item Make sure that all of the files for the mrandom package,
Xinclude the source and header files for your new RNG, are in the
Xsame directory.
X
X\item Include the names of your header, source, and object files in
X\file{makefile} on the lines labeled \code{INCS}, \code{SRCS}, and
X\code{OBJS}, respectively, as show in Figure \ref{fig:addmake}.
X
X\begin{figure}
X\begin{example}
XINCS = mrandom.h bentley.h pcrand.h ran0.h ran1.h ran2.h ultra.h xsq.h myrng.h
XSRCS = mrtest.c mrandom.c bentley.c pcrand.c ran0.c ran1.c ran2.c ultra.c xsq.c myrng.c
XOBJS = mrandom.o bentley.o pcrand.o ran0.o ran1.o ran2.o ultra.o xsq.o myrng.o
X\end{example}
X\caption{Addition of {\tt myrng} to {\tt makefile}}
X\label{fig:addmake}
X\end{figure}
X
X\item Follow the instructions for making the mrandom package, as
Xdescribed in Section \ref{sec:install}.
X\end{itemize}
XOnce the package has been remade it will be ready for use, with your new
XRNG, by other programs.
X
X\pagebreak
X\appendix
X\section{The RNGdata Structure}
X\label{app:rngdata}
X\subsection{Introduction}
XThis section describes the representation in C of the \code{RNGdata}
Xstructure which is used by the mrandom package to represent RNGs.  This
Xstructure need never be manipulated by the programmer, except as
Xdescribed in Section \ref{sec:progroutines}.  This section, therefore,
Xis intended for those who are interested in learning a little more about
Xthe inner workings of the mrandom package.
X
XIn order to generate random numbers, the user must first declare a
Xpointer to an \code{RNGdata} structure, and use \code{init_rng} to
Xallocate space for the RNG and perform various initialization functions.
XThe user uses the RNG entirely through calls provided by the interface
Xdescribed in Section \ref{sec:library}; i.e. the user should not
Xdirectly manipulate the \code{RNGdata} structure.
X
X\subsection{Inside the Structure}
X    The definition of the \code{RNGdata} structure is displayed in
XFigure \ref{fig:rngdata}.
X
X\begin{figure}
X\begin{example}
X\begin{tabbing}
Xstruct \= rngdata \{ \+ \\
Xlong rngalg;\\
Xlong mrandom_alg;\\
Xlong *rngstate;\\
Xlong *rngseed;\\
Xlong rngcount1;\\
Xlong rngcount2;\\
Xstruct \{ \= \+ \\
Xlong size;\\
Xlong nleft;\\
Xlong nbleft;\\
Xdouble *dbuf,*dbufp;\\
Xlong *lbuf,*lbufp;\\
Xint *bbuf,*bbufp;\\
X\} buffer; \- \\
Xlong rngnextval;\\
Xlong rngsplit;\\
Xchar rngname[];\\
Xlong rngstatesize;\\
Xlong rngseedsize;\\
Xlong rngrangem1;\\
Xdouble rngrange;\\
Xsigned int rngreturns; \- \\
X\}; \\
Xtypedef struct rngdata RNGdata;
X\end{tabbing}
X\end{example}
X\caption{The {\tt RNGdata} structure}
X\label{fig:rngdata}
X\end{figure}
X
XDescriptions of its fields are as follows:
X
X\begin{description}
X\item[\code{rngalg}] A number identifying the algorithm to be used by
Xthe RNG to produce pseudorandom generates.  Algorithms in the package
Xare numbered sequentially starting with 0; currently there are 10
Xalgorithms installed, numbered 0 through 9.  A table of RNGs which are
Xcurrently installed in the mrandom package, with their corresponding
Xalgorithm numbers, is in Appendix \ref{app:installedrngs}.
X\item[\code{mrandom_alg}] The algorithm use by \code{mrandomrv} when
Xcalled with this RNG.  See Section \ref{sec:mrandomrv} for more on
X\code{mrandomrv}.
X\item[\code{rngstate}] A pointer to the RNG's state vector, used to
Xstore the current state of the RNG.  See Sections \ref{sec:saverestart},
X\ref{sec:progroutines}, and \ref{sec:headers} for more information on RNG
Xstate vectors.
X\item[\code{rngseed}] A pointer to the RNG's seed vector.  See Section
X\ref{sec:seedproc} for more information on RNG seed vectors.
X\item[\code{rngcount1}, \code{rngcount2}] These two values represent the
Xnumber of generates the RNG has produced since initialization, according
Xto the formula:\\
X\begin{example}
Xrngcount1+rngcount2*BILLION\\
X\end{example}
Xwhere BILLION is defined in \file{mrandom.h}.  Please note that the
Xvalue represented by \code{rngcount1} and \code{rngcount2} is the {\it
Xtotal} number of generates produced by the RNG since initialization,
Xincluding those discarded due to splitting of the RNG.  (See Section
X\ref{sec:examandmodify} for more information about splitting RNGs.)
X\item[\code{rngnextval}] The next value to be output from the RNG.  This
Xvalue is used internally by the mrandom library and is not guaranteed to
Xbe accurate.
X\item[\code{rngsplit}] Every (\code{split}+1)-th generate of the
Xunderlying RNG will be returned by the RNG calling procedures.
X\code{rngsplit} is set to \code{DEF_SPLIT} upon initialization of the
XRNG, as defined in \file{mrandom.h}.  See Section \ref{sec:examandmodify}
Xfor more information about splitting RNGs.
X\item[\code{buffer}] This structure contains information about the RNG's
Xbuffer and its bit buffer.  (See Section \ref{sec:genproc} for more
Xinformation on RNG buffers.)  It contains several fields:
X\begin{description}
X\item[\code{size}] The number of entries in the RNG's buffer.
X\item[\code{nleft}] The number of values left in the RNG's buffer.
X\item[\code{nbleft}] The number of values left in the RNG's bit buffer.
X\item[\code{dbuf}, \code{dbufp}] A pointer to the first entry in the double
Xbuffer, and a pointer to the next entry to be retrieved from the
Xdouble buffer.
X\item[\code{lbuf}, \code{lbufp}] Same for the long buffer.
X\item[\code{bbuf}, \code{bbufp}] Same for the bit buffer.
X\end{description}
X\end{description}
X
XThe remaining values in the RNGdata structure are derived
Xfrom the RNG's header file upon initialization.  For more information on
Xthe values of these fields, see Section \ref{sec:headers}.
X
X\section{RNGs Currently Installed in the Package}
X\label{app:installedrngs}
XThere are currently ten RNGs installed in the mrandom package.  This
Xappendix provides brief descriptions of each of them.  References are
Xprovided for those who are interested in finding out about the RNGs in
Xmore detail.
X
X\begin{description}
X
X\item[RNG algorithm 0: A trivial RNG] A trivial RNG is included in the
Xpackage, primarily for testing purposes.  The generates it produces are
Xnot ``random'' in virtually any sense of the word; it simply produces
Xgenerates from an arithmetical progression determined by its initial
Xseeds.  For example, if it is seeded with 5 and 7, respectively, it will
Xproduce the sequence 5, 12, 19, 26, etc.
X
XThis RNG takes two \code{long}s as seeds.  It returns generates
Xof type \code{long}.
X
X\item[RNG algorithm 1: 4.3bsd random]
X\begin{tex}
XThis is UNIX 4.3bsd \code{random}.  It is a 31-bit nonlinear additive
Xfeedback generator with a range of $2^{31}$ and a period of
Xapproximately $16*2^{31}-1$.  It is nominally able to save and restore
Xstate, but its state-saving code is buggy.  Therefore, when using
X\code{random} with the mrandom package, no more than one RNG should use
X\code{random} at a time.
X\end{tex}
X
XThis RNG takes a single \code{long} as a seed.  It returns generates of
Xtype \code{long}.
X
X\item[RNG algorithm 2: the Knuth/Bentley prand]  This
Xlagged-Fibonacci RNG was introduced by Jon Bentley in his ``Software
XExploratorium'' column in {\em Unix Review}, Vol. 10, No. 6, June 1992,
Xand is based on one first presented in Donald E. Knuth's {\em The Art of
XComputer Programming}, Vol. 2, Addison-Wesley, Reading, Mass., 1981.
XIt has a range of 1,000,000,000.
X
XThis RNG takes a single \code{long} as a seed.  It returns generates of
Xtype \code{long}.
X
X\item[RNG algorithm 3: The Portable Combined RNG]  This combined
Xprime multiplicative congruential RNG was developed based on algorithms
Xand selections of prime numbers presented in ``Efficient and Portable
XCombined Random Number Generators,'' Pierre L'Ecuyer, {\em
XCommunications of the ACM}, Vol. 10, No. 6, June 1992, and ``Random
XNumber Generators: Good Ones are Hard to Find,'' Stephen Park and Keith
XMiller, {\em Communications of the ACM}, Vol. 31, No. 10, October 1992.
XIt has a range of 2147483561.
X
XThis RNG takes two \code{long}s as seeds.  It returns generates of type
X\code{long}.
X
X\item[RNG algorithm 4: 4.3bsd nrand48]
X\begin{tex}
XThis is UNIX 4.3bsd \code{nrand48}.  It produces generates using a
Xlinear congruential algorithm and 48-bit integer arithmetic.  It has a
Xrange of $2^{31}$.
X\end{tex}
X
XThis RNG takes three \code{unsigned short}s as seeds.  They are passed
Xto the seeding procedure as two \code{long}s, and are interpreted in the
Xfollowing way:
X\begin{itemize}
X\item The 16 least significant bits of the second \code{long} is the
Xfirst seed.
X\item The 16 least significant bits of the first \code{long} is the
Xsecond seed.
X\item The 16 most significant bits of the first \code{long} is the third
Xseed.
X\item The 16 most significant bits of the second \code{long} is
Xignored.
X\end{itemize}
XThis RNG returns generates of type \code{long}.
X
X\item[RNG algorithm 5: 4.3bsd rand]
X\begin{tex}
XThis is UNIX 4.3bsd \code{rand}.  It uses a multiplicative congruential
Xalgorithm.  It has a period of $2^{32}$ and a range of $2^{31}$.
X\end{tex}
X
XThis RNG takes a single \code{long} as a seed.  It returns generates of
Xtype \code{long}.
X
X\item[RNG algorithm 6, 7, and 8: Press and Teukolsky's ran0, ran1, and
Xran2]
X\begin{tex}
XThese three multiplicative congruential RNGs are adapted from those
Xpresented in ``Portable Random Number Generators,'' William H.  Press
Xand Saul A. Teukolsky, {\em Computers in Physics}, Vol. 6, No. 5,
XSep/Oct 1992.  They all have a period of $2^{31}-2$ and a range of
X$2^{31}-1$.
X\end{tex}
XThese RNGs take a single \code{long} as a seed.  They return generates
Xof type \code{double}.
X
X\item[RNG algorithm 9: Marsaglia's Ultra RNG]
X\begin{tex}
X
XWe obtained the source code for this generator by anonymous ftp from
X\code{nic.funit.fi} (take the file \code{fsultra.zip} from the directory
X\code{/pub/msdos/science/math/fsultra}).  A note in the \file{readme}
Xfile says: ``To obtain permission to incorporate this program into any
Xcommercial product, please contact the authors at the e-mail address
Xgiven above [[e-mail] or [e-mail]] or at Department of
XStatistics and Supercomputer Computations Research Institute, Florida
XState University, Tallahassee, FL 32306.''  This RNG is one of those
Xoriginally presented in ``A New Class of Random Number Generators,''
XGeorge Marsaglia and Arif Zaman, {\em The Annals of Applied
XProbability}, Vol. 1, No. 3, 1991.  It is a ``subtract-with-borrow''
Xgenerator with a range of $2^{32}$ and a staggering period of
X$10^{354}$.
X\end{tex}
X
XThis RNG takes two \code{unsigned long}s as seeds.  It returns generates
Xof type \code{double}.
X\end{description}
X
X\end{document}
END_OF_FILE
if test 56912 -ne `wc -c <'doc/mrandom.tex'`; then
    echo shar: \"'doc/mrandom.tex'\" unpacked with wrong size!
fi
# end of 'doc/mrandom.tex'
fi
echo shar: End of archive 4 \(of 6\).
cp /dev/null ark4isdone
MISSING=""
for I in 1 2 3 4 5 6 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 6 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0