The Mandelbrot Set
The Mandelbrot set is a classic application of complex arithmetic. It is the example of a fractal set.
Here and in the future we are going to try to separate the mathematical definition of our data from its display on the screen. In fact we won’t even add the screen display till the second iteration of the program.
Our data structure will be a two dimensional array, each element of which represents a fixed point in the complex plane. The array is defined by the value of the lower left point, the gap between points and the number of pixels in the x and y directions. Thus given that element (0,0) of the array matches the complex point (x0,y0), each point is separated by a value gap, we know that element i,j of the array represents the point (x0 + i*gap, y0 + j*gap) in the complex plane. Since we know this by position of the array element alone we dont’ need to store this value in the array.
What will we store in each element of this array? We’ll calculate a number to go there in the following fashion. Let z = 0 + 0i and let c be the position of that array element in complex space. calculate z = z*z + c and iterate as follows up to 200 times:
for (i=0; i < 200; i++) {
z = z.Times(z) + c;
}
The Mandelbrot set is composed of those elements which, no matter how long we do this, never approach infinity. Since infinity can take a mighty long time to approach, it's fortunate that a fairly elementary theorem in complex variable theory guarantees that any number whose magnitude ever exceeds two in this iterative scheme will become as large as one might wish. (i.e. They asymptotically approach infinity.) Therefore once a number exceeds two we can break out of the loop and say definitively that this number is not in the Mandelbrot set.
Unfortunately there's no guarantee that just because an element doesn't reach 2 in two hundred iterations it might not reach two on the two hundredth and first iteration or the two thousandth or the two millionth. However most numbers that don't prove they're not in the Mandelbrot Set by the two hundredth iteration are reasonably likely to be in it.
Here's how the code will work. First we'll select the lower left hand corner of our rectangle in complex space, the size of the gap between the points and the number of points in each dimension. For a specific example we can choose the square bordered on the lower left by (-2,-2) and on the upper right by (2,2). To keep initial computations manageable we'll break this up into an array of 101 by 101 elements which implies a gap size of 0.05.
Once this array is created we'll loop through it and fill each element with a Boolean value, true if the element is probably in the Mandelbrot Set (doesn't pass two in two hundred iterations) and false if it's not (does pass two and thus go to infinity). Here's the code:
class MandelApp {
public static void main(String args[]) {
int xdim = 101;
int ydim = 101;
double xstart = -2.0;
double ystart = -2.0;
boolean Mandel[][] = new boolean[xdim][ydim];
double gap = 0.05;
int max_iterations = 200;
int i,j,k;
Complex z, c;
for (i=0; i < xdim; i++) {
for (j=0; j < ydim; j++) {
c = new Complex(xstart + i*gap ,ystart + j*gap);
z = new Complex(0.0, 0.0);
k=0;
while (z.Magnitude() < 2.0 && k < max_iterations) {
z = z.Times(z);
z = z.Plus(c);
k++;
}
if (z.Magnitude() < 2.0) {
Mandel[i][j] = true;
}
else Mandel[i][j] = false;
}
}
}
}
Drawing the Mandelbrot Set
To make this interesting we want to actually draw pictures of the Mandelbrot Set. To do this we'll move the actual calculation into a thread in an applet and then draw the results into a bitmap. Here's the code:
import java.applet.Applet;
import java.awt.*;
public class Mandelbrot extends Applet {
int xdim;
int ydim;
double xstart = -2.0;
double ystart = -1.25;
int Mandel[][];
double gap = 0.05;
int max_iterations = 256;
public void paint(Graphics g) {
int i,j,k;
Complex z, c;
xdim = size().width;
ydim = size().height;
gap = 2.5/ydim;
Mandel = new int[xdim][ydim];
for (i=0; i < xdim; i++) {
for (j=0; j < ydim; j++) {
c = new Complex(xstart + i*gap, ystart + j*gap);
z = new Complex(0.0, 0.0);
for (k = 0; z.Magnitude() < 2.0 && k < max_iterations; k++) {
z = z.Times(z);
z = z.Plus(c);
}
g.setColor(selectColor(k));
g.fillRect(i, j, 1, 1);
}
}
}
protected Color selectColor (int num_iterations) {
if (num_iterations > max_iterations) return Color.black;
else if (num_iterations > 9*max_iterations/10) return Color.darkGray;
else if (num_iterations > 8*max_iterations/10) return Color.gray;
else if (num_iterations > 7*max_iterations/10) return Color.magenta;
else if (num_iterations > 6*max_iterations/10) return Color.cyan;
else if (num_iterations > 5*max_iterations/10) return Color.blue;
else if (num_iterations > 4*max_iterations/10) return Color.green;
else if (num_iterations > 3*max_iterations/10) return Color.yellow;
else if (num_iterations > 2*max_iterations/10) return Color.orange;
else if (num_iterations > 1*max_iterations/10) return Color.red;
else return Color.white;
}
}
This program is minimal. It should really create an ImageProducer which draws the Mandelbrot set. There are also a lot of additions that could be made to the parameters to allow for zooming in on particular regions. In fact you could even implement this as a Canvas in an applet with various controls to select the area of interest. This will all be investigated in the Cafe Au Lait newsletter.
For more details on the Mandelbrot Set see the first chapter of A.K. Dewdney’s The Armchair Universe.
Exercises
1. Explore different starting points and gap sizes for the Mandelbrot set. To make this easier add user input to dynamically select the starting point and gap size.
2. What happens if you allow the x and y gap size to be chosen independently?