The Mandelbrot Set The Mandelbrot Set by Steven Flintham (15A) Introduction When the Mandelbrot set first came into prominence in the personal computing world there were several articles about it in various computer magazines. Following a request from Robin Morom in issue 36, I will attempt to explain what the Mandelbrot set is, but if you find this article confusing and/or badly written you might like to try one of these two magazines: Personal Computer World, December 1986, "Fractal Sets", page 196 onwards Acorn User, May 1986, "Join The Mandelbrot Set", page 80 onwards (note that the accompanying programs have several errors, detailed in the June 1986 "Blunderbox", page 18) Although not just about the Mandelbrot set, I also recommend "Chaos" by James Gleick, published by Sphere Books. If you find any errors in this article, please let me know. Complex numbers To understand how to plot the Mandelbrot set, a basic grasp of complex numbers is required. A complex number is made up of a real number and an imaginary number. A real number is just an everyday number like 4, -3 or 2.59. To be precise, most of the numbers people handle every day are rational, i.e. they can be expressed in the form a/b where a and b are integers ('whole numbers'). There is another set of numbers called irrational numbers and these are also real numbers, but this is a technicality. An imaginary number is a multiple of a 'special' number which is given the symbol i. This is defined as the square root of -1. The square of a number is the number produced by multiplying it by itself. For example, the square of 2 is 4 because 2x2=4 and the square of 3 is 9 because 3x3=9. The square root of a number is the number which must be squared to produce it. For example, the square root of 4 is 2 because 2 squared is 4 and the square root of 9 is 3 because 3 squared is 4. All positive real numbers have exactly one square root, which will be a positive real number. Using real numbers only, negative real numbers do not have a square root. For example, there is no real number (positive or negative) which when multipled by itself gives -4 (the 'obvious' answer -2 is wrong because -2x-2=4 not -4). This is inconvenient, so we invent the number i and say that the square root of -1 is i by definition (which simply means that we have decided this is the case rather than worked it out from something else). As a result of this, i squared (ixi) is -1 (just as 2x2=4 because 2 is the square root of 4). Having defined the square root of -1, we can now find the square root of any negative real number. This is done by simply finding the square root of the corresponding positive number and multiplying it by i. For example, the square root of -4 is i times the square root of 4, or -2i. As I said before, a complex number has both a real and an imaginary part. An example of a complex number is 3+4i, which has real part 3 and imaginary part 4i. 3+4i is NOT the same as 7i because i is just another number and (for example) 3+4x7 is clearly not the same as 7x7 ('replacing' i by 7). Complex numbers obey exactly the same rules of arithmetic as real numbers. This means that (for example): 3+4i + 7+2i = 10+6i 3+4i - (7+2i) = -4+2i (3+4i) x (7+2i) = 3x7 + 3x2i + 4ix7 + 8xixi (using the normal rule for multiplying out brackets) = 21 + 6i + 28i - 8 (since ixi=-1) = 13+34i To square a complex number, multiply it by itself as for a real number. For example, 3+4i squared is: (3+4i) x (3+4i) = 3x3 + 3x4i + 4ix3 + 4ix4i = 9 + 12i + 12i - 16 = -7+24i In general, a complex number a+ib squared is (axa-bxb)+(2xaxb)i. Finally, there is the concept of the magnitude of a complex number. The magnitude or 'size' of a real number is a fairly obvious idea - you simply ignore the sign (plus or minus) of the number, so that 6 is 'bigger' than 4 but 'smaller' than -7. The magnitude of a complex number is defined as the square root of the sum of the squares of the real and imaginary parts. That sounds rather forbidding, but it is very simple. For example, the complex number 3+4i has magnitude SQR(3x3 + 4x4) where SQR is the square root. If you are interested, the length of a line drawn from the point representing a complex number in an Argand diagram (see the next section) to the origin is the magnitude of the number. This length is found using Pythagoras' theorem. If I have thoroughly confused you by now then all you really need to know is that a complex number is a 'pair' of real numbers - for example, 13+34i could be considered as the pair (13,34). Argand diagrams You are probably familiar with the idea that real ('ordinary') numbers can be placed on a number line, like this: -2 -1 0 1 2 3 ...:---:---:---:---:---:... Similarly, complex numbers can be represented on a plane (just a two dimensional surface, like a table top) with the real component on the 'x' axis and the imaginary component on the 'y' axis, like this: Imaginary axis . . - 2 : : - 1 : -2 -1 : 1 2 ...:---:---0---:---:... Real axis : : - -1 : : - -2 . . Every complex number can be represented as a point on this diagram, which is called an Argand diagram. The Mandelbrot Set Every point on the Argand diagram either belongs to the Mandelbrot set or it doesn't! To see if it does, we use the following relationship: z becomes z squared plus k where z and k are both complex numbers. z is initially 0 (or 0+0i, if you prefer) and k is the complex number corresponding to the point we want to test. We apply this over and over again, producing a new value of z each time, until the magnitude of z is either greater than 2 or it becomes apparent that this will never happen. If the magnitude of z never becomes greater than 2 then we say that k lies in the Mandelbrot set. Each repeat of this calculation is called an iteration. If the magnitude of z does become greater than 2 there is no problem as we can see that this has happened. However, we can never be sure that the z will not become greater than 2. Suppose we have performed a million iterations and the magnitude of z is still less than 2. It is still possible that the next iteration will make the magnitude of z greater than 2. In other words, it would take an infinite number of iterations to be sure that a point is in the Mandelbrot set. Even a supercomputer is going to have problems repeating the calculation an infinite number of times. We therefore have to settle for being reasonably sure and decide that after an arbitrary number of iterations without z getting larger than 2 we will consider the point as being in the Mandelbrot set. This number must be reasonably large, otherwise we will include many points in the Mandelbrot set which are not really in it. 32 may be enough, but 128 or 256 is better and as one gets 'deeper' into the set higher levels may be necessary because all the points you are considering will take at least a certain number of iterations before the magnitude of z gets larger than 2. However, the maximum number must not be too large or the process will take too long. The process described above is just for ONE point on the Argand diagram. Since there are infinitely many real numbers, there are obviously an infinite number of points on the Argand diagram and so it is impossible to calculate them all, even if we don't perform an infinite number of calculations to see if a point lies in the Mandelbrot set. Plotting the Mandelbrot set Plots of the Mandelbrot set on computers are produced by treating the screen as an Argand diagram and plotting a point at each position whose colour depends on whether or not that point lies in the Mandelbrot set. This will obviously use only two colours, so it is usual to use one colour for those points in the Mandelbrot set and to colour points not in the Mandelbrot set depending on how many iterations it took to determine that they were not in the set. The screen does not have infinite resolution and so we just have to perform the above calculations for each pixel on the screen. Since you are likely to have a higher maximum number of iterations (say 256) that you have colours available, you will have to decide on a method of allocating colours. One solution is to divide the colours evenly over the possible number of iterations. Another is to divide the number of iterations by the number of colours availble and use the remainder as the number of the colour. In mode 2, for instance, a point which had taken 240 iterations to determine it was not in the Mandelbrot set would be plotted in colour 240 MOD 7=2. This method is particularly useful for producing plots in two colour modes. It is traditional for pixels which took the maximum number of iterations (i.e. those which we are considering as in the Mandelbrot set) to be black. It is also quite common for no other number of iterations (even one less) to use black, although this is not always a good idea (two colour plots, for instance). It is usual to produce square plots of the Mandelbrot set, but this is not necessary. The 'standard' Mandelbrot 'beetle' (I think it looks more like a pear) is produced by plotting the region with real components from -2.0 to 0.5 and imaginary components from -1.25 to 1.25. The detail within this region depends on the resulution of the screen - the more pixels we have across or up the screen the smaller we can make the step between the components of the points we plot. We use the actual components when testing the point, obviously, but when we come to plot them we must convert to screen coordinates. This is just a scaling operation and for the 'beetle' plot we could use something like this (in BBC BASIC): screen_x%=(real+2.0)*1280/2.5 (2.5 because the 'width' is 0.5-2.0=2.5) screen_y%=(real+1.25)*1024/2.5 (2.5 because the 'height' is 1.25-(-1.25)=2.5) This is a square plot but we have used the full width and height of the screen, so there will be some horizontal 'stretching'. If this bothers you you could replace the 1280 with 1024 in the expression for screen_x% or increase the 'width' of the plot from 2.5 to 2.5*(1280/1024)=3.125 (by adjusting the real components corresponding to the minimum and maximum real components, such as using the range -2 to 1.25). However, since the Mandelbrot set is an abstract object I don't suppose it really matters if it is 'distorted'. The accompanying program Mandel plots a specified region of the Mandelbrot set. I have written this with readability rather than speed of execution in mind so that you can see how it works. In other words, it should be possible to write a BASIC program which will plot the set to the same level of detail more quickly, or which has more features. It should be straightforward to use - it will wait for you to press SPACE before clearing the screen afterwards. It is quite slow, so you may want to run it overnight and if you want to keep a copy of the screen, make sure that there is room on the disc for the saved screen and that you are not using a shadow mode. The accompanying mode 0 screen was produced with this program using the following parameters: Real components from -2 to 1.25 Complex components from -1.25 to 1.25 Maximum number of iterations: 32 The program should also be fairly easy to understand, but the main points are mentioned here. Since BASIC does not support complex numbers, the program handles the real and imaginary components separately. FNmandelbrot performs the iterations and is called by PROCplot_set which handles converting between screen coordinates and the corresponding complex number. Note the use of the variable old_z_real in FNmandelbrot - this is needed because the two calculations to square z are not intended to come in sequence but occur (at least theoretically) simultaneously, so it is important to use the old real component in both. This is no problem for the calculating the new real component but by the time the new complex component is to be calculated z_real has been overwritten by its new value. FNcolour simply chooses a colour number depending on the number of iterations - this is not a particularly good routine but it is nice and simple for demonstration purposes. If you want to write your own Mandelbrot program, I would suggest writing the number of iterations performed for each pixel to a file, possibly using a simple plot routine like the one used here so that you can monitor progress. You can then experiment fairly quickly with different methods of plotting the data from the file. An apology Finally, I would like to apologise for any mathematical errors and inconsistencies in this article. I have a suspicion that there are numerous little slips in terminology - please do let me know about them, but don't be too hard on me. I am also aware that the mathematics of the Mandelbrot set go much deeper than the relatively simple calculations involved in plotting it, but I know nothing about this at the moment and I suspect that it would be of little interest to most people anyway.