# Untitled

By: a guest on Jun 13th, 2012  |  syntax: None  |  size: 3.52 KB  |  hits: 17  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. // Project 1
2. // CMSC 15200
3. // Winter 2011
4. // Miranda Seitz-McLeese
5. // mseitzmcleese@uchicago.edu
6.
7. #include <math.h>
8. #include <stdio.h>
9.
10. // Recursion boundaries
11. #define max_levels 30
12. #define min_levels 3
13.
14. // Global variable for accounting of evaluations
15. int evaluations = 0;
16.
17. // Point struct definition
18. struct point
19. {
20.         double x;
21.         double y;
22. };
23.
24. // Pointer to a function that takes a double and returns a point
25. typedef struct point (*pcurve)(double);
26.
27. // Distance between two points.
28. double distance (struct point p_one, struct point p_two);
29.
30. // Line
31. struct point line(double t);
32.
33. // Parabola
34. struct point parabola(double t);
35.
36. // Sqrt Sine
37. struct point sine(double t);
38.
39. // Recursive function to find curve length
40. double curve_length(double left, double right, pcurve curve, double tolerance);
41.
42. // Print a few test results of curve_length
43. int main()
44. {
45.         // Declarations
46.         double line_length, parabola_length, sine_length;  // variables to hold the results of curve_length
47.
48.         // Line results
49.         line_length = curve_length(0, 2, line, .01);
50.         printf("Line     (tol = .01)   : %f, %d evaluations \n", line_length, evaluations);
51.         evaluations = 0;
52.         line_length = curve_length(0, 2, line, .0001);
53.         printf("         (tol = .0001) : %f, %d evaluations \n", line_length, evaluations);
54.         evaluations = 0;
55.
56.         // Parabola results
57.         parabola_length = curve_length(0, 1, parabola, .01);
58.         printf("Parabola (tol = .01)   : %f, %d evaluations \n", parabola_length, evaluations);
59.         evaluations = 0;
60.         line_length = curve_length(0, 1, parabola, .0001);
61.         printf("         (tol = .0001) : %f, %d evaluations \n", parabola_length, evaluations);
62.         evaluations = 0;
63.
64.         // Sine Results
65.         sine_length = curve_length(0, 1, sine, .01);
66.         printf("Sine     (tol = .01)   : %f, %d evaluations \n", sine_length, evaluations);
67.         evaluations = 0;
68.         sine_length = curve_length(0, 1, sine, .0001);
69.         printf("         (tol = .0001) : %f, %d evaluations \n", sine_length, evaluations);
70.         return 0;
71. }
72.
73. double distance(struct point p_one, struct point p_two)
74. {
75.         double dist = sqrt((p_one.x - p_two.x)*(p_one.x - p_two.x) + (p_one.y - p_two.y)*(p_one.y - p_two.y));
76.         return dist;
77. }
78.
79. struct point line(double t)
80. {
81.         struct point p;
82.         p.x = t;
83.         p.y = 2*t;
84.         return p;
85. }
86.
87. struct point parabola(double t)
88. {
89.         struct point p;
90.         p.x = t;
91.         p.y = t*t;
92.         return p;
93. }
94.
95. struct point sine(double t)
96. {
97.         struct point p;
98.         p.x = t;
99.         p.y = sqrt(sin(t));
100.         return p;
101. }
102.
103. double curve_length(double left, double right, pcurve curve, double tolerance)
104. {
105.         // Declarations
106.         static int levels = 0;           // Keep track of levels of recursion
107.         double corse, fine;              // Estimation variables
108.         double middle;                   // Mid point of interval
109.         double first_half, second_half;  // To hold the results of the recursive call
110.
111.         // Increment bookkeeping variables.
112.         levels++;
113.         evaluations++;
114.
115.         // Calculate midpoint
116.         middle = left + fabs(right - left)/2;
117.
118.         // Calculate corse and fine estimates
119.         corse = distance((curve(left)), (curve(right)));
120.         fine = distance(curve(left), curve(middle)) + distance(curve(middle), curve(right));
121.
122.         // If precise enough, return the fine value, if not, recurse again.
123.         if (levels >= max_levels)
124.         {
125.                 levels--;
126.                 return fine;
127.         }
128.         if (levels < min_levels || fabs(fine-corse) > tolerance){
129.                 first_half = curve_length(left, middle, curve, (tolerance/2));
130.                 second_half = curve_length(middle, right, curve, (tolerance/2));
131.                 levels--;
132.                 return (first_half + second_half);
133.         }
134.         else {
135.                 levels--;
136.                 return fine;
137.         }
138. }