IUP Computer Science
CO 300 Spring 1999

Project #5
(Due by 5 pm on 16 April 1999)

Write an assembly language main program to analyze how good a random number generator is. Also, in a separate file write the random number generator procedure.

You will be given one FORTRAN subroutine and two C functions to help you do this task. Each of these is described below. Your main program is to call these three procedures in the course of analyzing the random number generator - they will do the majority of the work for you. The FORTRAN subroutine will call the random number generator procedure that you are to write.

MAKEARR

This FORTRAN subroutine takes four arguments: the quadword seed, the array to hold the generated random integers, the number of random integers to generate (COUNT), and the limit on the size of the random numbers (MAX), in this order. The subroutine calls RANDOM (the random number generator procedure) COUNT times and stores the resulting random integers in the array, one after another.

SORT

This C function takes two arguments: the array holding the random integer values and the number of values in the array. The function sorts the array into ascending order (lowest to highest).

MISSING

This C function takes four arguments: the array holding random integer values, the number of values in the array (COUNT), the number of missed numbers (MISSED), and the limit on the size of the values (MAX). The function examines the COUNT entries in the array (which must be in sorted order), determines how many numbers between 0 and MAX - 1 are not present in the array and stores this result in MISSED.

Your main program should do the following tasks:
  1. Prompt for and read in the number of random integers (COUNT) to generate and the limit on the size of the random integers (MAX). COUNT should be allowed to be up to 10001; MAX should be allowed to be up to 1000001. Both COUNT and MAX must be odd positive numbers - your program must insure that they are.

  2. Display (with identifying labels) COUNT, MAX, and the expected mean for the random numbers to be generated (this is 1/2 of MAX).

  3. Display a table containing the following results (with column labels) from generating COUNT random integers in the range 0 to MAX-1 five times. That is, MAKEARR, SORT, and MISSING are to be called five times each; and after calling the three each time, your program must display in table form: 
         the Lowest random integer generated; 
     the Highest random integer generated; 
     the Mean of the values generated - in floating point form
     (with 2 decimal places);
     the Median of the values generated; and 
     the Number of integers between 0 and MAX-1 that were not generated.
    The Mean is the average of the numbers generated - convert the sum and divisor to floating point form to get a floating point result, then use WRITEFL. The Median is the middle value in the sorted list of COUNT values.

The RANDOM procedure uses a standard overflow technique to produce random numbers. This procedure must take three arguments: the SEED (a quadword that initially contains zero), the limit on the size of the random numbers (MAX), and the random number generated (RN). The procedure should behave like the following C++ sketch. 

     if (SEED is 0)
     { Use the GETTIM system service to initialize 
         SEED with the system time ans use the first four
         bytes of SEED as the KERNEL }
     else
     { Produce next SEED value by using only the first 
         four bytes of SEED (the KERNEL)
       KERNEL = abs(KERNEL) * 1194211693 + 12345; }
     Compute the random number RN by doing the following
     RN = (abs(KERNEL) / 1024) % MAX;
RN will then have a random value in the range 0 to MAX - 1. Note that RANDOM changes both SEED and RN each time it is called - changing the KERNEL changes the SEED. abs(x) is the absolute value of x.

Hand in an assembler generated listing for your main program and your RANDOM procedure and a CARBONCOPY captured execution of your program in which you try several different values for COUNT and MAX. You should find that if COUNT >= 3 * MAX then the Mean, Median, and Expected Mean are all close to each other with few missing values; and as the ratio of COUNT to MAX gets smaller, the Mean, Median, and Expected Mean become more different with many missing values.

EXTRA CREDIT:
Add instructions to your program to measure the amount of time it takes to generate, sort, count themissing and display the results five times. Display this time (in ticks, hundredths of a second) as part of the results. To measure this time, you will need to use the GETJPIW system service; use the jpi$_cputim item code as illustrated in class (it returns a longword result). Don't be surprised if the execution time varies.