Friday, November 14, 2014

A Guide to the Mandelbrot Set

For those of you who don't know about the Mandelbrot set, it's this thing:





























It's a fractal, which means it is infinitely detailed. So no matter how far in you zoom, it will still look just as complex as before. This video's a good demonstration. The higher the quality, the better.

It goes on for quite a while, don't feel like you have to watch all of it. You could zoom in literally forever. This video stopped at 10^227x magnification.

By the way, that's zoomed in to 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times bigger than at first.

But where does this weird-ass shape even come from? It's actually a little complicated (who would have thought). If you don't have the stomach for math, here's a basic understanding of how it works.

This mathematical, infinitely complex shape is called the Mandelbrot Set, or the M-Set for short. Imagine we want to draw the M-Set on a computer screen made up of a small number of pixels. We would assign each pixel on the screen a unique number based on its location, so every pixel has a different number. For each pixel, if the number satisfies a very certain quality, we color it black. If it doesn't, we color it something different. The M-Set is the black shape in the middle. All of the vibrant, colorful patterns are created through mathematical patterns.

Here's an example of a crudely rendered M-Set. Let's start with small numbers, how about 100 pixels. So on a 10x10 computer screen, we would one by one test each pixel and see if it should be black (part of the M-Set) or some other color (not part of the weird shape). If other, then we test further to get a more precise color. After the last pixel is tested and filled in with the appropriate color, we end up with a crude image of our beloved Mandelbrot set, something like the one here. 


(this is actually 11x11, odd numbers work better)





Let's say we do the same thing but with more pixels. A lot more pixels. We get a more detailed picture. The one below was calculated at 801x801. You should notice a very, very slight resemblance.

































Even though this looks much better than the 11x11, understand it still isn't perfect. The only way to get a truly perfect image is to use an infinite number of pixels, which is impossible, so we don't even fully understand this mathematical behemoth.

If you aren't interested in an in depth guide as to how I created these images and the math behind it, this is where you should say "neat" and stop reading. Things get a little bit scary beyond this line.
-------------------------------------------------------------------------------------------------------------

First you'll need to know what an imaginary number is, and some of its behaviors.

The function √4 is read as "the positive square root of four". This means the number that when multiplied by itself is equal to four. This function of multiplying a number by itself is called squaring. For example, 2 squared is equal to 4.

Important side note, -2 squared is also equal to 4, which is why we specify √ to mean the positive square root.

However, a problem arises when taking the square root of a negative number. Even when you multiply a negative number by itself, you get a positive number. So really, there is no real square root of a negative number.

This is why the square root of negative numbers are called imaginary numbers. You could think of imaginary numbers as place holders, because when you square an imaginary number you get a real number again.

Imaginary numbers are written as real numbers with an "i" after it. i, 2i, and -3.4i are all examples of imaginary numbers. They can be added, subtracted, multiplied, and divided just like conventional numbers.

i is defined as square root of -1. Therefore, i squared = -1. So for example -3i multiplied by 4i would be 12. Here's a step by step demonstration.

      -3i x 4i
 =  (-3 x i) x (4 x i)
 =  -3 x 4 x i x i
 = (-3 x 4) x (i ²)            ( " ² " is short hand notation for "squared" )
 =  (-12)  x   (-1)
 =  12

 If you are following so far, you are ready for the next step.

-------------------------------------------------------------------------------------------------------------

complex number is what you get when you subtract or add an imaginary number with a real number, and has two parts: the real component and the imaginary component. 1+i is a complex number. 3-2i is another example. These can be added, subtracted, multiplied and divided together.

For creating the Mandelbrot set, you will need to be able to multiply two complex numbers together. This can be done using the FOIL method. This stands for First, Outer, Inner, Last. This method is done by taking every combination of one component from each complex number and adding them up. Here's an example to help.

Let's try to find (4+2i) x (-7-i)
One combination is obtained by taking the first components of each: 4 and -7 (remember your signs!)
Another is comprised by the outer: 4 and -i
The inner: 2i and -7
The last: 2i and -i

