# Fractals/Iterations in the complex plane/Mandelbrot set

This book shows how to code different algorithms for drawing parameter plane ^{[1]} ( Mandelbrot set ^{[2]} ) for complex quadratic polynomial ^{[3]}.

One can find different types of points / sets on parameter plane ^{[4]}

## Contents

**Interior of Mandelbrot set** - hyperbolic components[edit]

## The Lyapunov Exponent[edit]

Math equation :^{[5]}

where :

means first derivative of f with respect to z

See also :

- image and description by janthor
^{[6]} - image by Anders Sandberg
^{[7]}

## Interior distance estimation[edit]

DEM/M - description of the method

## absolute value of the orbit[edit]

```
# Hypercomputing the Mandelbrot Set? by Petrus H. Potgieter February 1, 2008
n=1000; # For an nxn grid
m=50; # Number of iterations
c=meshgrid(linspace(-2,2,n))\ # Set up grid
+i*meshgrid(linspace(2,-2,n))’;
x=zeros(n,n); # Initial value on grid
for i=1:m
x=x.^2+c; # Iterate the mapping
endfor
imagesc(min(abs(x),2.1)) # Plot monochrome, absolute
# value of 2.1 is escape
```

### internal level sets[edit]

Color of point :

- is proportional to the value of z is at final iteration.
- shows internal level sets of periodic attractors.

### bof60[edit]

Image of bof60 in on page 60 in the book "the Beauty Of Fractals".Description of the method described on page 63 of bof. It is used only for interior points of the Mandelbrot set.

Color of point is proportional to :

- the smallest distance of its orbit from origin
^{[8]}^{[9]} - the smallest value z gets during iteration
^{[10]} - illuminating the closest approach the iterates of the origin (critical point) make to the origin inside the set
- "Each pixel of each particular video frame represents a particular complex number c = a + ib. For each sequential frame n, the magnitude of z(c,n) := z(c, n-1)^2 + c is displayed as a grayscale intensity value at each of these points c: larger magnitude points are whiter, smaller magnitudes are darker. As n rises from 1 to 256, points outside the Mandelbrot Set quickly saturate to pure white, while points within the Mandelbrot Set oscillate through the darker intensities." Brian Gawalt
^{[11]}

Level sets of distance are sets of points with the same distance^{[12]}

```
if (Iteration==IterationMax)
/* interior of Mandelbrot set = color is proportional to modulus of last iteration */
else { /* exterior of Mandelbrot set = black */
color[0]=0;
color[1]=0;
color[2]=0;
}
```

- fragment of code : fractint.cfrm from Gnofract4d
^{[13]}

