|
CMSC 201
Programming Project Five
Approximating PI Using a Series
Out: Sunday 4/28/02
Due: Before Midnight, Tuesday 5/14/02
The design document for this project, design5.txt
is due: Before Midnight, Sunday 5/5/02
|
The Objective
The objective of this assignment is to give you experience working with
linked lists. You'll be using command-line arguments, dynamic memory
allocation, passing by reference, and be working with the fraction ADT. You
will also continue to practice using good program design and implementation
techniques.
The Background
A series is a sum of terms that are related by some general formula.
We can approximate pi by using the following formula :
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 . . .
so
pi = 4(1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 . . .)
This is an infinite series. The more terms we use, the closer we get to the
real value of pi.
The Task
Design and code a project that uses a command-line argument to get the number
of terms the user would like to sum to approximate pi. Each term of the
series is to be stored as a FRACTION (see Lecture 22) within a NODE of a
linked list (See Lecture 23). So for each term you will create a node, store
the appropriate fraction in it and insert it into your linked list.
After building the linked list, you should traverse the list and print out all
of the fractions that are in it. Since you are interested in the sum of the
terms, as you insert each node, you'll need to add that fraction to the sum.
It is possible to keep this sum as either a FRACTION or a double. You should
calculate the sum in both forms (both FRACTION and double) if possible.
There is a problem with storing the sum as a FRACTION when the user chooses
to have more than 12 terms in his/her partial series. See the sample
output below to determine what that problem is. The file header comment of
your proj5.c file MUST explain the problem. If the user wants to use
a partial series of more than 12 terms, calculate the sum only as a double.
Your project should print out the fractions that are being stored in your
linked list as they would be printed by the function PrintFraction(). Although
this is sufficient to tell what is in the list, we would like to see the series
printed out in a more appopriate form. You must have a different function that
will print out the terms of the series in a nicer form as shown in the sample
run. You must also print out the sum either as just a double, or in both forms
when possible, and the approximation of pi.
Sample Run
<![CDATA[
linux1[101] a.out 1
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1
pi/4 = 1
pi/4 = 1
With 1 terms the approximation of pi is 4.000000
linux1[102] a.out 2
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3
pi/4 = 1 - 1/3
pi/4 = + 2/3
With 2 terms the approximation of pi is 2.666667
linux1[103] a.out 3
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5
pi/4 = 1 - 1/3 + 1/5
pi/4 = + 13/15
With 3 terms the approximation of pi is 3.466667
linux1[104] a.out 4
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7
pi/4 = 1 - 1/3 + 1/5 - 1/7
pi/4 = + 76/105
With 4 terms the approximation of pi is 2.895238
linux1[105] a.out 5
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9
pi/4 = + 263/315
With 5 terms the approximation of pi is 3.339683
linux1[106] a.out 6
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11
pi/4 = + 2578/3465
With 6 terms the approximation of pi is 2.976046
linux1[107] a.out 7
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13
pi/4 = + 36979/45045
With 7 terms the approximation of pi is 3.283738
linux1[108] a.out 8
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
pi/4 = + 33976/45045
With 8 terms the approximation of pi is 3.017072
linuxserver1[109] a.out 9
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17
pi/4 = + 622637/765765
With 9 terms the approximation of pi is 3.252366
linux1[110] a.out 10
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19
pi/4 = + 11064338/14549535
With 10 terms the approximation of pi is 3.041840
linux1[111] a.out 11
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
0 1/21
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19 + 1/21
pi/4 = + 11757173/14549535
With 11 terms the approximation of pi is 3.232316
linux1[112] a.out 12
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
0 1/21 0 1/-23
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19 + 1/21 - 1/23
pi/4 = + 255865444/334639305
With 12 terms the approximation of pi is 3.058403
linux1[113] a.out 13
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
0 1/21 0 1/-23 0 1/25
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19 + 1/21 - 1/23 + 1/25
pi/4 = 0.804601
With 13 terms the approximation of pi is 3.218403
linux1[114] a.out 25
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
0 1/21 0 1/-23 0 1/25 0 1/-27 0 1/29
0 1/-31 0 1/33 0 1/-35 0 1/37 0 1/-39
0 1/41 0 1/-43 0 1/45 0 1/-47 0 1/49
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19 + 1/21 - 1/23 + 1/25 - 1/27 + 1/29 - 1/31
+ 1/33 - 1/35 + 1/37 - 1/39 + 1/41 - 1/43 + 1/45 - 1/47
+ 1/49
pi/4 = 0.795394
With 25 terms the approximation of pi is 3.181577
linux1[115] a.out 100
[Your greeting and explanation of the approximation of pi goes here]
The fractions being held in the list are :
1 0/1 0 1/-3 0 1/5 0 1/-7 0 1/9
0 1/-11 0 1/13 0 1/-15 0 1/17 0 1/-19
0 1/21 0 1/-23 0 1/25 0 1/-27 0 1/29
0 1/-31 0 1/33 0 1/-35 0 1/37 0 1/-39
0 1/41 0 1/-43 0 1/45 0 1/-47 0 1/49
0 1/-51 0 1/53 0 1/-55 0 1/57 0 1/-59
0 1/61 0 1/-63 0 1/65 0 1/-67 0 1/69
0 1/-71 0 1/73 0 1/-75 0 1/77 0 1/-79
0 1/81 0 1/-83 0 1/85 0 1/-87 0 1/89
0 1/-91 0 1/93 0 1/-95 0 1/97 0 1/-99
0 1/101 0 1/-103 0 1/105 0 1/-107 0 1/109
0 1/-111 0 1/113 0 1/-115 0 1/117 0 1/-119
0 1/121 0 1/-123 0 1/125 0 1/-127 0 1/129
0 1/-131 0 1/133 0 1/-135 0 1/137 0 1/-139
0 1/141 0 1/-143 0 1/145 0 1/-147 0 1/149
0 1/-151 0 1/153 0 1/-155 0 1/157 0 1/-159
0 1/161 0 1/-163 0 1/165 0 1/-167 0 1/169
0 1/-171 0 1/173 0 1/-175 0 1/177 0 1/-179
0 1/181 0 1/-183 0 1/185 0 1/-187 0 1/189
0 1/-191 0 1/193 0 1/-195 0 1/197 0 1/-199
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15
+ 1/17 - 1/19 + 1/21 - 1/23 + 1/25 - 1/27 + 1/29 - 1/31
+ 1/33 - 1/35 + 1/37 - 1/39 + 1/41 - 1/43 + 1/45 - 1/47
+ 1/49 - 1/51 + 1/53 - 1/55 + 1/57 - 1/59 + 1/61 - 1/63
+ 1/65 - 1/67 + 1/69 - 1/71 + 1/73 - 1/75 + 1/77 - 1/79
+ 1/81 - 1/83 + 1/85 - 1/87 + 1/89 - 1/91 + 1/93 - 1/95
+ 1/97 - 1/99 + 1/101 - 1/103 + 1/105 - 1/107 + 1/109 - 1/111
+ 1/113 - 1/115 + 1/117 - 1/119 + 1/121 - 1/123 + 1/125 - 1/127
+ 1/129 - 1/131 + 1/133 - 1/135 + 1/137 - 1/139 + 1/141 - 1/143
+ 1/145 - 1/147 + 1/149 - 1/151 + 1/153 - 1/155 + 1/157 - 1/159
+ 1/161 - 1/163 + 1/165 - 1/167 + 1/169 - 1/171 + 1/173 - 1/175
+ 1/177 - 1/179 + 1/181 - 1/183 + 1/185 - 1/187 + 1/189 - 1/191
+ 1/193 - 1/195 + 1/197 - 1/199
pi/4 = 0.782898
With 100 terms the approximation of pi is 3.131593
]]>
Here is the output when using 25000 terms.
Here is a chart of some approximations
| # of terms | Approx of pi | | # of terms
| Approx of pi |
| 10
| 3.041840
|
| 11
| 3.232316
|
| 100
| 3.131593
|
| 101
| 3.151493
|
| 1000
| 3.140593
|
| 1001
| 3.142592
|
| 10000
| 3.141493
|
| 10001
| 3.141693
|
| 25000
| 3.141553
|
| 25001
| 3.141633
|
| 50000
| 3.141573
|
| 50001
| 3.141613
|
Further Specifications
- You must use separate compilation for this project. It would be
appropriate to have many .c and .h files for this project. I would
suggest proj5.c, list.c & .h, fraction.c & .h, and proj5aux.c & .h
- You must use a linked-list for this project.
You may NOT use an array implementation. If you choose to do so your
project will earn a 0.
- You may use the linked list code given in lecture 23. Some
of the functions will need minor modification, but some will work as
they are (if you choose your data structures carefully when designing).
- You may use the fraction code given in lecture 22.
- For terms of 12 or less, you must calculate the sum as both a fraction
and as a double and display each. For terms of more than 12, do NOT
calculate the sum as a fraction. Only calculate the sum as a double.
You must have an explanation of why this is necessary in your file
header comment of the proj5.c file.
- You MUST use dynamic memory allocation (malloc) to allocate the
memory for the nodes of the linked lists. Of course, you must check to
see that the space was actually given to you.
- You must destroy the list after you are finished using it, so you
must write your own DestroyList() function and add it to the
linked list code. This function should free all of the nodes of a
linked list that is passed to it.
- If the program is run with the wrong number of command line arguments,
an appropriate message must be printed to the screen informing the user
how to correctly run the program and then the program must exit.
Submitting the Program
Here is a sample submission command. Since you may have different file names
you'll have to adjust it to fit your needs. As always, be sure to submit all
of the files necessary for your project to compile.
Note that the project name starts with uppercase 'P' as always.
submit cs201 Proj5 proj5.c list.c list.h fraction.c fraction.h proj5aux.c
proj5aux.h
To verify that your project was submitted, you can execute the
following command at the Unix prompt. It will show the file that
you submitted in a format similar to the Unix 'ls' command.
submitls cs201 Proj5
<![CDATA[
]]>