Now find the product of each pair and add 'em up!

4 x -7 = -28
4 x -i = -4i
2i x -7 = -14i                          -28 - 4i - 14i + 2 = -26 - 18i
2i x -i = 2                            

So (4+2i) x (-7-i) = (-26 - 18i)

-------------------------------------------------------------------------------------------------------------

One last little thing to learn before we move on.

The absolute value of a complex number can be calculated by taking the square root of the sum of the squares of the coefficients of its real and imaginary components.

Damn. That is awfully derivative. Let's look at it backwards.

Let's take a complex number and walk it through for simplicity. 3+4i seems pretty simple.

Coefficient means the number something is multiplied by. The coefficient of the real component 3 is just 3, because in this case there is no "something", just the number. The coefficient of the imaginary component 4i would be 4, because the "something" this time around is i.
Our coefficients: 3 and 4

Now we need the squares of the coefficients. 3² is 9, 4² is 16. Our squares: 9 and 16

Next is the sum of the squares:  9 + 16 = 25

Last is the square root: √25 = 5
The absolute value of the complex number 3+4i is 5

It's pretty similar to the Pythagorean theorem, in that if the coefficients are the legs of a triangle, the absolute value would be the hypotenuse. This may make this process easier to remember.

-------------------------------------------------------------------------------------------------------------

If you are up to speed on everything discussed above, bravo. You can now assign numbers to your pixels. Each pixel will be assigned a complex number based on its location. The real component will be determined by its horizontal location, and the imaginary component by its vertical location. For example, The center pixel will be (0,0) and thusly assigned 0+0i.

It might help to think of your grid of pixels as a complex plane where the x-axis is real numbers and the y-axis is imaginary. Each point will have an x-value and a y-value, and the complex number is made up of the coordinates of the point.

As for units, you should make each pixel change by enough so that the farthest points from left to right should have real components -2 to 2. Same goes for your imaginary axis, the highest points should have imaginary component 2i and the lowest should be -2i. Everything outside of this range will be the same color and pretty boring.

-------------------------------------------------------------------------------------------------------------

Finally it is time to discuss what the magical test is for whether or not a pixel should be colored black.
The magic equation is this:

(Zn)² + Z= Z(n+1)

In this equation there is something you may notice to note. The use of the variable n in the subscript makes this a recursive formula, meaning for each complex number pixel there is a series of complex numbers to go with it. If the series diverges, then the pixel is said to escape the Mandelbrot set. But what does that even mean?

When your typical series of ordinary numbers diverges, it shoots off into infinity, either in the positive or negative direction. These are all series that diverge:

1, 2, 3, 4, 5, 6, 7, 8, 9....         -5, 10, -15, 20, -25, 30, -35...

2, 4, 8, 16, 32, 64, 128...        1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Here are a few series that do not diverge:

1/2, 1/4, 1/8, 1/16, ...

1, -1, 1, -1, 1...

How we determine this for a series of complex numbers is by taking the absolute value of each term in the series. Benoit Mandelbrot proved decades ago that if the absolute value Z0 ever becomes greater than or equal to 2, the series will diverge. Don't ask me. That is beyond my understanding, and you don't really need to know why to do the rest anyway.

To the points that do escape the set, a color is selected based on how many terms into the series it takes before the absolute value becomes at least 2. If after only 1 term a pixel has an absolute value of at least 2, we color the original pixel a certain color. For all of the pixels that take 2 steps to do this, we pick a different color. Usually a gradient scale is easiest on the eyes.

Now looking back at our magic equation, we plug a pixel value into Z0 and can make a series with it. The first term will be our complex number, Z0, and the next can be calculated by setting n equal to 0. We get (Z0)² + Z0 = Z1. With Z1, we can just plug in n=1 and get Z2 and so on.

After calculating, plugging and chugging, calculating, slaving away, we will eventually end up with a nice, pretty picture of the Mandelbrot Set.