\documentstyle[twoside,11pt,ltexproc]{article}
\include{psfig}
\setlength{\oddsidemargin}{+1in}
\setlength{\evensidemargin}{+.6in}
\setlength{\topmargin}{+5mm}
\raggedbottom

\begin{document}
\cleardoublepage
\pagestyle{myheadings}

\title{\bf Implementation of a Random Number Generator for sequential and parallel computers.}
\author{
Olukayode O. Odeyemi 
\thanks{Research Apprentice, 1995 NPAC REU Program,
{\it oodeyemi@npac.syr.edu}; Electrical Engineering and Computer Science major, City University of New York (City College),  
{\it csoko@csfaculty.engr.ccny.cuny.edu}.} 
\and Paul Coddington 
\thanks{NPAC Research Scientist, {\it paulc@npac.syr.edu}.}
} 

\date{\sc Proposal for a 1995 NPAC REU Project\thanks
{The 1995 Research Experiences for Undergraduates (REU) Program in 
 High-Performance Computing is conducted by the Northeast Parallel 
 Architectures Center (NPAC) at Syracuse University.  
 The National Science Foundation provides primary funding for the NPAC REU 
 program, through NSF Grant CDA-9424332.  
 Additional funding is provided by Syracuse University and NPAC.} }
\maketitle
\markboth{Odeyemi \& Coddington}{Implementation of a Random Number Generator}

\begin{abstract}

Here we propose an implementation of 64 bit sequential as well as
32 \& 64 bit parallel random number generators. In the near future, 64
bit processors will be commonplace.  Also parallel architectures
will dominate the computing scene. This will lead to an increase in
computing power, which will enable simulations of larger proportions,
in particular those using random number generators. 
Longer periods, better randomness properties, and portability to
different machines and architectures are needed for these generators to
keep up with simulation requirements. 
The combination of two generators,
efficiently implemented in a language such as High Performance
Fortran, can meet these conditions.

\end{abstract}

\section{Introduction}
Many computer simulations e.g. Monte Carlo simulations, use 
random number generators. However, according to Donald Knuth \cite{knuth1},  
``Random number generators should not be chosen at random'',
since there are not many good generators available, which of
course leads to the continuous study and improvement of random number
generators. But one has to point out right away that these generators
produce {\it pseudorandom} numbers, because the numbers generated are
actually deterministic sequences, so cannot be truly random. 
However this is not as bad as it seems, since the numbers generated
need to be deterministic and repeatable in order to 
debug a program that uses a random number generator. 

In order for a random number generator to be acceptable, it has to have the 
following properties \cite{csep}:

\begin{enumerate}
\item Produce uncorrelated sequences.
\item Have a long period (i.e. repetitions of the sequence are far apart).
\item Sequences should be of uniform distribution.
\item The program should be efficient.
\end{enumerate}

However, it is a little bit tricky to satisfy all these conditions. 
For example, not everything 
that seems random is uniform and not everything that is uniform is random. 
A deterministic sequence would have a hard time passing as being uncorrelated, 
and the other pair of conditions are difficult to achieve. 
Overcoming these problems is one of the tasks of this project.  

One of the generators commonly used is the 
{\it Linear Congruential Generator} (LCG) \cite{knuth1,PandM,csep,RNS,test}. 
These generators produce their sequence of numbers by using 
equations of the form:
  \begin{equation}
     S_{i} = A\,S_{i-1} + C\: {\em mod}\:m ,
  \end{equation}
where $S_{i}$ is the $i^{th}$ seed or random number generated, $S_{0}$ 
being the initial seed (to be selected by user); 
{\em A} is some multipier (to be determined); 
{\em m} is a modulus (to be determined) and {\em C} is some constant. 
For the terms that need to be determined, there are rules and tests 
that help choosing them \cite{knuth1}.  
One of these tests is the {\em spectral test} \cite{knuth1,csep,test}, 
a popular test used to determine the randomness of the output of a generator.  
We would like a generator to have a uniform spread as in 
Figure~\ref{Fig.plots}, rather than having a lattice structure 
as in Figure~\ref{Fig.plots2}. 
The spectral test properties for LCG's improve 
as the word size of the numbers used is increased, for example from 32 to 
64 bits \cite{knuth1,RNS,test}. 


\begin{figure}[htb]
\begin{minipage}{3in}
     \centerline{\psfig{figure=points1.ps,angle=-90,width=2.9in}}
     \caption{This graph shows good randomness.}
     \label{Fig.plots} 
