Consider an array a[] of type unsigned int. The length of the array is given by a parameter n, which is read at the beginning of the program. Initialize the array according to the following rule: a[0] == 0; a[i] = (a[i - 1] + x) % n, for all i > 0. Algebra tells us that whenever n and x are relatively prime, that is gcd(x, n) == 1, the whole pattern of a[] values a permutation of the numbers 0, ..., n. That is, all numbers occur exactly once. Taking x a prime number, this is guaranteed to hold for all n which are not a multiple of x.
The task is to verify this property for various n and x and to measure the time consumption. This is done by using a second unsigned integer array b[], which is used for counting the frequencies of the numbers in a[]. It is initialized at zero and in a final pass the maximum of all values in b[] is determined and printed.

Times can be measured with the following procedure:

     long dclock() {
       /* Returns the time in miliseconds */
       struct timeval  tp;
       struct timezone tzp;
       gettimeofday(&tp, &tzp);
       return 1000 * (tp.tv_sec % 1000000) + tp.tv_usec / 1000; }
   
This is not the most scientific way of measuring times, but it is simple and works quite well. In order to be able to use this routine it is necessary to include the system library "sys/time.h", which is done in the same way as the inclusion of "stdio.h".
For n you must test n = 2^k, for all k >= 12 as far as the computer allows you to solve the problem in less than 1 minute. For x you must test x = 1, 2, 4, 11, 19, 1007, 99991. The time measurement should only reflect the time for counting the frequencies of the numbers in a[], not the initialization or finding the maximum. To get stable measurements, the experiments should be repeated until the sum of the measured times exceeds 1000 ms (and then of course you must divide by the number of experiments to get the average time per experiment). Plot the resulting average time consumptions as a function of n using a doubly logarithmic scale (that is, both along the x-axis and along the y-axis the scaling is so that each factor two is one unit distance) connecting the points belonging to the same x value. Consider the developments and the differences and explain them.