Playing around with the Mandelbrot Set
What does a geek do when he’s given a little downtime during a week of conference talks and meetings? He plays with the Mandelbrot set.
I’ve been getting into vector programming – the nitty-gritty low-level programming we are finding necessary to squeeze every last bit of performance out of modern Intel CPUs. It isn’t exactly new; It is a rehash of old techniques used way back in the 1970s but with some modern nuances that make it a hot area of research once again. I decided to write a short routine that computes the Mandelbrot set for a given set of coordinates and bounds criteria and then dumps an image out in a PNG file.
What is the Mandelbrot set? We could spend a day going into this so I will give a watered down explanation and leave you to Google for further info. There are many resources out there.
The Mandelbrot set is generated by iterating the following complex function repeatedly until future values remain bounded (do not go off to infinity) or else do not remain bounded:
where and are both complex numbers. For the Mandelbrot set we always start with and compute for some value of . That value is then used as the next value of and we repeat the calculation. Another way to write this as an iterative expression is thus
To generate the set we use values for that cover the complex plane in the region of interest. Since it is a complex number, the x-coordinate of the plane is the real part and the y-coordinate is the imaginary part. It is known that for any absolute value of the series will be unbounded, and thus is not part of the set. We then only need to focus on the region of the complex plane from . The computational algorithm does just that. We start from the upper left corner and sweep to the lower right-hand corner, setting to the coordinates of each pixel we are computing. If this location produces an iterated set that remains bounded it gets colored black. Thus all black points of the image are those points contained within the Mandelbrot set. If the particular set of coordinates (value of ) produces a point that is unbounded, then we can do something fun; We assign a point a color based on how fast it goes “out of bounds”. The orange parts of the image below are those for which the iterates grow very large, very fast.
Cool and strange things happen along the boundaries of the Mandelbrot set. It exhibits the phenomenon of self-similarity, a fractal scaling seen in physical systems undergoing phase transitions and in other branches of mathematics. What this means is that as you zoom in and create ever more detailed images of what is happening in these areas, you start to see subsections that resemble the overall set. You can also see some other amazing structures. The whole process of zooming in to different areas of the boundary regions can produce an Alice In Wonderland trippy rabbit hole effect. The final animation created (below) shows this.
After an hour or so of writing the code and running it on my laptop I was quite pleased. The last time I did anything of the sort was waaaaay back in 1984 on my old Commodor 64. At that time I wrote the code in BASIC and the image sizes were much, much smaller with very blocky resolutions. Right now I’m creating simple 640 x 480 pixel sized images and they are much more impressive.
There is no GUI to my application to drive things, no way to decide where to zoom in and explore the set. I found an open source app for this next bit, the fantabulous fraqtive package. This will already generate the Mandelbrot set but, being open source, it allowed me to swap in my own routine for doing the calculations while keeping the GUI bits. This allowed me to do something I could never have dreamed of doing on the old C-64 days: Generate enough images to create an animation.
After plugging in my code and compiling the package I did an initial test to find some interesting spots to zoom around and explore. For this first animation I wanted to find areas that kept repeating the overall appearance of the larger set image. Once I arrived at my final spot I was able to use the series creation routine built into fraqtive to generate 10,000 frames that go from the initial set to deep inside the set, a scale of 10^32 in fact.
I’m not blown away by the image quality. Creating the MPEG animation loses quite a bit and the small image size used was another issue. I am, however, impressed by the speed with which this was done. The time to generate the 10,000 frames was less than 20 minutes and the time to assemble them into an animation (using the open source ffmpeg package) was under 7 minutes. All of this was done on a fall 2015 Macbook Pro.
My goal is to run this vectorized code on a large cluster of multiple-core CPUs such that the actual animation will be produced in real-time. It is similar to a much older program named pmandel that ships as an example program with Argonne National Laboratory‘s mpich package but without the reliance on MPI for the heavy workload.