\end{minipage}
\ \
\begin{minipage}{3in}

     \centerline{\psfig{figure=points2.ps,angle=-90,width=2.9in}}
     \caption{This one, however shows a pattern thus some kind of correlation.}
     \label{Fig.plots2}

\end{minipage}
\end{figure}


A combination of two LCG generators is advantageous since it provides 
longer cycles and better randomness properties \cite{WandH,RNS,test}. 
This combination can be done by simply adding the numbers produced by the
two LCGs, modulo the smallest value of $m$ for the two generators.
It is this kind of generator that will be used in this project. 
The maximum period of a linear congruential generator is $m$ \cite{knuth1}, 
which is about $10^9$ for generators using 32-bit numbers and $10^{19}$ 
for 64-bit generators. 
Combining two LCG's gives a generator with a period which 
is the product of the periods of the two LCG's, i.e. $10^{19}$ for 32-bit
generators and $10^{38}$ for 64-bit generators.


As time goes by, there is going to be the need for generators that are portable
to different machines and architectures (particularly parallel architecture
machines), for example, in order to cross-check simulation results. 
This would mean that most generators used right now would be obsolete 
in due time, thus the need for better implementations. 
Within the next five to ten years, large simulations on teraflop 
supercomputer would easily exhaust 32-bit generators we have today, 
thus the need for 64-bit implementations. 
There are some implementations of the 32-bit sequential and
parallel random number generators \cite{CandL}, but these could be improved 
upon as well as extended to a 64-bit implementation, that is, an extension 
to the work done by Cote and L'Ecuyer\cite{CandL} for 32-bit combined LCGs. 


\section{Proposed Work}
For this project, the work to be done is as follows: 

\begin{itemize}
\item Parallelizing existing 32-bit sequential random number generator code.
\item Implementation of 64-bit sequential random number generator.
\item Parallelizing the 64-bit sequential random number generator code.
\end{itemize}

These random number generators would be combined LCG's, which should make 
for better randomness properties. This work will 
also include determining values for {\em A}, {\em C} and {\em m} for 64-bit
LCGs that would give optimal period and then testing these generators 
to observe their randomness properties using the spectral test, so 
we get a densely packed even spread as in Figure~\ref{Fig.plots}.
We expect that on completion of the work we will have all the generators 
working properly and meeting all the conditions for an acceptable generator 
as stated above.

\begin{thebibliography}{99}
\bibitem{knuth1}
D.E. Knuth, {\it Seminumerical Algorithms}, 2nd Ed., 
Vol. 2 of {\it The Art of Computer Programming}, Addison-Wesley, 
Reading PA, 1981.
\bibitem{PandM}
Stephen K. Parker \& Keith W. Miller, 
{\it Random Number Generators: Good ones are hard to find}, 
Communications of the ACM, Volume 31, Number 10, 1988.
\bibitem{csep}
{\it Random Number Generators}, Computational Science Education Project, 
1995. Available from {\tt http://csep1.phy.ornl.gov/rn/rn.html}.
\bibitem{RNS}
Pierre L'Ecuyer, {\it Random Numbers for Simulation}, 
Communications of the ACM, Vol. 33, Number 10, 1990.
\bibitem{ARNGUMCS}
P. D. Coddington, {\it Analysis of Random Number Generators Using Monte Carlo 
Simulation}, Int. J. Mod. Phys. C, Vol. 5, p. 547, 1994.
\bibitem{CandL}
Pierre L'Ecuyer \& Serge Cote, {\it Implementing a Random Number Package with
Splitting Facilities}, ACM Transactions on Mathematical Software, Vol.  
17, No. 1, 1991.
\bibitem{WandH}
B.A. Wichmann \& I.D. Hill, 
{\it An efficient and portable pseudorandom number generator},
Appl. Stat., Vol. 31 (1982).
\bibitem{mctprng}
P.D. Coddington, S.H. Ko, W.E. Mahoney and J.M. del Rosario, 
{\it Monte Carlo Tests of Parallel Random Number Generators},
Northeast Parallel Architectures Center at Syracuse University Technical 
Report, in preparation.
\bibitem{test}
Pierre L'Ecuyer, 
{\it Efficient and Portable combined Random Number Generators}, 
Communications of the {\em ACM}, Volume 13, Number 6, 1995.
\end{thebibliography}

\end{document}


