|
This application
uses a pseudorandom number generator to generate and plot ordered pairs. You
design the generator.
The left hand side
of the screen contains your settings. The points are plotted in the square
field. The chart at the right displays the ordered pairs generated.
Your generator will
create a pseudorandom sequence, i0, i1, i2,
i3…in-1, in, of numbers. This application
will take ordered pairs (i0, i1), (i2, i3)…(in-1,
in). To plot the points in the square field, it will scale the
possible range of coordinates to the side length of the square field such
that no points are plotted outside the field.
Choosing a
Method and Setting Parameters
First, you will
choose between the two basic methods for generation of pseudorandom numbers
discussed in the How it Works section of this tutorial- the middle square
method and the linear congruence method. Next, you will set the parameters
for your generator. After this, you should enter the number of points you
want to be plotted.
The Middle
Square Method
If you use the
middle square method, the only parameter you will have to set will be the
seed value (the first value in the sequence.) The following pseudocode
describes how the application will plot N points using the middle square
method:
(Note that if the
number of digits in the seed value is odd, the application will append
another zero to the square.)
|
X
= Seed
S = number of digits in Seed
Do N times
Square = X2
Do until number of digits in
Square = S * 2
Append leading
zero to Square
Loop
If S is odd, then
Append leading
zero to Square
End If
Y = middle S digits of Square
Scaled x = X/ 10 ^ (S) * side
length of viewing field
Scaled y = Y/ 10 ^ (S) * side
length of viewing field
Plot point(Scaled x, Scaled y)
in viewing field
Square = Y2
Do until length of Square = S
* 2
Append leading
zero to Square
Loop
If S is odd then
Append leading
zero to Square
End If
X = middle S digits of Square
Loop |
|
The Linear
Congruence Method
If you use the
linear congruence method you will need to set four parameters- the seed, A,
B, and C. The following pseudocode describes how the application will plot N
points using the linear congruence method:
|
X= Seed
Do N times
Y = (A *
X + B) mod C
Scaled x
= X/C * side length of viewing field
Scaled y
= Y/C * side length of viewing field
Plot
point(Scaled x, Scaled y) in viewing field
X = (A *
Y + B) mod C
Loop |
|
Grid
Next, you will
choose whether or not to show a grid in the viewing window. The
intersections of the grid lines will represent every point within the range
of your generator. If you use the linear congruence method, it will be a C
by C grid. If you use the middle square method with an n-digit seed, it will
be a 10^n by 10^n grid. Since the grid “lines” have width, this feature is
available only when the range of the generator is less than 200.
Display Settings
This application
will plot squares to represent points. You may have the application plot
squares of alternating color or only black squares. Using black squares,
it’s easy to see if the generator starts cycling. With multicolored squares,
you can see the nature of the cycle.
You can also set the
size of the squares. A sample square appears below the size setting.
Plot the Points
To start plotting
points press the Plot button. You can pause the point generator pressing
Pause and start it again by pressing the Continue button.
Chart of Ordered
Pairs
As the points are
plotted, the each ordered pair will be displayed in the chart on the right
of the screen. The most recent point will appear at the top of the chart.
Examples – Middle
Square Method
Use a seed of 2041
to plot 200 multicolored points. What do you notice? (Keep an eye on the
lower left-hand corner of the viewing field.)
-
Use a seed of
2051 to plot 200 multicolored points. What do you notice?
-
Try 123456 with
200 multicolored points. What happens?
-
Use a seed of
12345678. How many numbers are generated before the sequence degenerates
to zero?
Examples- Linear
Congruence Method
Try the following
parameters using the linear congruence method.
Seed = 7 A =1 B=7
C=10. Show the grid. Plot 100 points.
Seed = 100 A = 100
B = 100 C =100
Seed = 100 A = 21 B
= 73 C = 100. Show the grid and use multicolored points. Plot 5 points, then
25, then 50, then 100, and then 1000.
Seed = 1 A = 5001 B
=2335 C = 32768. Use small black points. Plot several thousand points.
Famous Linear
Congruential Generators
Visual Basic
random number generator
Default Seed =
327680 A = 1140671485 B = 12820163 C =16777216
RANDU, a faulty
PRNG once widely used in the scientific community
A = 65539 B = 0 C =
2147483648
A linear
congruence generator suggested in Numerical Recipes in C
A = 1664525 B=
1013904223 C = 4294967296
Try to create a
linear congruence generator with as long a period as possible.
Hint: To get a full
period of C, your parameters must fulfill the following conditions:
1. B and C are
relatively prime
2. A-1 is divisible
by all prime factors of C.
3. A-1 is a multiple
of 4 if C is a multiple of 4
4. C is greater than
A, B, and the seed. |