bof60 { init: float mag_of_closest_point = 1e100 loop: float zmag = |z| if zmag < mag_of_closest_point mag_of_closest_point = zmag endif final: #index = sqrt(mag_of_closest_point) * 75.0/256.0 }

### bof61[edit]

Names and description

- period domain
- atom domain
- BOF61
- orbit trap at (0,0)

## Period of hyperbolic components[edit]

Period of hyperbolic component of Mandelbrot set is a period of limit set of critical orbit.

Algorithms for computing period:

- direct period detection from iterations of critical point z = 0.0 on dynamical plane
- "quick and dirty" algorithm : check if then colour c-point with colour n. Here n is a period of attracting orbit and eps is a radius of circle around attracting point = precision of numerical computations
- "methods based on interval arithmetic when implemented properly are capable of finding all period-n cycles for considerable large n." (ZBIGNIEW GALIAS )
^{[14]} - Floyd's cycle-finding algorithm
^{[15]} - the spider algorithm
- atom domain, BOF61

## internal coordinate and multiplier map[edit]

- interior coordinate
^{[16]}^{[17]}

The algorithm by Claude Heiland-Allen:

- check c
- When c is outside the Mandelbrot set
- give up now
- or use external coordinate

- when c is not outside (inside or on the boundary) : For each period p, starting from 1 and increasing:
- Find periodic point z0 such that fp(z0,c)=z0 using Newton's method in one complex variable
- Find b by evaluating first derivative with respect to z of fp at z0
- If |b|≤1 then return b, otherwise continue with the next p

- When c is outside the Mandelbrot set

### computing[edit]

For periods:

- 1 to 3 explicit equations can be used
- >3 it must be find using numerical methods

#### period 1[edit]

Start with boundary equation :

c+(w/2)^2-w/2=0;

and solve it for w

(%i1) eq1:c+(w/2)^2-w/2=0; 2 w w (%o1) -- - - + c = 0 4 2 (%i2) solve(eq1,w); (%o2) [w = 1 - sqrt(1 - 4 c), w = sqrt(1 - 4 c) + 1] (%i3) s:solve(eq1,w); (%o3) [w = 1 - sqrt(1 - 4 c), w = sqrt(1 - 4 c) + 1] (%i4) s:map(rhs,s); (%o4) [1 - sqrt(1 - 4 c), sqrt(1 - 4 c) + 1]

so

w = w(c) = 1.0 - csqrt(1.0-4.0*c)

#### period 2[edit]

w = 4.0*c + 4;

#### numerical aproximation[edit]

```
complex double AproximateMultiplierMap(complex double c, int period, double eps2, double er2){
complex double z; // variable z
complex double zp ; // periodic point
complex double zcr = 0.0; // critical point
complex double d = 1;
int p;
// first find periodic point
zp = GivePeriodic( c, zcr, period, eps2, er2); // Find periodic point z0 such that Fp(z0,c)=z0 using Newton's method in one complex variable
// Find w by evaluating first derivative with respect to z of Fp at z0
if ( cabs2(zp)<er2) {
z = zp;
for (p=0; p < period; p++){
d = 2*z*d; /* first derivative with respect to z */
z = z*z +c ; /* complex quadratic polynomial */
}}
else d= 10000; //
return d;
}
```

### Internal angle[edit]

Method by Renato Fonseca : ^{[18]} "a point c in the set is given a hue equal to argument

(scaled appropriatly so that we end up with a number in the range 0 - 255). The number z_nmax is the last one calculated in the z's sequence. "

#### Fractint[edit]

Fractint : Color Parameters : INSIDE=ATAN

colors by determining the angle in degrees the last iterated value has with respect to the real axis, and using the absolute value. This feature should be used with periodicity=0^{[19]}

### Internal rays[edit]

When varies and is constant then goes along internal ray. It is used as a **path** inside Mandelbrot set

```
/* find c in component of Mandelbrot set
uses complex type so #include <complex.h> and -lm
uses code by Wolf Jung from program Mandel
see function mndlbrot::bifurcate from mandelbrot.cpp
http://www.mndynamics.com/indexp.html
*/
double complex GiveC(double InternalAngleInTurns, double InternalRadius, unsigned int period)
{
//0 <= InternalRay<= 1
//0 <= InternalAngleInTurns <=1
double t = InternalAngleInTurns *2*M_PI; // from turns to radians
double R2 = InternalRadius * InternalRadius;
double Cx, Cy; /* C = Cx+Cy*i */
switch ( period ) {
case 1: // main cardioid
Cx = (cos(t)*InternalRadius)/2-(cos(2*t)*R2)/4;
Cy = (sin(t)*InternalRadius)/2-(sin(2*t)*R2)/4;
break;
case 2: // only one component
Cx = InternalRadius * 0.25*cos(t) - 1.0;
Cy = InternalRadius * 0.25*sin(t);
break;
// for each period there are 2^(period-1) roots.
default: // safe values
Cx = 0.0;
Cy = 0.0;
break; }
return Cx+ Cy*I;
}
// draws points to memmory array data
int DrawInternalRay(double InternalAngleInTurns , unsigned int period, int iMax, unsigned char data[])
{
complex double c;
double InternalRadius;
double RadiusStep; // between radius of points
int i; // number of point to draw
RadiusStep = 1.0/iMax;
for(i=0;i<=iMax;++i){
InternalRadius = i * RadiusStep;
c = GiveC(InternalAngleInTurns, InternalRadius, period);
DrawPoint(c,data);
}
return 0;
}
```

Example : internal ray of angle =1/6 of main cardioid.

Internal angle :

radius of ray :

Point of internal radius of unit circle :

Map point to parameter plane :

For this is equation for main cardioid.

### Internal curve[edit]

When is constant varies and varies then goes along internal curve.

```
/* find c in component of Mandelbrot set
uses complex type so #include <complex.h> and -lm
uses code by Wolf Jung from program Mandel
see function mndlbrot::bifurcate from mandelbrot.cpp
http://www.mndynamics.com/indexp.html
*/
double complex GiveC(double InternalAngleInTurns, double InternalRadius, unsigned int period)
{
//0 <= InternalRay<= 1
//0 <= InternalAngleInTurns <=1
double t = InternalAngleInTurns *2*M_PI; // from turns to radians
double R2 = InternalRadius * InternalRadius;
double Cx, Cy; /* C = Cx+Cy*i */
switch ( period ) {
case 1: // main cardioid
Cx = (cos(t)*InternalRadius)/2-(cos(2*t)*R2)/4;
Cy = (sin(t)*InternalRadius)/2-(sin(2*t)*R2)/4;
break;
case 2: // only one component
Cx = InternalRadius * 0.25*cos(t) - 1.0;
Cy = InternalRadius * 0.25*sin(t);
break;
// for each period there are 2^(period-1) roots.
default: // safe values
Cx = 0.0;
Cy = 0.0;
break; }
return Cx+ Cy*I;
}
// draws points to memmory array data
int DrawInternalCurve(double InternalRadius , unsigned int period, int iMax, unsigned char data[])
{
complex double c;
double InternalAngle; // in turns = from 0.0 to 1.0
double AngleStep;
int i;
// int iMax =100;
AngleStep = 1.0/iMax;
for(i=0;i<=iMax;++i){
InternalAngle = i * AngleStep;
c = GiveC(InternalAngle, InternalRadius, period);
DrawPoint(c,data);
}
return 0;
}
```

### Centers of components[edit]

**Speed improvements - optimisation**[edit]

- general optimization
- Speed improvements by Robert Munafo
- fractalforums : help-optimising-mandelbrot
- The Computer Language Benchmarks Game
- Koebe 1/4 theorem by claudiusmaximus

## Symmetry[edit]

The Mandelbrot set is symmetric with respect to the x-axis in the plane :

colour(x,y) = colour(x,-y)

its intersection with the x-axis ( real slice of Mandelbrot set ) is an interval :

<-2 ; 1/4>

It can be used to speed up computations ( up to 2-times )^{[20]}

## Bailout test[edit]

Instead of checking :

```
```

compute ER2 once and check :

```
```

It gives the same result and is faster.

## Period detection[edit]

"When rendering a Mandelbrot or Julia set, the most time-consuming parts of the image are the “black areas”. In these areas, the iterations never escape to infinity, so every pixel must be iterated to the maximum limit. Therefore, much time can be saved by using an algorithm to detect these areas in advance, so that they can be immediately coloured black, rather than rendering them in the normal way, pixel by pixel. FractalNet uses a recursive algorithm to split the image up into blocks, and tests each block to see whether it lies inside a “black area”. In this way, large areas of the image can be quickly coloured black, often saving a lot of rendering time. ... (some) blocks were detected as “black areas” and coloured black immediately, without having to be rendered. (Other) blocks were rendered in the normal way, pixel by pixel." Michael Hogg ^{[21]}

```
// cpp code by Geek3
// http://commons.wikimedia.org/wiki/File:Mandelbrot_set_rainbow_colors.png
bool outcircle(double center_x, double center_y, double r, double x, double y)
{ // checks if (x,y) is outside the circle around (center_x,center_y) with radius r
x -= center_x;
y -= center_y;
if (x * x + y * y > r * r)
return(true);
return(false);
// skip values we know they are inside
if ((outcircle(-0.11, 0.0, 0.63, x0, y0) || x0 > 0.1)
&& outcircle(-1.0, 0.0, 0.25, x0, y0)
&& outcircle(-0.125, 0.744, 0.092, x0, y0)
&& outcircle(-1.308, 0.0, 0.058, x0, y0)
&& outcircle(0.0, 0.25, 0.35, x0, y0))
{
// code for iteration
}
```

### Cardioid and period-2 checking[edit]

One way to improve calculations is to find out beforehand whether the given point lies within the cardioid or in the period-2 bulb. Before passing the complex value through the escape time algorithm, first check if:

to determine if the point lies within the period-2 bulb and

to determine if the point lies inside the main cardioid.

### Periodicity checking[edit]

Most points inside the Mandelbrot set oscillate within a fixed orbit. There could be anything from ten to tens of thousands of points in between, but if an orbit ever reaches a point where it has been before then it will continually follow this path, will never tend towards infinity and hence is in the Mandelbrot set. This Mandelbrot processor includes periodicity checking (and p-2 bulb/cardioid checking) for a great speed up during deep zoom animations with a high maximum iteration value.

## Perturbation theory[edit]

"The thing we call perturbation consist of 2 things: Calculate one pixel with high precision and use it as a reference for all other pixels.

This method will fail though, however thanks to Pauldelbrot we have a trustable method of detecting the pixels where the reference fails to compute the pixel with hardware precision. These pixels can be rendered with a reference closer to these pixels, so a typical perturbation render use several references. This method gives a speedup at about 10 times on depths of 10^100 Use a truncated Taylor series to approximate a starting value for a specific iteration, which make you able to skip all previous iterations. This method gives a speedup of typically Another 10 times on depths of 10^100, and together the speed up is typically 100 times. This, which we call Series Approximation, is where we have issues since we do not have any solid theoretically way of finding when too many iterations are skipped - for all pixels in the view. The more terms you include in the Taylor series, the more iterations you are able to skip. So if you stay below say 50 terms, it is not likely that you ever encounter any issues. Because some views can be correctly rendered 1000 or 100,000 times faster than full precision for each pixel with many terms - can you imagine a month turned into seconds! shocked K.I.Martin originally used only 3 terms " - Kalles Fraktaler ^{[22]}

### Description[edit]

Very highly magnified images require more than the standard 64-128 or so bits of precision most hardware floating-point units provide, requiring renderers use slow "bignum" or "arbitrary precision"^{[23]} math libraries to calculate. However, this can be sped up by the exploitation of perturbation theory^{[24]}. Given

as the iteration, and a small epsilon, it is the case that

or

so if one defines

one can calculate a single point (e.g. the center of an image) using normal, high-precision arithmetic (*z*), giving a *reference orbit*, and then compute many points around it in terms of various initial offsets epsilon-zero plus the above iteration for epsilon. For most iterations, epsilon does not need more than 16 significant figures, and consequently hardware floating-point may be used to get a mostly accurate image.^{[25]} There will often be some areas where the orbits of points diverge enough from the reference orbit that extra precision is needed on those points, or else additional local high-precision-calculated reference orbits are needed. This rendering method, and particularly the automated detection of the need for additional reference orbits and automated optimal selection of same, is an area of ongoing, active research. Renderers implementing the technique are publicly available and offer speedups for highly magnified images in the multiple orders of magnitude range.^{[26]} ^{[27]} ^{[28]}

#### Newton-Raphson zooming[edit]

One can "use newton's method to find and progressively refine the precision of the location of the minibrot at the center of a pattern. This allows them to arbitrarily select a magnification between the location they started at and the final minibrot they calculate to be at the center of that location."^{[29]}^{[30]}

#### Glitches[edit]

Glitches^{[31]}

### history[edit]

- 2 independent descriptions :
- Fast Mandelbrot set with infinite resolution by Sergey Khashin (July 9, 2011)
^{[32]} - perturbation method by K.I. Martin (2013-05-18)
^{[33]}( only use 3 Series Approximation terms )

- Fast Mandelbrot set with infinite resolution by Sergey Khashin (July 9, 2011)
- Pauldelbrot's glitch detection method
^{[34]} - extending Martin's description to handle interior distance estimation too by Claude Heiland-Allen
^{[35]}

### Programs[edit]

- SuperFractalThing in Java by K.I. Martin
^{[36]} - mightymandel by Claude Heiland-Allen
^{[37]} - mandelbrot-perturbator by Claude Heiland-Allen : http://code.mathr.co.uk/mandelbrot-perturbator/
- Kalles Fraktaler for windows

# More tutorials and code[edit]

- in Basic see Mandelbrot Dazibao
- in Java see Evgeny Demidov
- in C see Linas Vepstas
- in C++ see Wolf Jung page,
- in Factor program by Slava Pestov
- in Gnuplot see Tutorial by T.Kawano
- in Lisp (Maxima) see :
- in Octave see wikibooks or another verion by Christopher Wellons

- How to Plot the Mandelbrot Set By Hand
- comparison of various languages :
- Computer Language Benchmarks Game : Compare the performance of ≈30 programming languages using ≈12 flawed benchmarks for 4 different combinations of OS/machine.
- rosettacode
- Fractal Benchmark in Ruby, Io, PHP, Python, Lua, Java, Perl, Applescript, TCL, ELisp, Javascript, OCaml, Ghostscript, and C by Erik Wrenholt
- in PDL, IDL, MATLAB, Octave, C and FORTRAN77 by Xavier Calbet

- ASCI graphic :
^{[38]}- ASCII Graphics at Mu-Ency by Robert P. Munafo
- using scripting languages by Warp
- Fractal Benchmark by Theo Wollenleben
- using Lisp on Bill Clementson's blog

- 3D

# References[edit]

- ↑ parameter plane in wikipedia
- ↑ Mandelbrot set in wikipedia
- ↑ complex quadratic polynomial in wikipedia
- ↑ reenigne blog : mandelbrot-set-taxonomy
- ↑ The logistic equation by Didier Gonze October 4, 2013
- ↑ Ljapunov Exponent and mandelbrot set by janthor
- ↑ Image by Anders Sandberg
- ↑ Fractint : Misc. Options and algorithms
- ↑ Java™ Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald Mak
- ↑ Firefly Application Help by Terry W. Gintz
- ↑ Mandelbrot Oscillations by Brian Gawalt
- ↑ Fractint doc by Noel Giffin
- ↑ gnofract4d
- ↑ Rigorous Investigations Of Periodic Orbits In An Electronic Circuit By Means Of Interval Methods by Zbigniew Galias
- ↑ Mandelbrot set drawing by Milan
- ↑ interior_coordinates_in_the_mandelbrot_set by Claude Heiland-Allen
- ↑ practical interior_distance rendering by Claude Heiland-Allen
- ↑ The Mandelbrot set by Renato Fonseca
- ↑ fractint color params
- ↑ How to use symetry of set
- ↑ FractalNet by Michael Hogg
- ↑ Fractal Forums > Fractal Software > Help & Support > (C++) How to deep zoom in mandelbrot set?
- ↑ arbitrary precision at wikipedia
- ↑ perturbation theory in wikipedia
- ↑ "Superfractalthing - Arbitrary Precision Mandelbrot Set Rendering in Java by K.I. Martin 2013-05-18". http://www.fractalforums.com/announcements-and-news/superfractalthing-arbitrary-precision-mandelbrot-set-rendering-in-java/.
- ↑ "Kalles Fraktaler 2". http://www.chillheimer.de/kallesfraktaler/.
- ↑ Fast Mandelbrot set with infinite resolution, ver. 2 by Sergey Khashin, July 9, 2011
- ↑ Perturbation techniques applied to the Mandelbrot set by Claude Heiland-Allen October 21, 2013
- ↑ newton-raphson-zooming by quaz0r
- ↑ Newton-Raphson zooming and Evolution zoom method by Dinkydau
- ↑ pertubation-theory-glitches-improvement - fractal forum
- ↑ Fast Mandelbrot set with infinite resolution, ver. 2
- ↑ fractalforums : superfractalthing-arbitrary-precision-mandelbrot-set-rendering-in-java
- ↑ fractalforums - pertubation-theory-glitches-improvement
- ↑ Perturbation glitches by Claude Heiland-Allen
- ↑ superfractalthing By K.I. Martin
- ↑ mightymandel by Claude Heiland-Allen
- ↑ ASCII graphic