Monday, October 20, 2008

WTF is mandelbrot set?!

I don't know why I like this stuff.. I don't pretend to completely understand it. I think it just infinitely zooms in (or out) on itself with a repetitious pattern & maintaining its integrity throughout.. I think that's beautiful..

The following is taken from Wikipedia, the free encyclopedia

In mathematics, the Mandelbrot set, named after Benoît Mandelbrot, is a set of points in the complex plane, the boundary of which forms a fractal. Mathematically, the Mandelbrot set can be defined as the set of complex c-values for which the orbit of 0 under iteration of the complex quadratic polynomial xn+1 = xn2 + c remains bounded.[1] That is, a complex number, c, is in the Mandelbrot set if, when starting with x0=0 and applying the iteration repeatedly, the absolute value of xn never exceeds a certain number (that number depends on c) however large n gets.

Eg. c = 1 gives the sequence 0, 1, 2, 5, 26… which leads to infinity. As this sequence is unbounded, 1 is not an element of the Mandelbrot set.

On the other hand, c = i gives the sequence 0, i, (-1 + i), -i, (-1 + i), -i…, which is bounded, and so it belongs to the Mandelbrot set.

When computed and graphed on the complex plane, the Mandelbrot Set is seen to have an elaborate boundary, which does not simplify at any given magnification. This qualifies the boundary as a fractal.

The Mandelbrot set has become popular outside mathematics both for its aesthetic appeal and for being a complicated structure arising from a simple definition. Benoît Mandelbrot and others worked hard to communicate this area of mathematics to the public.

Phoenix Set magnification

For programmers:
The definition of the Mandelbrot set, together with its basic properties, suggests a simple algorithm for drawing a picture of the Mandelbrot set. The region of the complex plane we are considering is subdivided into a certain number of pixels. To colour any such pixel, let be the midpoint of that pixel. We now iterate the critical value c under Pc, checking at each step whether the orbit point has modulus larger than 2.

If this is the case, we know that the midpoint does not belong to the Mandelbrot set, and we colour our pixel. (Either we colour it white to get the simple mathematical image or colour it according to the number of iterations used to get the well-known colourful images). Otherwise, we keep iterating for a certain (large, but fixed) number of steps, after which we decide that our parameter is "probably" in the Mandelbrot set, or at least very close to it, and colour the pixel black.

In pseudocode, this algorithm would look as follows.
For each pixel on the screen do:
x = x0 = x co-ordinate of pixel
y = y0 = y co-ordinate of pixel
iteration = 0
max_iteration = 1000
while ( x*x + y*y <= (2*2) AND iteration < max_iteration )
xtemp = x*x - y*y + x0
y = 2*x*y + y0
x = xtemp
iteration = iteration + 1
if ( iteration == max_iteration )
colour = black
colour = iteration
where, relating the pseudocode to c and Pc:
* z = x + iy
* z2 = x2 + i2xy - y2
* c = x0 + iy0
and so, as can be seen in the pseudocode in the computation of x and y:
* x = Re(z2 + c) = x2 - y2 + x0 and y = Im(z2 + c) = 2xy + y0

To get colourful images of the set, the assignment of a colour to each value of the number of executed iterations can be made using one of a variety of functions (linear, exponential, etc). One practical way to do it, without slowing down the calculations, is to use the number of executed iterations as an entry to a look-up colour palette table initialized at startup. If the colour table has, for instance, 500 entries, then you can use n mod 500, where n is the number of iterations, to select the colour to use. You can initialize the colour palette matrix in various different ways, depending on what special feature of the escape behavior you want to emphasize graphically.

No comments: