22.1_Operation_of_Random_Numbers_on_the_RECOMP_Digital_Computer_Feb62 22.1 Operation Of Random Numbers On The RECOMP Digital Computer Feb62
22.1_Operation_of_Random_Numbers_on_the_RECOMP_Digital_Computer_Feb62 22.1_Operation_of_Random_Numbers_on_the_RECOMP_Digital_Computer_Feb62
User Manual: 22.1_Operation_of_Random_Numbers_on_the_RECOMP_Digital_Computer_Feb62
Open the PDF directly: View PDF 
.
Page Count: 25
| Download | |
| Open PDF In Browser | View PDF |
AUT 0 NET I C S
A DIVISION OF NORTH AMERICAN AVIATION, INC.
INDUSTRIAL PRODUCTS
-3400 E. 10th Street, Long Beach 5, Calif.
RECOMP TECHNICAL BULLETIN NO. 22.1
SUBJECT:
GENERATION OF RANDOM NUMBERS ON THE RECOMP DIGITAL
PURPOSE:
This bulletin describes techniques for generating sequences
of pseudo-random numbers with the RECOMP digital computer
and discusses methods for obtaining various statistical
and spectral properties in such sequences.
EFFECTIVE DATE:
13
RE"FERENCES:
Septembe~
1961
(a)
"Quarterly of Applied Mathematics" Vol XVI, 1958.
(b)
"Symposium on Monte Carlo Methods", edited by
H. A. Meyer, John Wiley and Sons, 1956; in particular, pp 15-28, Olga Taussky and John Todd,
"Generation and Testing of Pseudo-Random Numbers".
(c)
Martin Greenberger "Notes on a New Pseudo-Random
Number Generator" J. Assoc. Compo Mach. Vol. 8,
No.2, April 1961.
(d)
J. N. Franklin, "Note on the Equidistribution ot
Pseudo-Random Numbers, Quarterly of Applied Mathematics, Vol. XVI No.2, July 1958.
INFORMATION TO:
All Concerned
WRITTEN BY:
Robert J. Doyle
System Integration
Advanced Systems
Auto netic 8
REVISED DATE:
26 February 1962
Copyrifht 1961
Auto netics Industrial Pro ducts
A
COMPUTE~
Div. of North American Aviati.on, Inc.
r~ng Beach, Calif.
RECOMP TECHNICAL
BULLF:Tn~
NO. 22
PAGE ONE
-- - - - - - - - - - - - - - - - - - - - - - - - -
In system analysis work there arises from time to time a need for sequences
of random numbers, to simulate, e.g., the effects of noise and errors of
a random nature on system performance; and, of course, sue h sequences are
essential to the use of Monte Carlo techniques. This memorandum will discuss
some techniques for generating sequences of numbers which are suitable for
these puproses, and will descr:ibe some experiment·s that have been conducted
to studY the nature of such sequences. Although the following discussion will
be limited to application to Autonetics' REC0HP digital computer, the basic
ideas are certainly applicable to digital computation in general.
A conventional digital computer such as RECOJ'!P is, of course, incapable of
performing a truly random process; all of its operations are deterministic.
However, there exists a rather convenient method of generating a sequence of
numbers which, from the standpoint of the user are (through his ignorance,
i f you will) unpredictabl e and in this sense are pseudo-random.
By a 1?seudo~.
random sequence we mean a previously determined sequence which is used to
simulate a random sequence; however, in the discussion that follows the prefix IIpseudo" will be omitted l-lhen we refer to such sequences.
The mathod for generating this sequence is as follows:
greater than one and let Xo be a fraction
o~
xo~
Let N be an intefer
1
Define
r NXk-1
=- fractional part of
Then the sequence
2
l_1
Xk) is uniformly distributed between zero and one.
?
That is, the probability density function
~l
p(x)
lo
otherwise
To generate this random sequence on RECOHP 'We store the fraction x at
a binary scale of zero and the integer N at a binary scale of 39. Then
if' we multiply N by x we have the fractional part of the product, which
is the new x, in the R register. The sequence of commands is '.
CLA
x
MPY
N
XAR
STO
(exchange A & R registers)
x
PAGE TWO
RECOMP TECHNICAL BULLETIN NO. 22
~
-- - - - - - - - -- --- --- - - - -- - -- -~
~
~
~
~
The simplicity of this method is apparent. In practice it is recommended
that X • 2-3~ and that an odd power ot 3 or 5 be selected tor N. Different
o will ot course provide
- -sequences.
-choices
different
It is best to select
the largest odd power of 3 or 5 that can be contained in 39 bits. For further
discussion on this point, as well as the mathematical nature of the pseudorandom sequence, see references (b) and (c). A convenient method of obtaining
different sequences is to employ two generators with different odd powers otisay, 5 tor N. A member of the first sequence is selected, with an element of'
chance, by throwing a sense switch, to be used as the starting number for the
second sequence which provides the random numbers for the problem. A brief
table of odd pOWers of 3 and 5 in command fonnat is given in AppendixB.
In a practical application we are concerned with two characteristics of the
random ~quence. One of these is the distribution of the random numbers. As
assertea above the members of the random sequence are uniformly distributed
between zero and one, and a proof of this fact may be found in reference (d).
Figure 1 shows the actual distribution of a sample of 1024 numbers generated
in this manner.
A second characteristic of interest is the sequencing of the numbers, or more
precisely, if the sequence is thought of as a random time series, the power
spectral density of the series. In this regard experimental evidence indicates
that the spectral density is "whiten or uniform over all frequencies. (Of
course, as in all digital computer work, the spectral content is band limited
in a real time sense, by the sampling frequency, or the rate at which the
numbers are generated.) Another way of considering this characteristic which
does not depend on any concept of time is to state that the menbers of the
sequence are statistically independent of one another. To demonstrate this
fact an lt autocorre1ation" function was computed.
N
• 012 • • •
K • 1
Figure 2 shows an actual example of this computation on a sample of 1024
numbers. (The numbers were shifted first by subtracting one-half to lie
between plus and minus one-halt.) From this figure it is apparent that for
one or more shifts the numbers are uncorre1ated.
An important consequence of the independence of the members of the sequence
is that it permits the use of a single random number generator to provide
numbers for several applications in the same problem.
1=a
1
I~
1
t-3
~
~
• H
1
~.
I~
I~
11-3
H
1 Z
12:
t- --
,Yo
....
i\io..~
-- - - -
.~-
.......
~~
,-
I
,.~
'".
-
~",14
.
,.
I
-,;.:
I\)
II\)
O.~
I
i
,
.. 0·5
-0.4-
Figure 1.
-0.3
-o.z.
~JI4;~""'"
-0. f
SampIe Distribution of 10
o
•
"
II
0 0
Random Nll IIlbers.
ODe
0.06
~ -:=,0 I
) ;>
0
.....
..
"'1
31
I\)
I\)
with l
1 •
.-
..•
5
'!
t
,
1 t
10
• •
•
uniformly distrjbuted between -~ and
• 1 I J tt i
La
;.:>
~
I
1
.. ,, l
z-S
,,
t
3b
l
..
+!
'C
L
Figure 2.
Autocorrelation Function of 1024 Random Numbers.
l:g
10
txJ
I~
~
'I
RECOMP TECHNICAL BULLETIN NO. 22
PAC'-E FIVE
-- - - -
Thus, we have available a simple method of generating a random sequence whose
members are uniformly distributed between ·zero and one and are independent of
one another or "white". Other rectangular distributions may be easily obtained
by multiplying by a scale factor and adding a bias. For example, suppose it
. is desired to select at random an integer bet't~een 1 ann 52. We simply gener ate
a random number, multiply by 52, add 1, and take the integral part of the answer
as the desired number.
However, distributions other than rectangular are often required. For example,
failure rate is often characterized by an exponential distribution, system
errors are frequently considered to have gaussian distributions; other random
events may have a Poisson distribution. How may other distributions be obtained from a rectangular distribution?
If x is uniformly distributed between zero and one and if the probability
,density functio n p ( t) has the proper tie s
/" ~
p (t) ~ 0
I, p
and
(t) dt
= 1
./ _1,>tI&>
then the random variable
z
defined by the relation
z
x
=
(
\
(1)
p(t) dt
,,}
-~
has the probability distribution function
z
p (zo)
=J _
p (t)
dt
and hence the probability density function
For Pro bability
p (z).
Sz
<...
{
= Probability
S
Zo
=
_
since
tx!:
x
p (t) dt
o-!" f(t- ~n)2
Pn(t)dt
-00
so that
t1n
has a zero mean and unit varlance.
For N - 2 the distribution is triangular shaped and of limited interest.
N • 3 evaluation of the convolution integral gives
J-
2
u
o ~'ul ~ 3
8
P (u)
3
-
lu I
(3 -
with xi'
2
+
1· 1, 2, 3,
given in Figure 3.
)2 1~"
lu 1-: 3
(3)
16
o
where u -2 (Xl + x
For
3~
luI
x3 ) - 3
distributed according to (2).
A plOt of P3 (u) is
For comparison, a plot of the gaussian distribution
·1
r(u)··Vi~
is given on the same figure.
e
From this figure it is seen that the distribution
-
-
I~
10
o
I~
:~: l
0·4
Ii
LA. .:=
Z (X,.-f 'IZs of )(3) - 3
OL. ~ {, I
OTt.lERWI>£"
0.3
IH
o
I~
I
I~
f:"'4
IS:;
11-3
I~
I
.~
I
•
o
0.2..
0-1
I
I .'
I:
Figure 3.
Comparison of Distribution P3 (u) 'With Gaussian.
I
I. ~
10
tzJ
I
.~
:;
RECCMP TECHNICAL BULLETIN NO. 22
-----
-- - - --- - - - - - - --
T~JELVE
PAGE
~
- - - - - - - - - - - -- - ~ ~
of u is a very good approximation to the gaussian. In fact, it would be
difficult to distinguish between samples from the two distributions unless
an extremely large sample were taken. Figure 4 shows the actual distribution of
numbers generated according to equation (4). In this
figure the area of the rectangles equals the fraction of the sample falling
in the corresponding interval. The gaussian is also plotted on this figure
for comparison.
,000
This technique lends itself readily to digital computation. A subroutine for
generating "approximate gaussian" random numbers in this fashion is given in
Appendix A. As mentioned, above, these numbers have the distribution given
by (3) with zero mean and unit variance. To simulate the gaussian random
variable z with mean ~l
I J
" , ,let
z and variance I-""!'
~ Z
z
O'u.
z
-
+
It should be noted that members of the resulting gaussi.an random sequeooe
are also independent of one another or "white".
An even better approximation may be obtained by combining four of the uniformly distributed numbers. For N equal 4, evaluation of the convolution
integral yields
(" 4
13' - 2
iK3'
2
u +lu/
3
i
•
where
r::1
u-13
i
l
(2
)3
1
-
54
I u/
)3
.-:-\
o
~.l
xi
2
,1 3 ~ lu I
-~
with Xi' 1 • 1, 2, 3, 4, distributed according to (2). As before the distr.lbution has been scaled to have a zero mean and unit variame. Figure, shows
a plot of P4 (u) with the gaussi. an for comparison.
Appendix C provides a tawlation of the density functions P3
together with their respective cumulative distributions.
(u) and P4
(u)
.::0
t%J
1(')
9
I~
11-3
ItxJ
.~
H
Q
>
t"4
Sample Size Sample Hean
Sample Variance
/
:ft.'
.....:/I.'~~~..
f
..
-
\
\'-~'
.. ~\
'
-'
"",.-,.,.---
'.
P3 (u) Sample Distribution.
-0.0276
0.9979
~
I~
H
I~
.Z
o
I
\.
Figure h.
~
,000
•
I
'1\)
•
I'\)
0.2
o. f
1.0'
I~
I~
Figure
S. Gonparison of Distribution P4 (u) with Gaussian.
I
t:r:J
'"1j.
:~
1-:3
1t:t:J
I~
I
•
I
REcorU' TECHNICAL BULlE TP'T NO.
22
PAGE F'IFTEf.N
Another technique that j.s useful in providing a distribution that, although
not gaussian, favors small numbers over large and thus may be adequate for
some purposes, is to simply multinly two of the uniformly distributed numbers.
If xl' x 2 are distributed according to
~ ~
I
i
= 1,
(,
2
then the random variable
-1 __ xi -_ 1
otherwise
0
z = x x
1 2
has the distribution
-1 .__ z '._ 1
p(z)
=
o
Also the random variable
y
(
p(y)
•
=
1
\
4;y.
,l
othen-Jise
xl I xII has the distribution
-1",- Y ...,.1
J..
'~
otherwise
0
\...
,
Random variables such as these have the advantafe of being computed rather
easily.
As a final subject, we will briefly' consider the case where a random sequence
is required with a spectral density other than white. For example, it might
be required to constrain the sequence so that it does not change value too
rapidly or in other words, suppress the high frequency components in the sequence.
To achieve this end it is necessary to run the ttwhite" sequence through a lo'Wpass filter.
If the input X (t) to a filter with transfer function H (jw) is white, i.e.,
has power spectral density,
S
x
(jw)· S (0)
x
then the power spectral density of the output y (t)
S (jw) ·iH (jw)
y
i
2 S (0)
x
is
RECOMP TECHNICAL BULLF:TIN NO. 22
PAGE SIXTEEN
or in other words, the output spectral content is determined by the filter
characteristic. If the input to a line ar filter has a gaussian distribution
then the output will also be gaussian. It is then only necessary to determine
the mean and variance of the output in order to completely characterize the
output distribution. Well known techniques are available for the design of
digit~l filters and thus it is possible to generate gaussian random numbers
with a desired spectral content.
To demonstrate this technique a simple first order lag filter was programmed
a..l1d fed with a white gaussian input. The distribution and autocorrelation
function of the output were then computed. Suc,h a filter has t~e characteristic
=
H(jw)
a
a + jw
and impulse response
h(t)
=
where a is the so-called corner frequency.
is therefore
S
The output spectral density
(0)
x
The autocorrelation ,function of the output(the inverse transform of
has the form
S (jw)
y
(8)
where <-::r y is the variance
0
f the output.
To derive the difference equation defining the d;f!i-tal filter, we use the
fact that the output is the convolution of the input with the filter i.1tIpulse
response,
yet)
=
5
'to
t
=
o
h(t - t l > x(tt) dt'
ae
-a( t-t' )
x(tt) dt'
REOOMP TECHNICAL BULLETIN NO. 22
PAC·E SEVFNT2}!J\J
To evaluate this integral numerically we take an integration step A t
and assume x (t) is constant over this interval, thus
xC t)
The xn
a
(n-l)T ...... t ~'. nT
Xn
n
= 1,
=T
2, •••
be the input white p:aussian random sequence, 'With zero mean and
~ill
unit variance.
Now
(n+l)T
Yn+l
= y(fu+l)T)
= e
= e
-a(n+l)T
(
j
ae
at'
xC t
I
)dt I
0
nT
-at
-anT:/""
)"1
e
or
~
uo+l
= e -aT
Yn
+
( 1 - e -aT) xn+l
Equation (9) is the difference equation that defi~es the filter.
both sides of (9) we see that the output mean
or
..,....2 =
t/ Y
-aT
I - e
1 + e- aT
2
,. 'f" x
By averaging
RECOMP TECHNICAL IDILETlN NO. 22
- - -- - - - - --- - - - - - - - - - - - - - - - -
PAG.E
~
-
l.i'! G:-ITIi:EN
- -- -- -- --
~ ~
From equations (8) and (10) the autocorrelation function of the output is
1 - e
CC)
R
y
for
~
= 0,
=
1 + e
-aT
e-'CaT
-aT
1, 2, • • •
As an example of this computation we let
aT =
0.4
This gives
2
~.,'"
y
=
.191
Figure 6 shows the distribution of the output (normalized to have unit variance)
and Figure 1 shows the output autocorrelation function. One could apply Fourier
techniques to determine the output spectral content. However, from the exponential nature of the output autocorrelation f~~ction, it is clear that the output
has the desired spectral density.
I~
18
I~
:~
I~
IH
';\,
/
...
"
~
::
/'
1E=i
It'"
t'1j
1'-3
H
IZ
IZ
o
I
Ie
I
I\)
II\)
"
I
I- .
1
~3 .. 0
-Z.'S
Figure 6.
Output Distribution, Filtered Gaussian Random Numberse
.
.~
.
(")
o
I~
11-3
It.z:j
o
.zo
.~
IH
(")
I~
.z
o
•
I\)
If\)
I .
~..•.."'",
~.'
..
I
" ....." ....
~
.
• ·;·.· .....·•• ~( ..-'W:'!.;·"q ••
Figure 7.
Output Autocorrelation Function, Filtered Gaussian Random Numbers.
~(
~.
II
.:.''"'"''.".,.*. . . . . ,. . ".
..'. \3
:
, ....", ............. , -....... ,.. ··,.."~,..~·'"'·"··Ir.'···~,,,·f·.'·. ··.,..-···~,,· ••...~.''' ..
b
t ••
RECO~1P TECm~ICAL
BULLETIN NO. 22
PAGE Tl:AlENTY-ONE
- - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - ~
Appendix A
"Approximate - Gaussian" Random Number
Generator Subroutine
Enter Subroutine with + TRA 0006.0
Exit to next location with gaussian random number in A and R registers
0006.0
+
+
SAX 7760.0 +
CTV 0020.0 +
0010.0
+
+
+
+
+
ADD
+
A~D
7773.0
77TI.O
0000.0
0001.0
7774.0
7776.0
7777.0
777h.O
+
+
+
+
CIA
nLA
STO
FAD
7777.0
7775.0
()027.0
7774.0
CI.JA
XA.~
ARS
STO
+ MPY
+ STO
0020.0
CTL
TRA
0010.0
7760.0
+
srA
+
~1PY
+
STO
AnD
7773.1
7776.0
7777.0
7774.0
7777.0
0000.0
0001.0
7174.0
+
+.
+
+
+
+
+
+
+
eLA
XAR
ARS
STO
7776.0
0000.0
ARS 0001.0
TR.A 0000.1
MPY
XAR
-3 at Binary scale of 2
+2 at Binary scale of 39
N at Binary scale of 39
Xo
= +1
at Binary scale of 39
Notes:
(1)
(2)
It is recommended that N be an odd power of 3 or
r'~in
memory addresses are underlined.
5.
~
--
RECOO TECHNICAL BULLETIN NO.
22
PAGE· TWENTY-TWO
- - -- - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - -- - - - -Odd Powers of 3 and
Appendix B
5
RECOMP users may find the following list of odd 'pawers ot 3 and 5,
Command format,' usetul in programming random number generators a
323
21
3
19
3
17
3
1, .
3
$1,
•
+
1275321
+
67204$1
•
+
011,731
+
424$311
•
+
0010,20
6,47551
•
+
0000751
2413411
•
+
0000061
+
27446Sl
•
+
0343271
+
,223061
~3
•
+
0011000
2347121
sll
,9
-
•
+
0000270
+
103$,61
•
+
0000001
+
,632621
!!:!
RE~Or1P
TEC:"lN I CAL BUTLH:TDT NO. 22
- - -- - - -- -- - -- - - - - - - - - - - - - - - -- -- - - - - - - - - -- -
Appendix C
Probability Density Function and Cumulative
.1..
,tt...
j,. P3(x)dX
u
~)' P4(x)dx
P4(U)
~"J
.0
.1
.2
.3
.4
.5
.6
.7
.8
.9
1.0
1.1
1.2
1.3
1.L
1.,
1.6
1.7
1.8
1.9
2.0
2.1
2.2
2.3
2.1+
2.5
2.6
2.7
2.8
2.9
3.0
3.1
3.2
3.3
3.h
3.5
3.6
+.37500
+.37375
+.37000
+.36375
+.35500
+.34375
+.330UO
+.31375
+.29500
+.27375
+.25000
+.22563
+.20250
+.18063
+.16000
+.lu063
+.12250
+.10563
+.90000
+.75625
+.62500
+.,0625
+.40000
+.30625
+.22500
+.15625
+.10000
+.56250
+.25000
+.62500
+.84703
+.00000
+.00000
+.00000
+.00000
+.00000
+.00000
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+ 0
+0
+0
+0
+0
+0
- 1
- 1
- 1
- 1
- 1
- 1
- 1
- 1
- 1
- 2
- 2
- 3
-21
+0
+0
+0
+0
+0
+a
")
+.00000
+.37458
+.7}J.667
+.11137
+.14733
+.18229
+.21~00
+.24821
+.27867
+.30712
+.33333
+.35710
+.378,0
+.39765
+.41467
+.42969
+.44283
+.45423
+.h6400
+.47227
+.47917
+.48h81
+.48933
+.49285
+.49,,0
+.49740
+.49867
+.h9944
+.49983
+.49998
+.50000
+.10000
+.10000
+.10000
+.10000
+.10000
+.10000
+0
- 1
- 1
+0
+0
+a
+0
+0
+0
+0
+0
+0
+0
+a
+0
+0
+0
+0
+0
+0
+0
+0
+0
+a
+0
+0
+0
+a
+0
+a
+0
+1
+1
+1
+1
+1
+ 1
+.66667
+.66343
+.65L.IO
+.63926
+.61949
+.59536
+.56745
+.5363h
+.50260
+.46681
+.42956
+.39141
+.35294
+.31L.74
+.27737
+.2h143
+.20747
+.17609
+.It,781
+.12273
+.10067
+.81h15
+.64791
+.50599
+.38647
+.28743
+.20695
+.14309
+.93944
+.57576
+.32063
+.15482
+.59085
+.14174
+.8h48h
+.00000
+.00000
+0
+ 0
+ 0
+0
+0
+0
+ 0
+0
+0
+
a
+0
+0
+0
+0
+0
+0
+0
+0
+ 0
+0
+0
- 1
- 1
- 1
- 1
- 1
- 1
- 1
- 2
- 2
- 2
- 2
- 3
- 3
- 5
+0
+0
+.00000
+.38427
+.76489
+.11385
+0
- 1
- 1
+0
+.15C>21 + 0
+.113530 + 0
+.21:988 + 0
+.25076 + 0
+.28076 + 0
+.30C376 + ')
+0
+.33464
+.35834
+.37983
+.39910
+.41619
+.43116
+.h4h10
+.45",16
+.46450
+.47229
+.h7873
+.48397
+.48818
+.49150
+.l.t9406
+.49600
+.49742
+.49842
+.1.9910
+.49953
+.l.t9979
+.49992
+.49998
+.50000
+. ,0000
+.,0000
+0
+0
+0
+0
+0
+0
+0
+0
+ 0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+0
+ 0
+
a
+.,0000 + 0
RECOMP TECHNICAL BULLETIN NO.
PAGE
22
REFERENCES
a)
"Quarterly of Applied
Mathema~icsn Vol XVI,
1958
~1ENTY-FOUR
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.3 Linearized : No XMP Toolkit : Adobe XMP Core 4.2.1-c043 52.372728, 2009/01/18-15:56:37 Create Date : 2010:05:09 17:26:29-08:00 Modify Date : 2010:05:09 17:33:15-07:00 Metadata Date : 2010:05:09 17:33:15-07:00 Producer : Adobe Acrobat 9.32 Paper Capture Plug-in Format : application/pdf Document ID : uuid:22365ac8-7a12-4729-8c20-8c2a44857efe Instance ID : uuid:ce8015af-a8ec-4994-b392-b09790a693cc Page Layout : SinglePage Page Mode : UseNone Page Count : 25EXIF Metadata provided by EXIF.tools