Write a C program to generate a PostScript program that will plot the Mandelbrot set.

The Mandelbrot set 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 Mandelbrot set by performing the following calculation: start with r = x and s = y, 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 update formulae). If this sequence remains bounded (neither r nor s goes to infinity) then the point (x,y) is in the Mandelbrot set; otherwise, if the sequence diverges to infinity, it is not. If you plot the points in the Mandelbrot set black, and those not in the set white, a strange and wondrous pattern emerges, roughly within the 2.0-by-2.0 box centered at (-0.5, 0). For a more dramatic picture, the white points can be replaced by color gradations, depending on the number of iterations needed to discover that the point is not in the set. The colors reveal the striking detail of the terrain just outside the Mandelbrot set.

Part 1: Mandelbrot computation. Your first task is to write a function that determines whether or not the point (x,y) is in the set. The mathematical definition of the Mandelbrot set is precise, but is computationally unappealling, since we would have to perform an infinite number of iterations to determine whether a single point is in the set! We are rescued by the following mathematical fact: if r*r + s*s ever gets to be greater than 4, then the sequence will surely diverge off to infinity, and the point (x,y) is not in the set. There is no simple test that would enable us to conclude that (x,y) is surely in the set, but if the number of iterations exceeds 255, the point is extremely unlikely to be in the set.

Write a function int mandel(float x, float y) that performs the Mandelbrot computation on the point (x,y). It returns the number of iterations needed to discover that (x,y) is not in the set, or 255 if 255 or more iterations are required (this will be the case for all points in the set, and perhaps a few others). Using this function, you will produce a gray-scale and a color image of the Mandelbrot set, by writing a C program that outputs a PostScript program.

Part 2: gray-scale image. To produce the gray-scale image of the Mandelbrot set, you would need to perform the Mandelbrot calculation at every point in the plane. You cannot plot an infinite number of points, so you will plot a ``sample'' of the continuum. The interesting part of the Mandelbrot set occurs in a 2.0-by-2.0 box centered at (-0.5, 0.0), so you will plot an N-by-N grid of points, evenly spaced in this region. As you increase N, you get a better approximation to the set, at the cost of more computation. Your program should make N a compile-time constant.

We now describe how to plot the points. The following simple PostScript program draws a box, defines a point-plotting subroutine, and calls the subroutine to plot five points.

%!
50 50 translate
0 0 moveto 0 512 rlineto 512 0 rlineto 0 -512 rlineto closepath stroke 
/pt { 0 360 arc fill } def
1.000 setgray 128 128 64 pt
0.000 setgray  64 356  8 pt
0.500 setgray 200 490 20 pt
0.250 setgray 412 428 32 pt
0.400 setgray 450.234 75.1 50.999 pt
showpage

To understand how it works, put this program into a text file called test.ps and type gs test.ps (to see the result on the screen) or lpr test.ps (to print the result). 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 one arguments between 0 (black) and 1 (white).

Your task is to write a C program that produces this PostScript program as output, except with different arguments for the setgray and pt routines (and many more calls on them). Your main challenge here will be to translate and scale the plane coordinates from the 2.0-by-2.0 box centered at (-0.5, 0) to the PostScript 512-by-512 box centered on the page whose lower left corner is at (0, 0). Also, be sure to adjust the radius of the circle as a function of N for optimum display. Choose the gray-scale for a point according to the number of iterations (0 = white, 255 = black) in the Mandelbrot calculation for that point. Use 1 - t/255.0 as the setgray value, where t is number of iterations. This ensures that all points in the set are colored black. Points just outside the set will be colored in shades of gray.

When you run your C program, redirect its output to a file with the comand a.out > mandgray32.ps. The file mandgray32.ps now contains a PostScript program! To debug, first make certain that your C program produces a valid PostScript program exactly like the sample program, except with different calls to pt and setgray. 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.

Part 3: color image. The third part of the assignment is to generate a color version of the Mandelbrot set. For each point, the Mandelbrot calculation returns a value between 0 and 255. Depending on this value, you will plot the point in a different color using the setrgbcolor routine. The routine takes three arguments between 0 and 1. Red, green, and blue are (1,0,0), (0,1,0), and (0,0,1), respectively. White is (0,0,0), black is (1,1,1). The following line plots a magenta circle.

0.800 0.800 0.000 setrgbcolor 128 128 64 pt

The file color.map supplies a table that gives the three setrgbcolor parameters for each possible iteration count between 0 and 255. If the Mandelbrot computation takes i iterations, then use the ith line from the table as the 3 arguments for setrgbcolor. To do this, define an array of 256 3-float C structures (using struct) and initialize it by reading the table from standard input (using scanf).

What to submit: Submit the C files mandgray.c and mandcolor.c, and the corresponding PostScript files mandgray32.ps and mandcolor32.ps with N = 32.

Challenge for the bored: There are limitless opportunities to avoid boredom here. For example, zoom way in on interesting parts of the set, near "edges" and sharp corners. Or, design a different color map.

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