\myheading{Mandelbrot set}

\renewcommand{\CURPATH}{unsorted/mandel}

\leveldown{}

\epigraph{You know, if you magnify the coastline, it still looks like
a coastline, and a lot of other things have this property. Nature has
recursive algorithms that it uses to generate clouds and Swiss cheese
and things like that.}
{Donald Knuth, interview (1993)}

Mandelbrot set is a fractal, which exhibits self-similarity.

When you increase scale, you see that this characteristic pattern repeating infinitely.

\myheading{A word about complex numbers}

A complex number is a number that consists of two parts---real (Re) and imaginary (Im).

The complex plane is a two-dimensional plane where any complex number can be placed: the real part is one coordinate
and the imaginary part is the other.

Some basic rules we have to keep in mind:

\begin{itemize}
\item Addition: $(a+bi) + (c+di) = (a+c) + (b+d)i$

In other words:

$\operatorname{Re}(sum) = \operatorname{Re}(a) + \operatorname{Re}(b)$

$\operatorname{Im}(sum) = \operatorname{Im}(a) + \operatorname{Im}(b)$

\item Multiplication: $(a+bi) (c+di) = (ac-bd) + (bc+ad)i$

In other words:

$\operatorname{Re}(product) = \operatorname{Re}(a) \cdot \operatorname{Re}(c) - \operatorname{Re}(b) \cdot \operatorname{Re}(d)$

$\operatorname{Im}(product) = \operatorname{Im}(b) \cdot \operatorname{Im}(c) + \operatorname{Im}(a) \cdot \operatorname{Im}(d)$

\item Square: $(a+bi)^2 = (a+bi) (a+bi) = (a^2-b^2) + (2ab)i$

In other words:

$\operatorname{Re}(square) = \operatorname{Re}(a)^2-\operatorname{Im}(a)^2$

$\operatorname{Im}(square) = 2 \cdot \operatorname{Re}(a) \cdot \operatorname{Im}(a)$

\end{itemize}

\myheading{How to draw the Mandelbrot set}

The Mandelbrot set is a set of points for which the $z_{n+1} = {z_n}^2 + c$ recursive sequence
(where $z$ and $c$ are complex numbers and $c$ 
is the starting value)
does not approach infinity.\\
\\
In plain English language: 

\begin{itemize}
\item Enumerate all points on screen. 
\item Check if the specific point 
is in the Mandelbrot set.
\item Here is how to check it:

  \begin{itemize}
  \item Represent the point as a complex number.
  \item Calculate the square of it.
  \item Add the starting value of the point to it.
  \item Does it go off limits? If yes, break.
  \item Move the point to the 
new place at the coordinates we just calculated.
  \item Repeat all this for some reasonable 
number of iterations.
  \end{itemize}

\item The point is still in limits?
Then draw the point.

\item The point has eventually gone off limits?

  \begin{itemize}
    \item (For a black-white image) do not draw anything.
    \item (For a colored image) transform the number of iterations to some color. 
      So the color shows the speed with which point has gone off limits.
  \end{itemize}

\end{itemize}

Here is Pythonesque algorithm for both complex and integer number representations:

\lstinputlisting[caption=For complex numbers]{\CURPATH/algo_cplx.lst}

The integer version is where the operations on complex numbers are replaced with integer operations according to the rules
which were explained above.

\lstinputlisting[caption=For integer numbers]{\CURPATH/algo_int.lst}

Here is also a C\# source 
which is present in the Wikipedia article
\footnote{\href{https://en.wikipedia.org/wiki/Mandelbrot_set}{wikipedia}},
but we'll modify it so it will print the iteration numbers instead of some symbol
\footnote{Here is also the executable file: 
\MakeURL{\RepoPath/\CURPATH/dump\_iterations.exe}}:

\lstinputlisting[style=customc]{\CURPATH/dump_iterations.cs}

Here is the resulting file, 
which is too wide to be included here: \\
\MakeURL{\RepoPath/\CURPATH/result.txt}.

The maximal number of iterations is 40, so when you see 40 in this dump, it means that this point has been wandering
for 40 iterations but never got off limits. 

A number $n$ less than 40 means that point remained inside the bounds only for $n$ iterations, 
then it went outside them.

\clearpage
There is a cool demo available at 
\url{http://demonstrations.wolfram.com/MandelbrotSetDoodle/}, which shows
visually how the point moves on the plane at each iteration for some specific point. 
Here are two screenshots.

First, we've clicked inside the yellow area and saw that the trajectory (green line)
eventually swirls at some point inside:

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{\CURPATH/demo1.png}
\caption{Click inside yellow area}
\end{figure}

This implies that the point we've clicked belongs to the Mandelbrot set.

\clearpage

Then we've clicked outside the yellow area and saw a much more chaotic point movement, 
which quickly went off bounds:

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{\CURPATH/demo2.png}
\caption{Click outside yellow area}
\end{figure}

This means the point doesn't belong to Mandelbrot set.

Another good demo is available here: \\
\url{http://demonstrations.wolfram.com/IteratesForTheMandelbrotSet/}.

\levelup{}