For this assignment, you will experiment with a class of mathematical sets called CONVERGENCE SETS, and with one set in particular, the PAIN-D'AMANDE SET. The general idea of a convergence set is to take a function f(x). In this function, there is a constant C which contributes to the final value of the function. We begin with x=0, and call f repeatedly, generating the series {0, f(0), f(f(0)), f(f(f(0))), ...}. The question is: for a given value of C, does this series diverge (go off towards infinity), or does it stay "close" to 0? For a given function f(x), we say that the convergence set of f is the set of all values of C which cause the series above to stay close to 0. For instance, take the function f(x) = C * (x+1), defined over real numbers. It can be proven, using high-school algebra, that this series will diverge for any C>=1 and for any C<=(-1), and will converge for any C between -1 and 1. Thus, we would say that the convergence set for f is the set of all real numbers between -1 and 1 (exclusive). This is easy to prove, but also very BORING. Things get more interesting when we start talking about complex numbers, however. In fact, like the three-body problem in physics, a closed-form solution may be impossible. So we have to turn to the computer for help. We can program the computer with a given function, and let it try various values of C to determine which ones are in the convergence set. The Pain-d'Amande Set is defined as the convergence set for the complex function f(z) = z**2 + C (both z and C are complex numbers). In other words, a complex number C is in the Pain-d'Amande Set if the infinite series {0, C, C**2+C, (C**2+C)**2+C, ...} stays close to 0, and NOT in the set if the series diverges. (Remember that a complex number is the sum of a real number and an imaginary number. The latter is the product of i (square root of -1) and a real number. The rules for arithmetic on complex numbers are: (a + bi) + (c + di) = (a+c) + (b+d)i (a + bi) * (c + di) = (ac-bd) + (ad+bc)i The multiplication rule follows from the fact that i**2 = -1.) We don't know how to write down the complete Pain-d'Amande Set. All we can do is ask the computer to draw a portion of the complex plane, and indicate which points are in the set and which are not in the set. The computer you are using is capable of displaying a 640x400 grid of colored dots on its screen. Each dot is called a "pixel" and can be given one particular color. Therefore, you will write a program that will calculate the series at each point in a 640x400 grid of sample points in the complex plane. These points are equally spaced. For instance, suppose that we decide to plot a 640x400 grid of points, with the upper-left point taking the value C=0+0i and a distance of 0.01 between each pair of adjacent points. Thus, the lower-right grid point would correspond to C=6.39-3.99i. The entire grid would look like this: (0,0) (.01,0) (.02,0) (6.38,0) (6.39,0) * <-------> * * ... * * ¬ 0.01 0.01 | | V * * * ... * * (0,-.01) (.01,-.01) (.02,-.01) (6.38,-.01) (6.39,-.01) . . . . . . . . . . . . . . . * * * ... * * (0,-3.99) (.01,-3.99) (.02,-3.99) (6.38,-3.99) (6.39,-3.99) For each point, plug the appropriate value of C into the function f(z), and calculate the series {0, f(0), f(f(0)), ...}. As you compute each value in the series, check its magnitude (distance to the complex origin). If it goes beyond 10, you can assume that the series diverges and that that value of C is not in the Pain-d'Amande Set. If the magnitude stays less than 10 for a large number of iterations (100, for instance), then you can assume that the point is within the set. (A higher iteration count leads to more accurate results, but also takes more time.) There are large regions of the complex plane which are in the set, and even larger regions which are not in the set. The most interesting region of space to study is the area close to the boundary, i.e., the points which are "out" of the set, but "just barely." Therefore, your program should color a point according to how many iterations it takes to "leave" the set, i.e., to get a magnitude greater than 10. Your computer can give a point one of 16 different colors. Therefore, you can assign one color (black) to a point if it is in the Pain-d'Amande Set (i.e., after many iterations, you are still close to 0). You can then select a second color if it takes, for instance, fewer than 5 iterations for the magnitude to become bigger than 10, a third color if it takes between 5 and 10 iterations, etc. WHAT TO DO FOR THE ASSIGNMENT Your main task is to write a routine to draw Pain-d'Amande sets and to give the user the ability to select various parts of the complex plane to examine more closely. You should copy this main routine into your program: #include#define BOUNDS 10.0 #define LIMIT 100 void initialize (); int boundary (double *, double *, double *); void draw (double, double, double, double, int); main () { double ULreal = -2.3; /* Complex coordinates */ double ULimag = 1.1; /* of upper-left pixel */ double scale = .0055; /* Distance between adjacent pixels */ int more; /* Continuation requested by user */ initialize(); for (more = 1; more; more = boundary (&ULreal, &ULimag, &scale)) { draw (ULreal, ULimag, scale, BOUNDS, LIMIT); } } This program call an "initialization" routine, which will set up all the graphics for you. The main program sets the coordinates for the first drawing (the upper-left corner has the value C = -2.3+1.1i, and the interpixel distance is 0.0055). Then it goes into a loop, where it calls the procedure "draw" to paint the screen according to the parameters given, and then calls "boundary" to get coordinates for a new screen. We will provide you with "initialize" and "boundary"; your assignment is to write the "draw" function. The draw function takes 5 arguments. The first two give the real and imaginary parts of the complex number corresponding to the upper-left corner of the screen. The third argument gives the distance between adjacent pixels (in the complex plane). The fourth argument is the limit for deciding when the series has diverged. The last number, an integer, tells the draw function how many terms to calculate in the series before deciding that the value of C is in the Pain-d'Amande set. To fill in a particular pixel, use the putpixel routine, e.g., putpixel (column,row,color); All three arguments are integers. The first two give the column and row for the pixel. Columns are numbered from 0 (left) to 639 (right). Rows are numbered from 0 (top) to 399 (bottom). Thus, 0,0 represents the upper-left corner. The color argument is a number between 0 and 15 which tells the computer which color to use. We will have set up a "color map" for you, in which 15 is black (used for things in the Pain-d'Amande set) and the other numbers (0-14) form a rainbow of colors you can use for points not in the set. HINTS: This problem takes a LOT of time. It will probably take roughly 5-15 minutes to paint a single screen, depending on how many points are in the set. There are several things you can do to lessen the problems: 1. AVOID REDUNDANCY. Try to avoid repeat calculations. For instance, if the same operation is done twice in separate expressions, then do that operation once, save the results in another variable, then use that variable in the expressions. Also, remember that certain operations take longer than others, so you should try to do things with the quicker operations whenever possible. For instance, to check that the series has not diverged, your draw function should compare the magnitude of the current value in the series (i.e., sqrt(x**2 + y**2) with the fourth argument. Don't calculate the square root (too expensive!); instead, compare the SQUARE of the magnitude (i.e., x**2 + y**2) with the SQUARE of the fourth argument (the latter can be calculated once, at the beginning of the draw function, and then saved). Finally, don't use pow(x,2.0) to square x; use x*x instead. 2. SACRIFICE SPACE FOR SPEED. For instance, one thing you will have to do in the draw routine is to decide which color to use for a pixel after you determine how many iterations it takes for z to get too big. There are 16 ranges (for instance, >100 iterations = color 15, 95-100 = color 14, ... 1-10 = color 0). You could use a structure like if...else if...else if...else to turn an iteration count into a color, but the program would run faster if you were to make an array with 100 elements, which you would set at the beginning of the main program, which tells you which color to use for a given iteration. For instance, a[34]=8 would mean that if it took 34 iterations for z to get too big, then the pixel would be colored with color number 8. 3. PROTOTYPE FIRST. When you are first testing your program, you don't need to fill the entire screen (640X400). You could set it up so that it only fills a 64X40 corner of the screen. Filling up a screen of that size would only take 1% as long! Also, you can use a lower value for the fifth argument to draw, e.g., 20 or 30. The result won't be as accurate, but it will allow you to get the bugs out of your program more quickly. Once you are confident that your program works for the prototype screen, you can move to the full screen with the full suggested limit (100). (You should make the number of rows and columns appear in #define statements so that you can easily change them.)