Write a C program to generate a Postscript program that will plot the Mandlebrot set on the printer.

The Mandlebrot set is a specific set of points on the plane with many fascinating properties. One can determine whether or not a point (x, y) is in the Mandlebrot set by performing the following calculation: start with r=0.0 and s=0.0, then enter into a loop which resets r to r*r - s*s + x and s to 2*r*s + y (using the old values of r and s in both of these equations). If r*r + s*s ever gets to be greater than 4, this iteration diverges (r goes to infinity or s goes to infinity). The set of all points for which divergence does not happen is the Mandlebrot set. If we consider the number of iterations needed to discover that points in the plane are not in the Mandlebrot set, a strange and wondrous pattern emerges, roughly within the 2.0-by-2.0 box centered at (-0.5, 0). We can't compute or plot for the infinite number of points on the plane, so, in order to plot the points, we perform this calculation for an N-by-N grid of points, a ``sample'' of the continuum spaced at regular intervals. As we increase N, we get a better approximation to the set at the cost of more computation.

Your main task is to do a rough plot, using your terminal window as a (very) low-resolution output device. To get started, use the following program, which plots an N-by-N pattern with an asterisk in position (i, j) if i and j are relatively prime, where N is a compile-time constant. The function used to perform this computation implements Euclid's algorithm (see Sedgewick, p. 191). Though the function is not related to the Mandlebrot set, you should be interested in this program because the structure of the computation is what you need: it prints a square pattern of characters that are either blanks or asterisks, depending on the value of a function with arguments correponding to the position.

      #include <stdio.h>
      #define N 32
      int gcd(int m, int n)
        {
          if (n == 0) return m; else return gcd(n, m % n);
        }  
      main() 
        { 
          int i, j;
          for (i = 2; i < N; i++)
            {
              for (j = 2; j < N; j++)
                if (gcd(j, i) == 1) printf("  "); else printf("* ");
              printf("\n");
            }
        }

To accomplish your first task, modify this program to include a function that returns the number of iterations required to determine that a given point is not is the Mandlebrot set (or 100 if the number of iterations is 100 or greater, which will be the case for all the points in the set and perhaps a few other points), and to replace the call to gcd with a call on that function. The main task here is to rescale from the implied integer coordinate system (j and i running from 0 to N) to x and y values in the 2.0-by-2.0 box centered at (-0.5, 0), which contains an interesting part of Mandlebrot set. Also, maintain a global array area such that area[t] is the number of points for which your function returns t. The array is so named because 4.0*area[100]/(N*N) is an approximation to the area of the Mandlebrot set. Print out these values, using "%3d " as the format in the printf, so that the printout only uses a few lines. Your primary submission for this assignment is this program, which prints out the Mandlebrot set and the area values. This part of the assignment accounts for 90 per cent of your grade. The second part of the assignment is fun and educational, so it will certainly be worth your while to give it a try, but don't treat getting it working as a make-or-break proposition.

Consider the following code for plotting points on the printer. It is a simple program that draws a box, defines a point-plotting subroutine, and calls the subroutine to plot five points. It is written in a language called PostScript, the internal language for most printers nowadays.

%!
50 50 translate
0 0 moveto 0 512 rlineto 512 0 rlineto 0 -512 rlineto closepath stroke 
/pt { 0 360 arc fill } def
.75 setgray 128 128 64 pt
.50 setgray  64 356  8 pt
  0 setgray 200 490 20 pt
.25 setgray 412 428 32 pt
.99 setgray 450.234  75.1 50.999 pt
showpage

First, put this program into a file called test. There are at least two ways to run this program and see what it does: gs test shows the result on the screen, and lpr test puts the result on the printer. When you see the result, you can figure out that the program draws five circles, using a pt function that takes three arguments (which precede the call): the x and y coordinates of the point (in the range between 0 and 512) and the size of the point. The ``color'' of the point is set by a built in routine setgray that takes an argument between 0 and 1.

Your next task is to write a C program that produces this PostScript program as output. When you run your C program, you can redirect its output to a file, which will then contain a PostScript program! The last step is to combine this program and your Mandlebrot program for the terminal to make a program that produces a grey-scale representation of the Mandlebrot set, using the color 1-t/100.0 for each point, where t is the number of time the Mandlebrot test loop iterated. Thus, points which might be in the set have color 0 (black). To debug, first make certain that your C program produces a valid PostScript program that is just like the sample program, except with more calls to pt. Do not print your output or use very big values of N until you are certain that your program works. Even once it works, be careful about using big values of N. Learn to trade off time, space, and resolution.

You must submit a file mandtty.c which solves the first part of this assignment. If you succeed in getting the PostScript part working, name your source file mandps.c and submit it along with a file picture.ps, that produces a 32-by-32 pattern of touching dots, scaled to fill the page, shaded to represent the Mandlebrot set, as described above. If not, just collect your 90 per cent credit, and don't burden us with incomplete or dysfunctional PostScript solutions.

Challenge for the bored: There are limitless opportunities to avoid boredom here. For example, try using different rules for assigning the gray, experiment with color displays, or zoom in on other interesting parts of the set. Try a .25-by-.25 square somewhere near the edge.

This assignment was adapted by R. Sedgewick and M. Weiksner from the book A Turing Omnibus by A. Dewdney.