Papers
Papers
Home > Papers > Parallel Fractals
Introduction | Mandelbrot Set | Image Characteristics | Parallel Algorithm Design | Partitioning | Agglomeration | Output Synchronization | Token-Passing | Polling | Performance Analysis | Conclusion | Bibliography | Slides

Parallel Fractal Image Generation
The Mandelbrot Set

Fractals are generated by calculating certain formulas over and over again, feeding the results of one step back into the next step. For example, the Mandelbrot set, the most well-known fractal object first described by Benoit Mandelbrot, is created by iterating a simple formula over complex numbers.

A complex number C consists of two components – a "real" part Re C, and an "imaginary" part Im C. The imaginary part is multiplied by the constant i, defined as the square root of –1:

C = Re C + Im C * i; where i := sqrt (-1)

Although complex numbers look like an abstract mathematical contraption that has no connection with the real world, they are as realistic as the real number space that we are used to. In fact, complex numbers are routinely used by electrical engineers to design the devices we use every day, so they are indeed a valid means of describing the world. To make complex numbers a bit easier to grasp, we can visualize them as points with the coordinates (x, yi) on a plane, as shown in Figure 1:

Figure 1: The complex plane
Figure 1: The complex plane

The magnitude of a complex number, |C|, ist defined as that point's distance from the origin of the complex plane and calculated as

|C| = sqrt ((Re C)^2 + (Im C)^2) = sqrt (x^2 + y^2)

Now, to start creating a fractal image, we choose an arbitrary point C from the complex plane and plug it into the following simple iteration formula:

Z[0] = 0; Z[n+1] = Z[n]^2 + C

This is the formula Benoit Mandelbrot first described. It takes the current point Zn (for the first iteration, this is Z0, the origin), squares it, adds the constant C we chose before, and so arrives at a new point Zn+1. This point is again squared, C is added, and so on. We perform this iteration several times and see how the values of Z develop.

For example, if we choose C = –1.0 + 0.5i, we get the series of values of Z shown in Table 1:

n Re Zn Im Zn |Zn|
0 0.0000000000000 0.0000000000000 0.00000000000000
1 -1.0000000000000 0.5000000000000 1.11803398874990
2 -0.2500000000000 -0.5000000000000 0.55901699437495
3 -1.1875000000000 0.7500000000000 1.40451281589030
4 -0.1523437500000 -1.2812500000000 1.29027523446130
5 -2.6183929443359 0.8903808593750 2.76563910980620
6 5.0632035362069 -4.1627339199185 6.55472224713590
7 7.3076763610173 -41.6535382072400 42.28970771924700
8 -1682.6151113846000 -608.2811530195500 1789.18964175920000
9 2461186.6519410000000 2047006.6200823000000 3201199.12507070000000
10 1867203633030.9000000000000 10076130739563.0000000000000 1024767583835.30000000000000
... ... ... ...

Table 1: Iteration approaching infinity with C = –1.0 + 0.5i

We observe that Z moves out towards infinity within very few iterations. Somehow, this is what we might expect since we are constantly squaring and adding numbers.

However, if we try a different choice of C, for example C = 0.25 – 0.25i, we get the results in Table 2:

n Re Zn Im Zn |Zn|
0 0.000000000000000 0.00000000000000 0.00000000000000
1 0.250000000000000 -0.25000000000000 0.35355339059327
2 0.250000000000000 -0.37500000000000 0.45069390943300
3 0.171875000000000 -0.43750000000000 0.47005027989035
4 0.088134765625000 -0.40039062500000 0.40997608405816
5 0.097455084323883 -0.32057666778564 0.33506252161220
6 0.156728093532030 -0.31248365238264 0.34958508021450
7 0.176917662295790 -0.34794993419571 0.39034473986338
8 0.160230702525410 -0.37311697790776 0.40606669062459
9 0.136457598828770 -0.36956959098863 0.39395730588684
10 0.132038993694610 -0.35086115797288 0.37488377936362
... ... ... ...

Table 2: Beginning iteration with C = 0.25 – 0.25i

Surprisingly, Z stays within close range of the origin. If we iterate some more, we find that Z actually converges to a certain point (Table 3):

n Re Zn Im Zn |Zn|
... ... ... ...
114 0.14644660940674 -0.35355339059328 0.38268343236510
115 0.14644660940673 -0.35355339059328 0.38268343236510
116 0.14644660940672 -0.35355339059328 0.38268343236509
117 0.14644660940672 -0.35355339059327 0.38268343236509
118 0.14644660940673 -0.35355339059327 0.38268343236509
119 0.14644660940673 -0.35355339059327 0.38268343236509
120 0.14644660940673 -0.35355339059328 0.38268343236509
121 0.14644660940673 -0.35355339059328 0.38268343236509
122 0.14644660940672 -0.35355339059327 0.38268343236509
123 0.14644660940673 -0.35355339059327 0.38268343236509
124 0.14644660940673 -0.35355339059327 0.38268343236509
125 0.14644660940673 -0.35355339059327 0.38268343236509
... ... ... ...

Table 3: Converging iteration with C = 0.25 – 0.25i

Obviously, Z shows very different behaviour (converging vs. escaping to infinity) depending on our initial choice of C. To see how the two are related, we apply the iteration formula to every point C on the complex plane and color it according to the behavior if the iteration – if Z converges, we mark C black, and if Z escapes to infinity, we leave C white. The result is the graph shown in Figure 2:

Figure 2: The Mandelbrot set
Figure 2: The Mandelbrot set

We have plotted the Mandelbrot set – the set of all points for which the iteration formula does not escape to infinity after a certain maximum number of iterations. It is a fractal with a solid interior, but an extremely convoluted edge that shows infinite detail and self-similarity when we look at it more closely.

Introduction | Fractal Image Characteristics >

© 2001 Matthias Book