Assignment #7 - 94A

Assignment #7 - 94A


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.)