CSC 245 Laboratory Exercise 7 – Analyzing RND( )



CSC 245 Laboratory Exercise 7 – Analyzing RND( )

In this laboratory exercise you will evaluate the random number generator in the random.adb package. We will test to see if the distribution of values is uniform by comparing the expected number of repeating values to the actual number obtained experimentally.

Preparation – The generation of random numbers using a computer is one of the most important computational methods you will study. Digital computers are completely deterministic. This means that there is no uncertainty or randomness possible in the execution of a program on a digital computer. So how do we generate random numbers using a computer? The short answer is, we don't.

Actually we can generate sequences of numbers that appear to be random. In other words we can write computer programs to generate pseudo-random numbers that are useful for many applications needing sequences of random numbers. The only requirement is that these pseudo-random sequences meet the tests for randomness that are important to our application.

In this case we will be evaluating a random number function that generates integer values in the range (0 ..2,147,483,647). We want to be certain that these values are uniformly distributed, which means that any value in the specified range is equally likely to occur each time we call the random function. If each value in the range is equally likely to occur, then the probability that we will obtain a particular value in a single trial is,

[pic] (1)

Once we have obtained a particular value, the probability that we will obtain the same value in the next trial is pi = 1/2,147,483,647. This is because there are Nmax = 2,147,483,647 equally likely values from which to choose. Assuming that we do not get a repeating value in n-1 trials, we can compute the probability that the nth value will be different from any of these by noting that it must be one of Nmax-(n-1) values. The probability that the nth value is different is therefore

[pic] (2)

In general, the probability n numbers drawn from a set of Nmax values will all be different is,

[pic] (3)

The Π symbol is a capital pi representing the product of the individual terms from i =1 to n-1, which is analogous to our use of Σ to represent summations. In our analysis, we will compare the expected number of repeating values based on Expression 3 with the actual number of repeating values obtained from the function rnd( ).

Implementation – In this laboratory you will need to implement two different procedures. The details of these are provided below:

Expected Value - Design an Ada program to compute the expected number of random values to be generated to have a 0.5 probability (50% chance) of having a repeating value. This program is an implementation of Expression 3 above. The output of this program will be the number of values n0.5 to be drawn from a set of Nmax=2,147,483,647.

Experimental Value - You will design and implement an Ada program that experimentally determines the number of repeated values in a set of n random values generated by the rnd( ) function in the random.adb package. The problem is how to keep track of over 2 billion possible values. It is recommended that you build a hash table and hash the n random values into the table, while testing for repeaters, but this is not a requirement.

The data structure for a hash table for this problem could be similar to,

numtab : constant integer := 10000;

type hashnode;

type hashlink is access hashnode;

type hashnode is

record

val : integer;

count : integer;

next : hashlink;

end record;

type hashtabletype is array (0 .. numtab - 1) of hashlink;

hashtable : hashtabletype;

Your program should output a count of the number of values drawn from rnd(Nmax-1) = before a repeating value is obtained. You will need to make sufficient measurements to demonstrate a confidence in the average count.

Analysis

Write a report comparing the expected count with the experimentally derived count for the number of values drawn before a repeating value is obtained. You report should include a discussion of the significance of your results. Your report should conclude with a statement of the validity of the random number generator rnd( ).

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download