%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%\documentstyle[12pt]{article}
\documentstyle[12pt,epsf,psfig]{article}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itobservation}[itlemma]{Observation}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{observation}{\begin{itobservation}\rm}{\end{itobservation}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
					\noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt}        %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]}            %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bo}[1]{\begin{observation}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}    %Yes, 2 different ones...
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\eo}{\mybox\end{observation}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\eos}{\end{observation}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%%%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%%%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}
%%%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%%%\def \min {{\rm min \,}}
\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%%%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%%%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%%%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or
%%%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%%% FOOTNOTE (Instead of Roman).  See LaTeX manual pp.91-92 as well as 175.
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%% FROM HERE, macros special for paper
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1} % projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\pagestyle{empty}
\begin{flushright}
{\sl CPS615-fall.95.hmk6}
\end{flushright}

\vspace{1cm}
\vspace{1cm}

\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
Generation of Random Numbers - the Linear Congruent Generator. 
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

\begin{center}
Saleh Elmohamed\\
Northeast Parallel Architectures Center,\\
Syracuse University\\
Syracuse, NY 13244-4100\\
saleh@npac.syr.edu\\
\end{center}
\newpage
\pagestyle{empty}
\tableofcontents

\newpage

\pagestyle{plain}
\pagestyle{myheadings}
\markright{\sl CPS615-fall.95.hmk6}
\section{Solution to problem [1]}
\setcounter{page}{1}

The linear congruential methods (LCG) is a widely used method as a
random numbers generator. A good source to study this method in a
details is that of Knuth \cite{Knuth}. Those numbers composing the
LCG equation are: the modulus ($M, M > 0$), the multiplier ($A, 0\le A
< M$), the increment ($C, 0 \le C < M$), and the starting value ($X_0,
0\le X_0 < M$). The desired sequence of random numbers $<X_n>$ is then
obtained by setting:

\be{LCG-equation}
X_{n+1} = (A X_n + C) \;\;\;mod \;\;\;\;M, \;\;\;\; n \ge 0.
\ee

The sequences obtained are not always ``random'' for all choices of
$M, A, C,$ and $X_0$. Also congruential sequences always ``get into a
loop''; i.e. there is ultimately a cycle of numbers that is repeated
endlessly. The repeating cycle is called the period and a useful
sequence will of course have a relatively long period, but a long
period is only one desirable criterion for the randomness of the
sequence. For example, when $A = C = 1$, the sequence is simply
$X_{n+1} = (X_n + 1)\;\;\; mod\;\;\; M$, and this obviously has a period of length
$M$, yet it is anything but random.

\subsection{Complete Program of an LCG-based Random Numbers Generator}

\begin{verbatim}
/******************************************************************
Author: Saleh Elmohamed
Nov, 1995.
Function: an LCG random numbers generator and more.
********************************************************************/
/*******************************
The computation required to generate a new random number is a one
integer multiplication, which multiplies two 32-bit integers and
returns the answer modulo 2^{31}-1 (this is the standard  
for unsigned ints in C), and 1 floating point multiplication, to
convert  the integers into a floating point number in [0,1).
*********************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>

#define PRANDMAX 10000000000

/* Variables for the linear congruential generator (LCG)
    used in initialization */
#define M ( 0x7fffffff )    /* also set to  65536 or 16  */
                      /* = 2^{31}-1 in hex -- mask by M to get 
                                      modulo 2^{31} */

#define A  1103515245   /* also set to 66  or  5  */
#define C  12345        /* also set to 0 */

