Exercise 1

Please do the following problems:

• (20 points)
  Show that the associative and distributive laws in general do not hold for finite precision floating point arithmetic.

  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 no credit.

• (40 points)
  Let us do a dramatic floating point computation experiment.
  

  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

  P = out^k(in^k(P)) = in^k(out^k(P))

  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²(in²(P)), out³(in³(P)), in²(out²(P)) and in³(out³(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:

  maximum error of A = maximum of |x - x'| and |y - y'|

  The maximum error of P is the maximum over all five vertices. Then, you can compile a table as follows:

  p	out2(in2(P))	out3(in3(P))	in2(out2(P))	in3(out3(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 Note Note 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.

• (40 points)
  Use spheres, boxes, planes, cylinders, cones and whatever objects you like to compose a scene. Then, raytrace it.

  Please note the following when you do this problem:

  1. Your scene should be in a single file.
  2. Do not generate large images . Testing your result using 120×90 or 160×120. When you are done, put POVRAY in the background for generating a larger image, say 640×480.
  3. Use display or xv for viewing.
  4. To reduce file size, convert POVRay's output file to JPEG with low compression ratio. display, xv and gimp have this conversion capability. Under display, you can choose save, followed by format. Then, select jpeg. Finally, save the result. The default quality factor is 75%. Please change this value to 80% or higher for better image quality. Please erase your TARGA file because it is huge (uncompressed). Make sure the filename extension is jpg rather than JPG nor JPEG.
  5. Feel free to use whatever colors you like and choose whatever location and viewing position.
  6. Add your name and e-mail address on the JPEG image.

Use the submit command to submit the following material:

• A README file contains the solutions to these three problems. More precisely, you should put the answer to Problem 1, the tables and elaboration of Problem 2, and the description and anything you want to write about for Problem 3 in this file. Please use ASCII text files. This file will be graded and e-mail back to you. Make sure line length in your README file is no more than 80 characters (i.e.), use the Return key to limit the length of each line to 80 characters. Otherwise, you will risk lower grade.
• In the very beginning of your README file, you should add the following information for identification purpose:

  NAME:      your name
  E-MAIL:    your e-mail address
  EXERCISE:  1
  FILES:     README, and other files submitted along with README
  

• Submit your JPEG image with filename your-name.jpg. Also add your name and e-mail address on the image. With display, use the left-button to bring up the ImageMagick main menu and choose Image Edit followed by annotate. Then, you could choose a font, a color and so on. Finally, move the mouse pointer into the image area where you want to place your name, click, type your name, and hit ESC key to get out. Don't forget to save your file. After submitting your file, please do not touch it until this semester is over.
• In summary, you need to submit the following files:
  1. File README
  2. A C program file pentagon.c
  3. A Makefile for me to compile and run your C program and generate the desired result.
  4. POVRAY scene file your-name.pov
  5. JPEG file your-name.jpg

• For all problems, you should show the details of your reasoning and computations. Only showing a few numbers receives no credit.
• Your README file, program file and scene file should include your name and e-mail address (no SSN please). Program files and scene files should have sufficient details for me to understand and evaluate your work. Apply all you have learned in programming courses to your programs and scene files.
• Do not use any scene files and/or object files you download from the Internet. Otherwise, I will consider it an act of cheating. You must design your own scene.
• If you were in this class previously, even for a brief of time, do not submit your old work. Otherwise, I will return it to you. In other words, I expect you to submit your new work.
• If you have any questions, please stop by or e-mails me.