Update

[less_retarded_wiki.git] / mandelbrot_set.md

# Mandelbrot Set

Mandelbrot set (also M-set) is a famous two dimensional [fractal](fractal.md), a [set](set.md) of [points](point.md) in two dimensional plane that are defined by a specific very simple equation. It turns out this set has an infinitely complex border (i.e. its shape is a fractal) and the whole thing is just [beautiful](beauty.md) to look at, especially when we draw it with colors and start zooming in to various interesting places -- patterns keep emerging down to infinitely small scales so we may keep zooming in forever and still discover new and new things; some patterns show self similarity, some not. Applying tricks to further add colors to inside and outside of the set increases the visual beauty yet more -- rendering Mandelbrot set is in fact a quite popular activity among programmers as it's very easy to [program](programming.md) such visualizations (at least until we reach the limits of [floating point](float.md) precision, then some more cleverness has to be applied; and yes, Mandelbrot can also be rendered only using [fixed point](fixed_point.md)). The origins of exploring this set are somewhere around 1905 when Fatou and Julia explored the equations related to it, however due to the lack of [computers](computer.md) the set couldn't very well be drawn -- this was only achieved much later, the first rendering of the set seems to be from 1978, albeit of very poor resolution. The set is named after Benoit Mandelbrot who is often considered the father of the field of fractal geometry and who researched this particular set a lot. Of course, Mandelbrot set is awesome, it's a like a whole infinite world to explore, hidden in just one simple formula.