/*********************************************************************
   Initialize the random number generator.

   LCG:      s_{i+1}  = (A * s_i  + C)   mod M

   A = 1103515245   C = 12345   M = 2^{31}-1
*********************************************************************/
/*----------------------------------------------------------*/
/*-----------------The main driver of the generator.--------*/
/*----------------------------------------------------------*/
/* The input line takes a filename followed by 3 arguments. */
/*  

After compilation, to run the program do:

 <Filename.executable>   <Total_number>   <Initial_seed>

------------------------------------------------------------*/
main( int argc, char *argv[])
{
  int total_number, dim_number;
  int i, j;
  unsigned long seed;
  unsigned long current, randx, rand_total;
  double *random_list, sum, x, y; 

  double mean, variance, standard_deviation;

  FILE *f1, *f2, *f3, *fopen();
/*---------------The input line arguments. ---------------------------*/
                                   /* 0. The a.out file.              */
  total_number = atoi(argv[1]);    /* 1. Total numbers generated.     */
  seed = atoi(argv[2]);            /* 2. The seed of the generator.   */
      
  f1 = fopen("x_y.two_adjacent_numbers.out","w");
  f2 = fopen("error_in_mean_variance.out","w");
  f3 = fopen("list_of_randoms.out","w");

/*---------------------------------------------------------------------*/
/* For defensive programming, one need to do some normalization:       */
/*---------------------------------------------------------------------*/
  if (seed < 0)    
    seed = -seed;   

#if 0
  seed = seed % PRANDMAX; 
#endif

  random_list = malloc(total_number * sizeof(double));
  rand_total = 0;
  sum = 0.0;
  randx = seed;
  printf("\n.... Sample Size: .... \n");
  for (i = 0; i < total_number; i++)
    {
      current = (A * randx + C) % M;
      random_list[i] = current;
      rand_total += current;
      randx = current;
      fprintf(f3, "The %d  random =  %d\n", i + 1, current);
   }

#if 1
  for (i = 0; i < total_number - 1; i++) 
    {
      x = (double) random_list[i] / (double) M;
      y = (double) random_list[i+1] / (double) M;
      fprintf(f1,"%f  %f \n", x, y);
    }
#endif
/*======================= Statistical Analysis =====================*/
/*--- [1] compute the mean ---*/
  mean = (double) rand_total / total_number;
  printf("\nSize = %d , Sample sum = %ld, Average = %f\n", 
         total_number, rand_total, mean);

/*--- [2] compute the variance ---*/
  for (i = 0; i < total_number; i++)
    sum += ((random_list[i] - mean) * (random_list[i] - mean));

  variance = (double) sum / total_number;

  printf("\nSize = %d ,  variance =  %f\n", total_number, variance);
  printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
  printf("\nRandoms in [0,1) interval ..... \n");

  mean = mean / (double) M;
  printf("\nSize =  %d ,  average = %f\n", total_number,  mean);
  printf("\nError in average = %f\n", fabs(0.5 - mean));

  fprintf(f2,"Size=  %d   error_in_average=  %f\n", 
          total_number, fabs(0.5 - mean));

  variance = variance /((double) M * M);

  printf("\nSize =  %d ,  variance = %f\n", total_number, variance);
  printf("\nError in variance =  %f\n", fabs((1.0/12) - variance)); 

  fprintf(f2,"Size=  %d   error_in_variance=  %f\n", 
          total_number, fabs((1.0/12) - variance));

  fclose(f1);
  fclose(f2);
  fclose(f3);
}

\end{verbatim}

