The following is a fun little project I did for a third year math class during my undergrad.
The Mandelbrot set, discovered by Benoit Mandelbrot, is a visually striking fractal generated from a set of simple rules.
In this project, we present the stages of development to write a program to generate the Mandelbrot set. First, a basic program to generate the set is presented, followed by what improvements can be made visually, and how to improve performance.
The first stage of the program was the most basic and straightforward way to generate the Mandelbrot set. The screen has a 900 x 600 resolution. The program defines a minimum and maximum x and y value. We then iterate over all pixels, convert the coordinates of the pixel into a corresponding complex coordinate, and estimate whether that complex coordinate is in the Mandelbrot set.
Recall that to define the Mandelbrot set, we first define, for any complex number c, a sequence of complex numbers, such that
Then we can define the Mandelbrot set as
An important theorem when generating the Mandelbrot set is as follows: For any c, if |z_n| > 2 for any n, then c is not in the Mandelbrot set.
This gives us our way to tell if a given complex number is in the Mandelbrot set. We find the sequence z_0, z_1, ... up to z_100. If any of these have norm greater than 2, we stop - this point is not in the Mandelbrot set. Otherwise, we conclude that it is probably in the Mandelbrot set.
The justification for this is that most points not in the Mandelbrot set exceed two before 100 iterations. If a point not in the Mandelbrot set only exceeds two after more than 100 iterations, it is very probably very close to the Mandelbrot set, and drawing it as being in the Mandelbrot set still gives a fairly accurate picture.
Below is the actual code used to tell if something is in the Mandelbrot set.
This first version of the program can be downloaded here. Source code is avaiable here.
A few notes on the first version - it is slightly buggy, especially in terms of the zooming in functionality (this is fixed in the second version, available further down this page). To zoom in, simply left click on two corners of the rectangle you want to zoom in on.
The next obvious step in developing the program is to add colour. This is in fact a simple task to accomplish, and almost built in to the pre-existing code.
As mentioned before, the number of iterations it takes for a complex number to have norm greater than 2 is a good indicator of how close it is to the Mandelbrot set. So, instead of colouring pixels simply by whether they are in or not in the Mandelbrot set, we can colour them according to how close they are to the set. As the picture shows, this immediatley shows us some subtleties in the set that went previously unseen.
In this version of the program, the function that determines whether a point is in or out of the Mandelbrot set is replaced by a function that determines the colour a point is supposed to be. If the point is in the Mandelbrot set, it is coloured black. Otherwise, it is coloured blue, and as the number of iterations it took to note that the point was outside the set increases, we colour it a more intense blue. This provides a nice visual contrast between what is in the set, and what is close to the set.
This second version of the program can be downloaded here. Source code here Differences from the first version include added colour and zooming in properly working.
The last improvement made to the program is to improve its performance. When generating the image, the program spends a lot of time on each individual pixel. When working in a part of the picture where there's a lot of detail, this is necessary. However, when working in an area such as far into the interior of the set, or far out of the set, this is wasteful.
This motivates an alteration to the algorithm. Instead of testing each individual pixel (540,000 pixels), the program instead divides the screen into 5400 10x10 squares. The program then iterates over each square.
For each square, a test is made to determine the variance within that square. The four corner pixels of the square, as well as six pixels chosen at random within the square, are tested to see what they should be coloured. If it is found that all 10 pixels should be coloured the same, then it is considered to be reasonably certain that the entire square can be coloured one colour. If variance is found however, the old algorithm of individual colouring is used.
This algorithm can give a good performance, especially when there are large amounts of the picture are in the interior of the Mandelbrot set. Using the old algorithm, for each 10x10 square, we perform 100 calculations on each pixel, for a total of 10,000 calculations per square. With this new algorithm however, we only perform the calculations on 10 squares, or 1,000 squares.
The one drawback of this algorithm of course, is accuracy - it is entirely plausible that a square has details missed by the corners and a few random points.
In fact, this drawback is generally fairly small, due to the small size of the squares. Generally this loss of accuracy can be noted at bifurcation points.
Below, a picture that flips between two generated images - one with the fast algorithm and one with the slow one.
While we can see a slight loss of detail in the fast image, the picture over all is still very detailed and accurate. As well, it took 19 seconds to generate the slow image, but only 6.9 seconds to generate the fast one. This is a noticeable difference in time, while the loss of detail is only noticeable when the two are put on top of one another.
The final version of the project is available here. Source code is here
Here are a variety of images generated with this software.