CS1101C Lab 3 (Even Week)

Fibonacci Number Density

The deadline for this lab question is Friday 27 October 2006, 23:59:59 hours.

The name of your C program file must be called fibdense.c, files with any other name will not be marked.

Background

Look at the following infinite sequence of numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

The first two numbers are one. Each subsequent number is simply the sum of the immediate previous two numbers. Any number in the above infinite sequence is called a Fibonacci number.

Suppose we are given a range of integers from one to 100 inclusive. How many of those integers are Fibonacci numbers? This is known as the density of Fibs and we convert that to percentage.

There are two ways to calculate the density of Fibs in a certain range. We can do it precisely by testing if each of the numbers in the range is a Fibonacci number. This is the most precise method, but it is also the slowest.

The other method is by sampling. We take x random integers in the range and see how many of those are Fibonacci numbers. This is a faster method, but the density calculate is only an approximation.

We will implement both methods in our program.

Implementation

You will be provided with an input file consisting one or more lines. Each line contains the parameters for each experiment. Each line consists of a random number seed, the lower limit of the range, the upper limit of the range, and the number of samples. A typical line from the input file consist of four integers separated by blank spaces as shown below:

23129 100 10000 1000

The explanation for each number is given as follows:

23129 Random number seed
100 Lower limit of range (inclusive)
10000 Upper limit of range (inclusive)
1000 Number of samples (x)

The random number seed should be initialized to the value shown (by using the srand function) at the beginning of each experiment.

Note that there is no relationship between the range and the number of samples.

Input File

Assume that the text input file is always called fibs1.txt. This sample input file contains data for five experiments:

32251 1 100 100
32252 1 1000 1000
32253 1 10000 10000
32254 1 100000 100000
32255 1 1000000 1000000

We will test your program with other experiment data, so your program must work for the general case, and not just only for the sample input file given.

Sample Run

The following shows a sample run for the input file fibs1.txt. Actual values for the experiment results have been replaced with x’s (the number of x’s does not signify the number of digits). Display the percentage to six decimal places. To print a % sign in a printf statement, use %%.

You are reminded to follow the sample outcome exactly, else marks will be deducted.

Seed: 32251, lower: 1, upper: 100,
      sampled fibs: xx, samples: 100, percentage: xx.xxxxxx%
      num fibs: xx, total: 100, percentage: xx.xxxxxx%
Seed: 32252, lower: 1, upper: 1000,
      sampled fibs: xxx, samples: 1000, percentage: xx.xxxxxx%
      num fibs: xxx, total: 1000, percentage: xx.xxxxxx%
Seed: 32253, lower: 1, upper: 10000,
      sampled fibs: xxxx, samples: 10000, percentage: xx.xxxxxx%
      num fibs: xxxx, total: 10000, percentage: xx.xxxxxx%
Seed: 32254, lower: 1, upper: 100000,
      sampled fibs: xxxxx, samples: 100000, percentage: xx.xxxxxx%
      num fibs: xxxxx, total: 100000, percentage: xx.xxxxxx%
Seed: 32255, lower: 1, upper: 1000000,
      sampled fibs: xxxxxx, samples: 1000000, percentage: xx.xxxxxx%
      num fibs: xxxxxx, total: 1000000, percentage: xx.xxxxxx%

Take Note

Assume that the text input file always exists and contains only valid integers.
Assume that all the numbers in the input file will never be greater than 1,000,000 or smaller than 1.
Do not use any arrays in your program.

Tips

To print a % sign in a printf statement, use %%.

Use the following rand_int2 function to generate random numbers.

/*---------------------------------------------------*/
/*  This function generates a random integer         */
/*  between specified limits a and b (a<b).          */
int rand_int2(int a, int b)
{
    if (RAND_MAX == 32767)
        return (rand()<<15^rand())%(b-a+1) + a;
    else
        return rand()%(b-a+1) + a;
}
/*---------------------------------------------------*/

If you have not yet read the article How NOT to Go About a Programming Assignment (which was found in the IVLE workbin), read it now.
This may be the most complicated program you have ever designed. Go to the drawing board and plan your program. Think about the individual modules you want using the divide-and-conquer strategy. Write and test each module / function individually. Do not ever write the complete program, and then start compiling / running / testing it. You will end up with numerous compilation and logic errors which will take a long time to fix.
You should probably not use the input file given when testing your program for the first time; you should create your own input file (by using the Unix command “vim fibs1.txt”) with manageable values and small number of experiments. When you are confident that your program is working for small number of experiments, increase it.
You should use many printf statements to give more information of what your program is doing exactly. You should print out as much debugging information as you need; then before submission, comment out the debugging information.

Reflect

What is the use of Fibonacci numbers?

Ponder

Is your sampling accurate? How can you ensure higher sampling accuracy?

Slightly Advanced Pondering

If your sampling is accurate, what does it indicate about the numbers generated by the random number generator?

More Advanced Pondering

When compiling and executing the program in sunfire, try using the following rand_int function instead. Does it work? Why or why not?

/*---------------------------------------------------*/
/*  This function generates a random integer         */
/*  between specified limits a and b (a<b).          */
int rand_int(int a, int b)
{
    return rand()%(b-a+1) + a;
}
/*---------------------------------------------------*/

Super Advanced Pondering

Write your own Pseudo Random Number Generator (PRNG).

Ultra Advanced Pondering

Write your own True Random Number Generator (TRNG) based on real life random data. Test the quality of your random numbers generated by your RNG. Google is your friend.

This document, index.html, has been accessed 31 times since 25-Jun-24 11:57:13 +08. This is the 1st time it has been accessed today.

A total of 21 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 9 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.

`23129`	Random number seed
`100`	Lower limit of range (inclusive)
`10000`	Upper limit of range (inclusive)
`1000`	Number of samples (x)