02 Jan 2015

Compute the Mandelbrot Set

Images of the Mandelbrot set display an elaborate boundary that reveals progressively ever-finer recursive detail at increasing magnifications. The “style” of this repeating detail depends on the region of the set being examined. The set’s boundary also incorporates smaller versions of the main shape, so the fractal property of self-similarity applies to the entire set, and not just to its parts. [1]

 Definition

The Mandelbrot set is an visualization of the behavior of the following recursive function (A function, where the result of the current calculation n depends on the result of the previous calculation n-1) .

    \[ f(\(z_{n})= z_{n-1}^{2} + c \]

Part of this Mandelbrot set are all complex numbers c for which the recursive function converge, which is also the challenge about ‘computing the Mandelbrot set’.  It’s a trade off between performance and the resolution of the Mandelbrot set. The following video, which is an art project of teamfresh, shows a zoom-in with a respectable resolution. As mentioned by the authors, the computation take them six months. The video also shows the self-similarity of the Mandelbrot set.


Last Lights On – Mandelbrot fractal zoom to 6.066 e228 (2^760) .

The following link shows a HTML5 demo of the Mandelbrot set ( it’s possible to zoom-in with a mouse click or you can zoom-in/out with the mouse-wheel )

Demo

Complex numbers

For the computation of the Mandelbrot set it’s inescapable to take a closer look to the basics of complex numbers (very rudimentary). A complex number exists of two real numbers, lets say x and y. The real number x represents the real part  and y the imaginary part of the complex number.

    \[ z = ( x | y) \]

The following calculation rules will simplify the computation of the Mandelbrot set.

Addition

    \[ z_{1} + z_{2} = (x_{1} + x_{2}  |  y_{1} + y_{2}) \]

Subtraction

    \[ z_{1} + z_{2} = (x_{1} - x_{2}  |  y_{1} - y_{2}) \]

Multiplication

    \[ z_{1} + z_{2} = (x_{1} *  x_{2}  - y_{1} * y_{2}  | x_{1} * y_{2} + x_{2} *  y_{1}) \]

Absolute value of z

The absolute value of the complex number is very important for the computation of the Mandelbrot set, because it can be used as indicator for convergence.  The absolute value corresponds to the length of the vector z.

    \[ z  = \sqrt{ (x ^ {2} + y ^ {2}) } \]

Manual computation

As mentioned before, the Mandelbrot set is an visualization of all complex numbers c for which the function converge.

Lets take a complex number c, for example:

    \[ c  = (0.5 | 0.5) \]

This number is a constant, now we need a initial value for z to start the computation. The initial value of the Mandelbrot set is the following (and always the same).

    \[ z  = (0 | 0) \]

The computation:

    \[  f_{1}  = (0 | 0) ^{2} + ( 0.5 | 0.5 ) = (0 | 0.5) \]

    \[  f_{2}  = (0 | 0.5) ^{2} + ( 0.5 | 0.5 ) = (0.5 | 1.0) \]

    \[  f_{3}  = (0.5 | 1.0)^{2} + ( 0.5 | 0.5 ) = (0.5 | 1.5) \]

    \[  f_{4}  = (0.5 | 1.5)^{2} + ( 0.5 | 0.5 ) = (-0.25 | -0.25) \]

    \[  ..... \]

Visualization

For the visualization the following interval is used for the complex number c:

    \[  [-1,2] [-1,1] \]

For every complex number part of this interval the function, shown above, is computed, theoretically infinity steps, but this is computationally infeasible. So a convergence criterion is required.

The complex numbers c can be divided into two groups:

  • inside the Mandelbrot set, that means, the result of the computation (for all steps n) is always inside the given interval (defines the form of the Mandelbrot set), to say this sequence converges.
  • outside the Mandelbrot set, that means the result of the computation will leave the interval, to say this sequence diverge.

The divergency can be determined with following criteria:

    \[ | f(z_{n}) | > 2 \]

Implementation of f(z)

A implementation of the function, which makes use of the recursive characteristics, can look like this (JavaScript):

function f_recursive(r, i, cr, ci, n) {
    var rn = r * r - i * i + cr;
    i = 2 * r * i + ci;
    if (rn * rn + i * i >= 4 || n === 0) {
        return n;
    }
    return f(rn, i, cr, ci, n - 1);
}

The recursive implementation (using JavaScript, Firefox) seems to be much slower than the iterative variant.

function f(r, i, cr, ci, n) {
    while (n > 0 && r * r + i * i < 4) {
        var rn = r;
        rn = r * r - i * i + cr;
        i = 2 * r * i + ci;
        r = rn;
        n = n - 1;
    }
    return n;
}

Implementation of the visualization

This is a way to implement the visualization using the HTML5 methods createImageData() and putImageData(). The variable ctx is thereby the 2D-context of the canvas container.

function mandelBrotSet(itn) {
    var img = ctx.createImageData(cwidth, cheight);
    var ci = 1.0;
    for (y = 0; y < cheight; y++) {
        var cr = -2.0;
        for (x = 0; x < cwidth; x++) {
            var n = f(0.0, 0.0, cr, ci, itn);
            var pos = y * cwidth * 4 + x * 4;
            img.data[pos] = n; //Read
            img.data[pos + 1] = n;  //Green
            img.data[pos + 2] = n;  //Blue
            img.data[pos + 3] = 255; // Opacity
            cr = cr + dx;
        }
        ci = ci - dy;
    }
    ctx.putImageData(img, 0, 0);
}

The source files of the HTML5 demo can be downloaded with the following link.

Download script

Leave a Reply