\subsection{Plots and Analysis of the Program's Output}

After setting $A$ to 13445, $C$ to 0, $M$ to 65536, and seed to 16811,
a program run for each of the following sequence sizes of 10, 100,
1000, and 10000 was obtained. The following figures (Figure 1 and 2)
plot the sample size vs. the error of the mean values, and sample size
vs. the error of the variance, respectively. For a higher floating
point accuracy, Alpha's Kestrels are used for running this program.

\begin{figure}[htb]
\centerline{\psfig{figure=sample_size.vs.mean_error.ps,width=6in,angle=-90}}
\caption{Sample sizes vs. the mean's error.} 
\label{graph.1}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=sample_size.vs.var_error.ps,width=6in,angle=-90}}
\caption{Sample sizes vs. the variance's error.} 
\label{graph.2}
\end{figure}

Figure \ref{graph.1} shows that given the generator parameters, as we
increase the sample size the error obtained from the average declines
very slowly. The ideal situation is that it should approach zero but
because of the value of parameter $C$ it won't. For a better result
one needs to have a larger than zero value fro $C$. Likewise, the
decline in the average's error will also result in a decline in the
variance error. The variance itself goes from $0.149930$ for sample
size $10$ to $0.085846$ for size $100$ to $0.079155$ for size $1000$
then goes up a little to $0.083867$ for sample size $10000$.

\section{Solution to problem [2]}

Here we take the above program using the following values: $A = 5$, 
$C = 0$, $M = 16$ , and $seed$ varying between $0$ and $15$ as
follows:

\begin{verbatim}

 Seed                     output                pattern
-----------           -----------------       ---------------
  0                    0 0 0 0 0  0 0 0            0
  1                    5 9 13 1 5 9 13 1        5 9 13 1
  2                    10 2 10 2 10 2 10 2        10 2
  3                    15 11 7 3 15 11 7 3      15 11 7 3
  4                    4 4 4 4 4 4 4 4             4
  5                    9 13 1 5 9 13 1 5        9 13 1 5
  6                    14 6 14 6 14 6 14 6        14 6
  7                    3 15 11 7 3 15 11 7      3 15 11 7
  8                    8 8 8 8 8 8 8 8             8
  9                    13 1 5 9 13 1 5 9        13 1 5 9
  10                   2 10 2 10 2 10 2 10        2 10
  11                   7 3 15 11 7 3 15 11 7    7 3 15 11
  12                   12 12 12 12 12 12 12        12
  13                   1 5 9 13 1 5 9 13        1 5 9 13
  14                   6 14 6 14 6 14 6 14        6 14
  15                   11 7 3 15 11 7 3 15      11 7 3 15

Viewing the output differently, new patterns emerge telling us that
different seeds can produce the same pattern:

 Seed(s)                         formed pattern(s)
-------------                  --------------------
1 5 9 13                           5 9 13 1
2 10                               10 2
3 15 11 7                          15 11 7 3
4                                  4
14 6                               6 14
8                                  8
12                                 12

\end{verbatim}

\subsection{Observations}
\begin{itemize}
\item
There are 8 (eight) independent patterns. Also we observe that the odd seeds
form longer patterns than the even numbers. 
\item
The even seeds form patterns consisting of even numbers and the odd
seeds form patterns consisting of odd numbers.
\item
Three of the even seeds form a patterns of single numbers which is the
seed itself.
\item
From the LCG equation $X_{n+1} = (A * X_n + C)\;\;mod\;\;M$, we can
deduce the following:
\begin{verbatim}
Given A = 5, C = 0, M = 16, and seed =[0...15],

   X_n         5 * X_n       (mod 16)
 ------       --------       --------
   1             5              5
   5            25              9
   9            45              13
   13           65              1

   2            10              10      
   10           50              2

   3            15              15
   7            35              3
   11           55              7
   15           75              11

   6            30              14
   14           70              6

   12           60              12
   8            40              8
\end{verbatim}

\item Setting $C = 0$ and having a small even value for $M$ has an
effect on the above behavior of patterns. One good choice for $M$ is a
large prime number.
\end{itemize}

\section{Solution to problem [3]}

For this problem, setting seed to $0$ will yield a list of all zeros
so best to have seed to be some value other than $0$. I have chosen to
set it to $13$.
\subsection{Part A}

LCG: $(A = 66, c = 0, M = 2^{31}, seed = 13)$ for 4096 random
numbers. Because of M exceeding the max allowed modulus that can be
used, the output $(x_i,x_{i+1})$ list is normalized giving: 
\begin{verbatim}

0.000000  0.000026 
0.000026  0.001740 
0.001740  0.114865 
0.114865  0.581116 
0.581116  0.353682 
0.353682  0.343009 
0.343009  0.638582 
0.638582  0.146404 
0.146404  0.662634 
0.662634  0.733869 
0.733869  0.435328 
0.435328  0.731617 
0.731617  0.286720 
0.286720  0.923538 
0.923538  0.953522 
0.953522  0.932434 
0.932434  0.540649 
0.540649  0.682861 
0.682861  0.068848 
0.068848  0.543945 
0.543945  0.900391 
0.900391  0.425781 
0.425781  0.101562 
0.101562  0.703125 
0.703125  0.406250 
0.406250  0.812500 
0.812500  0.625000 
0.625000  0.250000 
0.250000  0.500000 
0.500000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 

... etc. ...

0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
0.000000  0.000000 
\end{verbatim}

A plot of this data is displayed in  Figure \ref{graph.3}.

\begin{figure}[htb]
\centerline{\psfig{figure=x_y.adjacent-randoms.m=2to31.seed=13.v2.ps,width=6in,angle=-90}}
\caption{(X,Y) adjacent randomly generated numbers, for $M=2^{31}$,
seed=13, A=66, and C=0}
\label{graph.3}
\end{figure}

\subsection{Part B}

LCG: $(A = 5, c = 0, M = 2^{31}-1, seed = 13)$ for 4096 random
numbers. 
A list of these numbers is given:
\begin{verbatim}
0.000000  0.000000 
0.000000  0.000001 
0.000001  0.000004 
0.000004  0.000019 
0.000019  0.000095 
0.000095  0.000473 
0.000473  0.002365 
0.002365  0.011823 
0.011823  0.059117 
0.059117  0.295586 
0.295586  0.477929 
0.477929  0.389644 
0.389644  0.948222 
0.948222  0.741111 
0.741111  0.705557 
0.705557  0.527784 
0.527784  0.638920 
0.638920  0.194599 
0.194599  0.972995 
0.972995  0.864973 
0.864973  0.324865 
0.324865  0.624326 
0.624326  0.121630 
0.121630  0.608150 
0.608150  0.040748 
0.040748  0.203740 
0.203740  0.018702 
0.018702  0.093511 
0.093511  0.467556 
0.467556  0.337781 
0.337781  0.688907 
0.688907  0.444534 
0.444534  0.222670 
0.222670  0.113352 
0.113352  0.566760 

... etc. ....

0.415294  0.076468 
0.076468  0.382339 
0.382339  0.911696 
0.911696  0.558480 
0.558480  0.792402 
0.792402  0.962012 
0.962012  0.810059 
0.810059  0.050293 
0.050293  0.251463 
0.251463  0.257315 
0.257315  0.286573 
0.286573  0.432864 
0.432864  0.164320 
0.164320  0.821598 
0.821598  0.107990 
0.107990  0.539951 
0.539951  0.699754 
0.699754  0.498772 
0.498772  0.493859 
0.493859  0.469294 
0.469294  0.346470 
0.346470  0.732351 
0.732351  0.661755 
0.661755  0.308774 
0.308774  0.543871 
0.543871  0.719354 
\end{verbatim}

These numbers are plotted in Figure \ref{graph.4}.

\begin{figure}[htb]
\centerline{\psfig{figure=x_y.adjacent-randoms.m=2to31-1.seed=13.v2.ps,width=6in,angle=-90}}
\caption{(X,Y) adjacent randomly generated numbers, for $M=2^{31}-1$,
seed=13, A=5, and C=0}
\label{graph.4}
\end{figure}

\section{Discussion}

The above generators are not good at all and partly because of our
choice of values for $A$, $C$, and $M$. The values of these two
parameters have a great effect on the periodic length of the random
numbers. Certainly, setting $C$ to $0$ and using small values for $A$
gives a very poor and unacceptable set of random numbers, regardless of the
value $M$. Of course, a good chosen value for the modulus $M$ is
essential and ideally  equal to $2^{31} -1$. Also, setting seed to $0$
give us a sequence which is basically all zeros.

The last plot (Figure \ref{graph.5}) shows that the results can be
improved by choosing appropriate values of $A$, $C$ and $M$. These are
$M= 2^{31} -1$ , $A = 1103515245$,  $C = 12345$, and seed = 13 as
above.

\begin{figure}[htb]
\centerline{\psfig{figure=x_y.adjacent_randoms.large_C.M=2to31-1.seed=13.ps,width=6in,angle=-90}}
\caption{(X,Y) adjacent pairs, for $M=2^{31}-1$, seed=13, A=1103515245, and C=12345}
\label{graph.5}
\end{figure}

%\clearpage
\newpage
\begin{thebibliography}{MASE}

\bibitem[Knuth]{Knuth}
D. E. Knuth,
The Art of Computer Programming: Seminumerical Algorithms, Vol. 2. 2nd
edition, Addison-Wesley, 1981.

\end{thebibliography}

\end{document}
