(a) Write a program to determine the value of 
by numerically casting a needle
of length D on a ruled grid with spacing S as shown in Figure 1.
You must first
determine a random position (relative ruled grid as shown in Figure 1.
You must
first determine a random position (relative to a ruled line), then determine a
random angle, and thirdly, see whether the needle falls within the
ruled lines.
You may find it instructive to compute approximations for versus the
number of trials, e.g. N = 10, 100, 1,000 and 10,000.
For 
, your answer
for the fraction of time, 
, the needle falls within the grid should be
[30]:
(b) Verify the above equation.
What is the corresponding formula for 
? (Warning:
there is considerable effort involved in this derivation!)
(c) Using a needle and a piece of paper upon which you have placed a
ruled grid, perform a physical experiment to determine using the above
equation. Perform first 10, then 100, and then 1,000 trials. Comment on the
accuracy of these results relative to the accuracy of the results from the
numerical experiment. Discuss reasons for any bias apparent in the results.
For uniformly distributed real random numbers, 
, on [0,1), the average
value should be 0.5. Note that, to compute the mean and variance, we can order
the random numbers in any fashion (as both of these computations are
independent
of order). It is useful to choose to order the real, random numbers in
ascending order, and approximate the distribution in the form of a continuous
variable 
. Verify by direct integration that the average, 
, and
the
variance, 
, should be 0.5 and 0.083333, respectively, as follows:
Obtain and edit the linear congruential program ranlc.f. Supply the
additional code to compute the average and the variance. For sample sizes of
10, 100, 1,000, and 10,000, run the code and plot the errors in the average and
variance versus sample size. Discuss how the error in these quantities varies
with the sample size. Use the following parameters: 
, 
, and
.
Consider linear, congruential random number generators.
If , it is obvious
that 
is not a good candidate integer for the initial seed because it
maps to itself. In fact, if 
, a prime, then there is always a number
which maps to itself (a constant sequence), even if 
. Prove this by
finding the integer which maps to itself, and which does not appear in the full
period sequence of length 
for the following linear, congruential
generators:
For the linear, congruential generator 
, generate all the
possible sequences by varying the initial seed from 0 and 15. How many
independent (i.e. not cyclical shifts of one another) sequences are there? Is
there a pattern observable in even versus odd integers? Discuss possible
reasons
for this behavior.
On a Cray supercomputer running UNICOS, obtain the manual page on its intrinsic random number generator by typing at the UNICOS prompt (%) ``man ranf > ranf.doc''. Read the file ranf.doc to see how to set and get the seed for ranf. Given that ranf is a multiplicative, congruential generator (c = 0) using 46 bits - get the initial seed; discuss it in terms of cycle length. Set the seed to 1, and call ranf to obtain a new seed. Get and print out the new seed; this new seed is the multiplier of the generator. Discuss the multiplier in the context of the cycle length. Print out the first ten random integers in decimal and hexadecimal format, and the corresponding random real numbers using an f20.16 format.
Modify the ranlc.f code to output 
pairs of numbers as
, 
, 
, etc. Plot
these discrete points for the following cases:
Complete Exercise 6 above to determine the parameters 
and 
(probably
) of Cray's ranf(). Develop a vectorized version of ranf()
by creating a vector of successive multiples of the coefficient . For a
vector length of 64, for example, you will need a vector of (
). Race your vectorized version of ranf() vs. Cray's
ranf(), and see how close you can come to their execution time. To do
this, you will have to generate long vectors of random numbers, and use them
elsewhere in the code. Use second() to obtain elapsed CPU time.
For the LCG, 
, where ,
determine 
and 
so that
, resulting in a leap-ahead of
places on the original LCG cycle.
Use the code ranlf.f to generate random numbers. Modify the code to
print
out pairs of random numbers on [0,1) and display them as points as 
vs. for 4,095 points (4,096 random numbers).
(a) Using 
(
varies from 0 to 16), and 
, select a
subtractive generator. Use an initial seed of 37 to generate the initial
state.
Compare the display to those of Figures 6a-f in Section 4
which were generated using LCG
generators.
(b) Select different values for , but keep 
fixed at 17. Use the
parameters as in (a) above. Generate plots as above in (a). What do you
observe about the uniformity of the random numbers and their correlation?
Consider the Fibonacci generator 
.
(a) Draw a shift register diagram, similar to Figure 10, to represent , the action of this generator.
(b) How long is the period, 
, of this generator?
(c) How many distinct cycles does this generator have?
(d) Using the information for this generator in Table 4, initialize, in canonical form, every cycle for this generator, and generate each full cycle.
(e) Suppose the generator were initialized with the values, 
, 
, and 
. If the generator were advanced for a full cycle,
which of the ``canonical'' cycles generated in part (d) would be the same as
this new one? How many advances of the generator did you need to determine
this?
(f) Would parts (a) through (e) be fun to do if the generator changed
only slightly, from to 
?
What is the value of for ? How many distinct
cycles does it have?
Using a computer and your favorite programming language, go through steps (a)
through (e) as in Exercise 11, above, for the generator 
. What
about part (f), i.e., changing to 
? What would that
change do to the number of cycles and to ?
