Number of Points | 100 |
Due Date | Friday, September 16, 11pm |
Please do the following problems:
If you do not know how to prove it theoretically, showing counterexamples is as good as a proof. In this case, you might assume that the machine being used can store four significant digits. Then, find three floating point numbers that do not satisfy the associative law. Do the same for the distributive law. Use the normalized form of floating point numbers, and don't use overflow and underflow! Otherwise, you risk lower grade.
You should (1) present the input, (2) show a step-by-step computation using decimal numbers, and (3) finally conclude that the associative and distributive laws do not hold. Only submitting a few numbers without calculation steps and elaborations receive credit.
The above shows a pentagon ABCDE. If we draw the five diagonals of this pentagon, we have a smaller pentagon inside the pentagon ABCDE. This smaller pentagon has its vertices in white color. Let us call the original pentagon P and the smaller pentagon in(P), because it is the result of "going" inside of pentagon P.
If we extend the sides of the given pentagon, they will intersect in five points, which define a new pentagon outside of the pentagon P. We call this new "outside" pentagon out(P), because it lies outside of pentagon P.
From this construction, we know that going out from in(P) should be P. Similarly, going in from out(P) should also be P. More precisely, we have P = out(in(P)) and P = in(out(P)). Let in^{k}(P) denote executing the "going in" operation k times, and out^{k}(P) denote executing the "going out" operation k times. Then, the following should hold
This means that going in k times followed by going out k times should yield pentagon P. Similarly, going out k times followed by going in k times should also yield pentagon P.
Now consider the following strange pentagon:
The vertices are as follows, where p can be 0.1, 0.01, 0.001, 0.0001, 0.00001 and 0.000001.
Vertex | x | y |
A | 0 | 1 |
B | 0 | 0 |
C | 1 | 0 |
D | 1 + p | 1 |
E | 1 | 1 + p |
For a given P, compute out^{2}(in^{2}(P)), out^{3}(in^{3}(P)), in^{2}(out^{2}(P)) and in^{3}(out^{3}(P)). Then, theoretically all four pentagons should be identical to pentagon P. Unfortunately, due to finite precision arithmetic, this is not the case. As a result, we should measure the error generated from the in() and out() operations. For each vertex of the pentagon P, say A = (x, y), and its corresponding result after taking the in() and out() operations, say A' = (x', y'), we compute the maximum error as follows:
The maximum error of P is the maximum over all five vertices. Then, you can compile a table as follows:
p | out^{2}(in^{2}(P)) | out^{3}(in^{3}(P)) | in^{2}(out^{2}(P)) | in^{3}(out^{3}(P)) |
0.1 | fill maximum error in each entry | |||
0.01 | ||||
0.001 | ||||
0.0001 | ||||
0.00001 | ||||
0.000001 |
Write a program that uses both float and double to perform the calculation and generate the above maximum error table. Name your program pentagon.c. You will need (1) constructing a line from two points, and (2) computing the intersection point of two lines. Please consult your calculus and analytic geometry books.
To receive full credit, you should do the following: (1) the required maximum error tables, one for float and one for double, (2) program file pentagon.c and a Makefile for me to compile and run your program, (3) the vertices of the resulting pentagon, (4) a table in the format mentioned above (submit it in your README file) and (5) an analysis which should include answers to questions like (a) why could the error be very large? (b) what is the cause(s) of the problem(s)? (c) which vertex (or vertices) causes the largest error?, and (d) any findings that are worth mentioning. In answering (5b), you should provide evidence and argument to convince me. The reason that "it is due to finite precision and loss of significant digits in floating point calculation" is not acceptable.
An Important NoteNote that having subtraction operations and losing significant digits are not good answers. They are the consequences of some operations you put into your program. You should pinpoint the right places where these problems appear and tell me why. |
Please note the following when you do this problem:
Use the submit command to submit the following material:
NAME: your name E-MAIL: your e-mail address EXERCISE: 1 FILES: README, and other files submitted along with README