COS 126Mandlebrot Set |
Programming Assignment 2Due: Wednesday, 11:59pm |

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