Programming Assignment I
Due on Friday, September 25, 2020 @ 11pm
50 points
This is a warm-up simple programming assignment using only Unix system calls fork(), wait() and exit().
f1 = f2 = 1Use THIS recursive formula to compute the n-th Fibonacci number.
fn = fn-1 + fn-2 if n > 2
We may use a program to simulate this needle throwing process. For simplicity, let L = G = 1.
We need two random numbers:
In this way, your program loops r times. In each iteration, your program uses the above formula to throw a needle, and checks whether the needle crosses a dividing line. If the needle crosses a dividing line t times, t/r is an approximation of the exact probability. In fact, if r is very large, the simulated result would be very close to the exact result. In our case, since L = G = 1, the result for large r should be close to 2/π = 0.63661..... Use acos(-1.0) to obtain the value of π.
This means the area between the sin(x) function and the x-axis is 2. This area is completely enclosed in a rectangular area with length π and height 1 as shown in the figure below. The area of this rectangle is π×1 = π.
If we randomly pick s points in the rectangle and find out t of them in the area of the sin(x) function, then the ratio t/s suggests that the area under sin(x) is t/s of the rectangle. Therefore, (t/s)×π should be close to 2. Here is what your program must do.
In this component, you are to write a program to find the value of e based on the above formula. This is a simple program. You just follow the steps below:
However, your program must print the results of the first 10 values for i = 1, 2, 3, ..., 10. Therefore, the possible values of i should be 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 32, 64, 128, 256, ....
./prog1 m n r swhere m, n, r and s are four positive integers. You can only assume that your program will be compiled in the C89 standard.
| You must use recursion to compute fn. Moreover, the parent and its four child processes must run concurrently. Violating these rules you will receive zero point for this programming assignment. |
Here, m, n, r and s are four positive integers. There are always four arguments and they are always correct. Moreover, m, r and s are usually very large../prog1 m n r s
Suppose the command line is
Then, your program should (1) compute the 10-th Fibonacci number, (2) simulate throwing a needle 100000 times, (3) use 200000 points to compute the area between the sin(x) function and the x-axis in the range of 0 and π. and (4) use 73000000000000000 as the maximum possible exponent in the computation of Euler's number../prog1 73000000000000000 10 100000 200000
The Fibonacci process should have its output as follows:
All output from this process starts on column 7 (i.e., 6 leading spaces). Since the computed Fibonacci number may be very large, use %ld to print the computed result.Fibonacci Process Started Input Number 10 Fibonacci Number f(10) is 55 Fibonacci Process Exits
The Buffon's Needle process should have its output as follows:
Since the output value is always in the range of 0 and 1, use 5 positions after the decimal point for printing. All output from this process starts on column 10 (i.e., 9 leading spaces).Buffon's Needle Process Started Input Number 100000 Estimated Probability is 0.63607 Buffon's Needle Process Exits
The integration (i.e. third) process should have its output as follows:
All output from this process starts on column 13 (i.e., 12 leading spaces).Integration Process Started Input Number 200000 Total Hit 127498 Estimated Area is 2.0027339 Integration Process Exits
Note that the results of Buffon's Needle problem and the integration problem may be slightly different from the output shown here even with the same r and s because random numbers are used.
The Euler's number computation process should have its output as follows:
Approximation of e Process Started
Maximum of the Exponent 73000000000000000
1 2.000000000000000 0.718281828459045
2 2.250000000000000 0.468281828459045
3 2.370370370370370 0.347911458088675
4 2.441406250000000 0.276875578459045
5 2.488319999999999 0.229961828459046
6 2.521626371742113 0.196655456716932
7 2.546499697040712 0.171782131418333
8 2.565784513950348 0.152497314508697
9 2.581174791713198 0.137107036745847
10 2.593742460100002 0.124539368359043
16 2.637928497366600 0.080353331092445
32 2.676990129378183 0.041291699080862
64 2.697344952565099 0.020936875893946
128 2.707739019688021 0.010542808771024
256 2.712991624253434 0.005290204205611
512 2.715632000168991 0.002649828290054
1024 2.716955729466436 0.001326098992609
2048 2.717618482336880 0.000663346122165
4096 2.717950081189666 0.000331747269379
8192 2.718115936265797 0.000165892193248
16384 2.718198877721971 0.000082950737074
32768 2.718240351930294 0.000041476528751
65536 2.718261089904603 0.000020738554442
131072 2.718271459109306 0.000010369349739
262144 2.718276643766046 0.000005184692999
524288 2.718279236108013 0.000002592351032
1048576 2.718280532282396 0.000001296176649
2097152 2.718281180370437 0.000000648088608
4194304 2.718281504414671 0.000000324044374
8388608 2.718281666436840 0.000000162022205
16777216 2.718281747447938 0.000000081011107
33554432 2.718281787953491 0.000000040505554
67108864 2.718281808206268 0.000000020252777
134217728 2.718281818332656 0.000000010126389
268435456 2.718281823395851 0.000000005063194
536870912 2.718281825927448 0.000000002531597
1073741824 2.718281827193247 0.000000001265799
2147483648 2.718281827826146 0.000000000632899
4294967296 2.718281828142596 0.000000000316450
8589934592 2.718281828300821 0.000000000158225
17179869184 2.718281828379933 0.000000000079112
34359738368 2.718281828419489 0.000000000039556
68719476736 2.718281828439267 0.000000000019778
137438953472 2.718281828449156 0.000000000009889
274877906944 2.718281828454101 0.000000000004944
549755813888 2.718281828456573 0.000000000002472
1099511627776 2.718281828457809 0.000000000001236
2199023255552 2.718281828458427 0.000000000000618
4398046511104 2.718281828458736 0.000000000000309
8796093022208 2.718281828458891 0.000000000000155
17592186044416 2.718281828458968 0.000000000000077
35184372088832 2.718281828459006 0.000000000000039
70368744177664 2.718281828459026 0.000000000000019
140737488355328 2.718281828459036 0.000000000000009
281474976710656 2.718281828459040 0.000000000000005
562949953421312 2.718281828459043 0.000000000000002
1125899906842624 2.718281828459044 0.000000000000001
2251799813685248 2.718281828459045 0.000000000000000
4503599627370496 2.718281828459045 0.000000000000000
9007199254740992 1.000000000000000 1.718281828459045
18014398509481984 1.000000000000000 1.718281828459045
36028797018963968 1.000000000000000 1.718281828459045
72057594037927936 1.000000000000000 1.718281828459045
All output from this process starts on column 4
(i.e., 3 leading spaces).
The first column shows the value of i, the second has the value of (1+1/i)i, and the third shows the absolute difference between the calculated value of e and the actual value of e. You can always get a true value of e with the C math function exp(1.0) The above sample output has m being 73000000000000000. Because the value of n can be very large, the first column used %18lu, meaning n is a unsigned long integer. The second and third columns should allow the printing of at least 7 to 15 digits, meaning floating point calculations are done in double. You may use your own format, but keep in mind that the output must be readable as shown above. You may find the largest value of unsigned long on any system in C's header file <limits.h>.
If you examine the above result, you should be able to see that the approximation is getting closer to 2.71828 with a small error. However, the approximation number suddenly dropped to 1. Why is this problem? Be prepared to answer this in your README.
The main program should print the following output:
All output line from the main process should start on column 1 (i.e., no leading spaces).Main Process Started Fibonacci Number 10 Buffon's Needle Iterations = 100000 Integration Iterations = 200000 Approx. e Iterations = 73000000000000000 Fibonacci Process Created Buffon's Needle Process Created Integration Process Created Approximation of e Process Created Main Process Waits Main Process Exits
It is very important to remember the following.
| All processes must run concurrently and may print their output lines in an unpredictable order. As a result, the output lines from a process may mix with output lines from other processes. This is the reason that proper indentation is required to know who prints what. Also make sure that each line will not contain the output from different processes. |
This procedure may be repeated a number of times with different input to see if your program works correctly.gcc prog1.c -std=c89 -lm -o prog1 <-- compile your program ./prog1 73000000000000000 10 100000 200000 <-- test your program
|
You must use the above command lines to compile and run your program.
Otherwise, our grader may not be able to grade your program,
and you will risk a low or even a 0 score.
By default, CS lab machines use C89, and our grader uses C89 for grading. Therefore, if you use C90 to write this program, your program may not compile using CS lab machines. If this happens, you will receive a 0 because your program does not compile. |
/* ----------------------------------------------------------- */ /* NAME : John Smith User ID: xxxxxxxx */ /* DUE DATE : mm/dd/yyyy */ /* PROGRAM ASSIGNMENT # */ /* FILE NAME : xxxx.yyyy.zzzz (your unix file name) */ /* PROGRAM PURPOSE : */ /* A couple of lines describing your program briefly */ /* ----------------------------------------------------------- */
Here, User ID is the one you use to login. It is not your social security number nor your M number.
For each function in your program, include a simple description like this:
/* ----------------------------------------------------------- */ /* FUNCTION xxyyzz : (function name) */ /* the purpose of this function */ /* PARAMETER USAGE : */ /* a list of all parameters and their meaning */ /* FUNCTION CALLED : */ /* a list of functions that are called by this one */ /* ----------------------------------------------------------- */
void main(int argc, char **argv)
{
int i, n = atoi(argv[1]);
for (i = 1; i < n; i++)
if (fork())
break;
printf("Process %ld with parent %ld\n", getpid(), getppid());
sleep(1);
}
void main(int argc, char **argv)
{
int i, n = atoi(argv[1]);
for (i = 0; i < n; i++)
if (fork() <= 0)
break;
printf("Process %ld with parent %ld\n", getpid(), getppid());
sleep(1);
}
void main(int argc, char **argv)
{
int i, n = atoi(argv[1]);
for (i = 0; i < n; i++)
if (fork() == -1)
break;
printf("Process %ld with parent %ld\n", getpid(), getppid());
sleep(1);
}
You should elaborate your answer and provide details. When answering the above questions, make sure each answer starts with a new line and has the question number (e.g., Question X:) clearly shown. Separate two answers with a blank line. Also make sure that the diagrams in your README file will PRINT correctly. Do not judge the results on screen.
Note that the filename has to be README rather than readme or Readme. Note also that there is no filename extension, which means a filename such as README.TXT is NOT acceptable.
README must be a plain text file. We do not accept files produced by any word processor. Moreover, watch for very long lines. More precisely, limit the length of each line to no more than 80 characters with the Return/Enter key for line separation. Missing this file, submitting non-text file, file with long lines, or providing incorrect and/or vague answers will cost you many points. Suggestion: Use a Unix text editor to prepare your README rather than a word processor.