{ Pretty amazing ASCII rendering of the Mandelbrot set can be found at http://www.mrob.com/pub/muency/asciigraphics.html. ~drummyfish }

```
 ___________________________________________________________
|[-2,1]                                       .             |
|                                            .:.            |
|                                           :::::           |
|                                         ...:::..  .       |
|                                    :..:::::::::::::....   |
|                                   .:::::::::::::::::::'   |
|                                 ::::::::::::::::::::::::  |
|                                :::::::::::::::::::::::::' |
|                     :..:::.   .:::::::::::::::::::::::::: |
|                   .:::::::::. ::::::::::::::::::::::::::  |
|                .. ::::::::::: :::::::::::::::::::::::::'  |
|      '  '     '::':::::::::::'::::::::::::::::::::::::.   |
|                   ::::::::::: ::::::::::::::::::::::::::  |
|                    ':::::::'  ::::::::::::::::::::::::::. |
|                     '  '''     :::::::::::::::::::::::::' |
|                                '::::::::::::::::::::::::' |
|                                 ''::::::::::::::::::::''  |
|                                    ::::::::::::::::::::   |
|                                    '  ''::::::::'':       |
|                                           .:::.           |
|                                           ':::'           |
|                                             :             |
|___________________________________________________[0.5,-1]|
 ___________________________________________________________
| ''.:.:':::::  '' :.'..::'::.:''.::.::: .:''' :'.::'.:'':':|
|: ::.''.':'::::.'  :.'::::'::::.:::..' .:::: : ::'::::'::::|
|::' . :::: ' ::. : :'   :.'::.' .:::''.'::'.: ':.:.':':':.'|
|'::: .'.':.' '':.    ..'.'::::':.':::' ..:'::'. ':::'.':::'|
| ::::..'::'.'.'.'.: : :: ::::': .:. :''..::.::... :..':::::|
|:':::  ':.:::... ':''.: ..::::'::':::': :'::'':: '': :.':'.|
|:::.:':::':. :::.':...::: :  .  ''.'.: .:.  '.::::  .::'  :|
|:::::'.'' .::':. :..:.::.::..'   .::. ::''   :''           |
|::::::  :.::''''. ::. .:'::::.    .':''.     '    . ...': :|
|:::''''' :''   :'':::  '.':''      :          . . '':':'.'.|
|':''':::..     ::'::.::.' .        '      :':::::.:::: .:::|
|:.  .:.::..  '': '  ::. ':::          .    '':::'..::' :.'.|
|:: :  :. '        '..::  '          :::  : .':::.:::::'::::|
|..::.::' .    ...:'':.'        ::.'.':'': ':':'.:.:'':::..:|
|.::::::::           ':         .'''.....:: ::.'::.:.....'. |
|:::::::::.          .'        .  ' ':.::::.. :':.' : ': '  |
|:::::::::.'                 :':.  ''.':::. .:: :.. .:':.  '|
|:.::::'':':              .:.:: ::'':. .'::'.::'.:.  '.:   '|
|:..''''':               :.::::'.     ::. : :'''':'::    .::|
|    :::  '. .        .. '':'::::: '.:: :.:'. ..''' :.. ':'.|
|:  :::'  ::...      :..::.::::.::::': .::'':.:':::::    . :|
|'..   . '.. ''       .: ::::: '::::::.':.:..:.::.  '   .:.'|
|::....   '           . ' :: '.'::::::.:..'':. ''::'   .'  '|
|:':.:::.                    ..'..'': :..:''' .. :'  '   .':|
|  .'::::              :. . . ':::::.:.'::..' . .::::   :. .|
| .::.::               '..:'. :''.::':::''::'..:: ' '   ::''|
|:'' .:'::.          ': ::''::''. ..:'' :: :::::.:::.   ' ':|
|::.:.' .'''        .::::::::..':.''':  ':...::''.:: .'   ..|
| :':'     '        . :::::':':..::::::..'.:::':'::'':'   ' |
|'':                . '::''::: ::::::'.:.:::  : . '' '     '|
|___________________________________________________________|
```

*Simple ASCII rendering of Mandelbrot set, below a zoomed-in detail.*

**Definition**: we use [complex numbers](complex_number.md) to define the set. Consider the following series of complex numbers *z[n]*:

*z[0] = 0*, *z[n + 1] = z[n]^2 + p*

Mandelbrot set is the set of all points *p* for which the [absolute value](abs.md) ("length") of *z[n]* stays bounded (i.e. doesn't grow beyond any limits) as *n* goes towards infinity.

NOTE: here is the series equation rewritten to just work with *x* and *y* coordinates. Checking the point *[px,py]*, your series will be *x[n + 1] = x[n]^2 - y[n]^2 + px* and *y[n + 1] = 2 * x[n] * y[n] + py*.

I.e. taking any point *p* in the complex plane (whose real and imaginary parts we see as the *x* and *y* coordinates), plugging it into the above equation and iterating the series infinitely many times, if the absolute value of *z[n]* stays bounded under some finite value (even very large, just not infinitely large), the number belongs to the set, otherwise not (if the absolute value diverges towards infinity). I.e. in other words the Mandelbrot set is a set of kind of "well behaved" points that don't shoot away to infinity when we keep applying some operation to them over and over. Of course computers cannot evaluate infinitely many iterations of the series so they cannot compute the set 100% accurately, but we may very well [approximate](approximation.md) by performing many iterations (let's 100000) and seeing if the value we get is "very large" (let's say 1000000000) when we stop -- this will work correctly for most points and those few points near the set borders where we make a wrong guess won't really be noticed unless we zoom in very close -- in such cases we can simply perform more iterations to increase precision. To add **[colors](color.md)** to the visualization (so that we don't observe just the borders but also some kind of structure inside and outside of the set) we may simply assign different colors to the points depending e.g. on how big the absolute value is at the time we stop the evaluation, or how many iterations it took for the absolute value to exceed given limit (for points outside the set). Also note that for nice pictures we should apply [antialiasing](antialiasing.md). Additional fancy filters and [shaders](shader.md) such as some kind of postprocessing or fake 3D can also be applied to make the result even more impressive.

There are further **[optimizations](optimization.md)** we may apply to calculate the set faster. The set itself also lies in the circle centered at [0,0] with radius 2, so points outside this area can be safely marked as lying outside the set. Furthermore it's proven that if absolute value of *z[n]* ever gets greater than 2, the point won't lie in the set (because getting absolute value greater than 2 basically means we start checking a point that inevitably lies outside the circle with radius 2 inside which the whole set lies, so we know the point won't lie in the set). A quick [bailout](bailout.md) check (not requiring square roots etc.) here can therefore be e.g. checking if either the real of imaginary component absolute value exceeds 2 (which implies the whole vector length must exceed 2 as well), or checking if the sum of squares of the components exceeds 4 (i.e. we squared both sides of the equation and got rid of the square root). [Symmetry](symmetry.md) of the set can also be used to skip computing some points. Further more complex optimizations exist, based e.g. on estimating distance of any given point to the set border etc.

**Quick example**: does point *[-0.75,1]* lie in the Mandelbrot set? Taking the above *x* and *y* coordinate equations we set *px = -0.75* and *py = 1*, our starting values are also these, i.e. *x[0] = -0.75* and *y[0] = 1*. Now *x[1] = x[0]^2 - y[0]^2 + px = (-0.75)^2 - 1^2 - 0.75 ~= -1.1875*, *y[1] = 2 * x[0] * y[0] + py = 2 * -0.75 * 1 + 1 ~= -0.5*. So after first iteration we got to approximately *[-1.1875,-0.5]*, the length of this vector is *sqrt((-1.1875)^2 + (-0.5)^2) ~= 1.28*, so we're still in the game. Now we repeat this all with these new coordinates, getting *x[2] ~= 0.4101* and *y[2] ~= 2.1875*, with length of the vector *sqrt(0.4101^2 + 2.1875^2) ~= 2.2256*. This value surpassed 2, so by the mentioned optimization we now know iterating further the value will only be getting higher and higher until infinity, so we conclude the original point *[-0.75,1]* does NOT lie in the Mandelbrot set.

As an alternative to drawing the set in the traditional plane with *x*/*y* axes correspond to the *real*/*imaginary* parts of the complex number, we may utilize different mappings, for example [polar coordinates](polar_coords.md) or the "inversion mode" (swapping zero and infinity) used in xaos. These may offer yet different angles of view of the set.

Mandelbrot set is similar and related to **[Julia sets](julia_set.md)**; in a way Mandelbrot set is kind of a map of Julia sets, of which there are infinitely many. Each Julia set is, like the Mandelbrot, a set of complex numbers that usually has fractal boundary. Julia sets are defined using the same series as Mandelbrot set, however for given Julia set we take the *p* to be constant and instead set *z[0]* to the visualized coordinate -- so each *p* in the complex plane has its own Julia set. There are some deep mathematical connections between Julia sets and Mandelbrot set. To a Mandelbrot set admirer Julia sets offer infinitely many similar worlds to explore.

The following are some **attributes** of the Mandelbrot set:

- **[Hausdorff dimension](hausdorff_dimension.md)** (of the boundary): 2
- **area**: approximately 1.5052; this is a current best estimate, the area is not easy to calculate (it may be estimated e.g. with [Monte Carlo](monte_carlo.md) methods).
- It is **symmetric** along the *x* axis.
- It's proven the set is **connected**, i.e. it's just a single "island".
- The number [pi](pi.md) is embedded in the shape of the set in a hugely mysterious way which was discovered by mistake by David Bolle in 1991 who tried to measure the width of the gap touching the point [-0.75,0] -- as he increased precision of his iterative algorithm, the number of iterations started to approximate digits of pi.
- ...

**How to explore Mandelbrot set?** There are about billion programs for this, but a quite nice FOSS one is e.g. [Xaos](xaos.md).

As the set is being studied and explored a lot, some even started to make maps of it and give names to various regions. The biggest bulb-part is called the *Main Cardioid*, the smaller disk to the left of it is the *Main Disk*. Between these two parts there is the *Seahorse Valley*. On the right side of *Main Cardioid* there is the *Elephant Valley*. There are terms such as *mu-atom* (also *island*, *mandelbrotie*, *minibrot* or *midget*) -- the smaller distorted self-similar versions of the big set inside the set itself. And so on. Here are some examples of **interesting places** (nice for wallpapers :]) in the Mandelbrot set (views are denoted as [center X, center Y, view radius]):

- View [-0.774680610626904,-0.137416885603787,8e-12] shows a very nice circular pattern.
- View [-0.74989,-0.0376656,1.04358e-05] shows another nice grid pattern.
- View [0.353447,0.0990225,1.12029e-05] shows a cool spiral pattern.
- View [-1.4045,0,0.0006] shows self-similarity, an approximate smaller Mandelbrot set shape inside itself.
- Views [-1.38379,0,0.037555] and [-1.3973347,0,0.008779] show approximate self similarity.
- Point [-1.3932809650418352,0.0215485287711777498] shows a very thin connection.
- Point [0.372138,0.0903982] shows an infinitely zoomable point from which circular arms stem.
- ...

**Generalizations and modifications**: mentioned [Julia sets](julia_set.md) are very similar to the Mandelbrot set. **[Multibrot](multibrot.md)** sets are sets similar to the Mandelbrot which we define by requiring *abs(z[n])* to not surpass some given value *T* under infinite iteration, i.e. Mandelbrot set is one of Multibrot sets, that in which we set *T = 2* (because as mentioned above, reaching 2 always leads to divergence towards infinity); for different values of *T* we'll get similar but different Multibrot fractal sets. We may also modify the iterative equation from quadratic to cubic (replace *z[n]^2* with *z[n]^3*), or a different power (or modify the equation in similar ways) to again get sets similar to the Mandelbrot. Using [quaternions](quaternion.md) instead of complex numbers generalized Mandelbrot from 2D to 4D. [Buddhabrot](buddhabrot.md) is another famous fractal (which looks like Buddha) and is related to Mandelbrot set.

## Code

The following code is a simple [C](c.md) program that renders the Mandelbrot set into terminal (for demonstrative purposes, it isn't efficient or do any [antialiasing](antialiasing.md), also using [float](float.md) for simplicity but keep in mind [fixed point](fixed_point.md) can be easily used as well).

```
#include <stdio.h>

#define ROWS 30
#define COLS 60
#define FROM_X -2.0
#define FROM_Y 1.0
#define STEP (2.5 / ((double) COLS))

unsigned int mandelbrot(double x, double y)
{
  double cx = x, cy = y, tmp;

  for (int i = 0; i < 1000; ++i) // 1000 iterations
  {
    tmp = cx * cx - cy * cy + x;
    cy = 2 * cx * cy + y;
    cx = tmp;

    if (cx * cx + cy * cy > 4) // optimization
      return 0;
  }

  return 1;
}

int main(void)
{
  double cx, cy = FROM_Y;

  for (int y = 0; y < ROWS; ++y)
  {
    cx = FROM_X;

    for (int x = 0; x < COLS; ++x)
    {
      unsigned int point = 
        mandelbrot(cx,cy) + (mandelbrot(cx,cy + STEP) * 2);

      putchar(point == 3 ? ':' : (point == 2 ? '\'' : 
        (point == 1 ? '.' : ' ')));

      cx += STEP;
    }

    putchar('\n');

    cy -= 2 * STEP;
  }

  return 0;
}
```

Note on the optimization above: a naive line checking the divergence of the series would look e.g. like `if (sqrt(cx * cx + cy * cy) > 1000000000)`. However, as said above, it is enough to check if the value exceeds 2, as it's proven that then the series will surely diverge, so we can change it to `if (sqrt(cx * cx + cy * cy) > 2)`. Furthermore we can get rid of the [square root](sqrt.md) by squaring both sides of the inequality, so we get `if (cx * cx + cy * cy > 4)`. Hopefully this is one small example of why [math](math.md) is important for programming.

## See Also

- [fractal](fractal.md)
- [Julia set](julia_set.md)
- [Buddhabrot](buddhabrot.md)