Friday, 29 December 2017

Escape Condition for Julia and Mandelbrot Fractals

This post is reproduced from the blog for my next book, Make Your Own Algorithmic Art.

This post isn't a tutorial on creating the Julia or Mandelbrot fractals - you can learn about that here. Here we'll focussed on a specific bit of mathematics about the "escape condition" that many guides state but fail to explain.

Basic Idea

The basic idea behind both Julia and Mandelbrot fractals is to take a starting complex number $z_0$, apply a simple function $z^2 + c$, and feed the output $z_1$ back into this function as input. Doing this repeatedly we get a sequence of output complex numbers, $z_1$, $z_2$, $z_3$ ...

$$z_{n+1} = z_{n}^2 + c$$

These output values can behave in one of three ways:
• They can get larger and larger, towards infinity. This is called escaping.
• They can get smaller and smaller, towards zero.
• They can orbit around, but without getting ever larger. In some cases they can approach a finite constant.

The fractal patterns are coloured to show which points escape, and which don't. Those that escape are outside the fractal, and those that don't are inside.

The difference between Julia and Mandelbrot fractals is only how we choose $z_0$ and $c$.

Computational Problem

The behaviour of complex numbers under $z^2 + c$ is chaotic. That is:
• The output sequence is very often irregular, and predicting future values is very difficult without actually working out the sequence. They seem random, even if they're not.
• The sequence is very sensitive to starting conditions. That is, even a tiny change in the starting conditions can drastically change how the sequence behaves.

We can't derive a mathematical formula which tells us which points are inside the fractal, and which are outside (they escape). And this chaotic behaviour suggests we can't truly know even if we run the feedback iterations many many times, because the sequence can suddenly escape after a long period of orbiting around.

Practical Compromise

So we have to compromise - we agree to generate a fixed number of output values, so we can render an approximate pattern. Perhaps a sequence of 50 output values is sufficient? Maybe 100? Maybe even 1000?

By experimenting, it becomes clear that 50 or 100 iterations is fine, except when we are zooming into a very small area of the fractals, where we need more iterations to be able to separate out the inside and outside regions. If we don't do this, the details of the fractal don't emerge.

Computational Shortcut

For many starting points in a fractal pattern, the output values will get larger and larger very quickly. We want to stop calculating the sequence for two reasons:
• If the numbers get too large, this can cause our code to crash with an error, or worse, continue with incorrect calculations. The root cause of this is that the largest size of number we can store and calculate with is fixed.
• We don't want to waste time and computational effort continuing to calculate the sequence which is only every going to get larger and larger. This shortcut can be important because the calculations for detailed fractals can take a long time.

So many guides will state that we can stop calculating the sequence when the magnitude $|z_n|$ gets larger than 2.

That works well, and makes intuitive sense. If $z_n$ has got so large that it is more than 2 away from the origin, then it will forever get larger and larger. But the statement is rarely explained.

Next is a simple proof - and also a demonstration that the popular escape condition $|z_n| > 2$ is incomplete.

Simple Proof

First let's remind ourselves of the triangle inequality, which basically says that a direct path is always shorter than an indirect path between two points.

$$| a + b | \leq |a| + |b|$$

Let's contrive to artificially expand out $|z^2|$,

$$|z^2| = |z^2 +c -c|$$

If we use that triangle inequality, with $a = z^2 +c$ and $b = -c$, we have

$$|z^2 +c -c| \leq |z^2 +c| + |-c|$$

but because $|-c|$ is just $|c|$ we have

$$|z^2 +c -c| \leq |z^2 +c| + |c|$$

Now, remember the next value in a sequence is $z^2 + c$ because that's the function we keep applying. Let's bring that to the left of that last inequality.

$$|z^2 +c| \geq |z^2| - |c|$$

Also, $|z^2|$ is the same as $|z|^2$ so we have

$$|z^2 +c| \geq |z|^2 - |c|$$

Now is the interesting part. If we say that $|z|$ is bigger than $|c|$, that would mean

$$|z|^2 - |c| \gt |z|^2 - |z|$$

That means we can also say,

$$|z^2 +c| \gt |z|^2 - |z|$$

Which can be factorised as

$$|z^2 +c| \gt |z|(|z| -1)$$

Let's rewrite that previous expression as a ratio of the sizes of the current $z_n$ and the next $z_{n+1} = z_n^2 + c$,

$$\frac {|z_{n+1}|} {|z_n|} \gt (|z| -1)$$

Now another interesting part. If we say $|z|$ is greater than 2, that means $|z| -1 \gt 1$. So we finally have

$$\frac {|z_{n+1}|} {|z_n|} \gt 1$$

Which is saying that $|z_{n+1}|$ is always greater than $|z_n|$ as long as:

• $|z| \gt |c|$, and
• $|z| \gt 2$

So we've shown that two conditions need to be true to prove that the sequences escapes, not just the traditional one. However in practice, the traditional $|z| \gt 2$ seems to work well enough.

Reference
One text that does try to cover this is Chaos and Fractals: New Frontiers of Science.

Tuesday, 19 July 2016

Python 3 Code on GitHub

The code for the book Make Your Own Mandelbrot is now on github:

And whilst I was doing this, I updated the code to Python 3.

This required only minor changes: the xrange() becomes the simpler range() function.

(sadly the 3d code requires the mayavi libraries which are not yet ported to Python 3)

Tuesday, 19 April 2016

Republished for Better Formatting

I've republished the kindle and print book.

The main reason is that a few people with older kindle devices didn't have great experiences with the formatting. For some images didn't show properly, for others, the margins were wonky, etc

This is sad because it shouldn't be that hard to get right in 2016. The core problem is that ebook file formats are not open, stable and implemented in an interoperable way. It's like the web 20 years ago - with big companies not implementing web standards properly, and deliberately trying to pervert them to their own ends. Thankfully after 20 years - that's all settled down and usable.

I took the decision to publish the ebooks using Amazon's new Kindle Textbook format. That promises to have much greater certainty over layout, even for complex content, ... like a PDF. This will be great for people who want to see a page more or less as it was intended., and certainly not mashed up.

The following are screenshots from my Android phone's Kindle app - and it looks fantastic!

There is a down side - those with older Kindles that can't support this new Textbook format, won't be able to buy the book. So happier readers, but fewer of them. I didn't take that decision lightly but not having unhappy readers was a priority for me.

Tuesday, 3 March 2015

London Python Group

I was lucky enough to present a flash talk on Make Your Own Mandelbrot at the London Python Group.

One of the great things about such grassroots groups is the openness, honestly and generousness - unlike corporate events. I picked up some pointers on things I didn't know:

• The IPython Cookbook has some content on interactive UI elements (widgets) for IPython Notebooks. Something I always wanted to know how to do.
• An example of GPU accelerated computation in IPython notebooks for generating Mandelbrot fractals.

Sunday, 8 February 2015

I'm now focussing on my next ebook Make Your Own Neural Network.

The central idea is the same, to make sure that anyone with interest and nothing more than school-level maths can understand how neural networks work, and appreciate the pretty cool concepts on the way! Again we'll use Python and assume no previous knowledge of programming.By the end of the guide, you'll have built a simple neural network that recognises human handritten numbers.

You can follow progress and discussions at: http://makeyourownneuralnetwork.blogspot.co.uk/ and @myoneuralnet

Friday, 24 October 2014

LinuxVoice Magazine

I'm really pleased that LinuxVoice Magazine has published the first of my 2-part series on Python and the Mandelbrot fractals.

I hope the series will inspire those completely new to programming to try it - the tutorials require no previous experience at all.

And I also hope the mathematics - which is no more difficult than school maths - will inspire young and old by showing that it can be surprising, exciting and beautiful!

I'd like to thank Graham, the editor of LinuxVoice, for being so accommodating, helpful and patient with me.

By the way, I've been reading computer magazines for over 20 years and LinuxVoice has refreshed enthusiasm, community spirit, and quality content - best wishes for its future!

Grab a copy of issues 009 and 0010 - out now and next month!

Saturday, 27 September 2014

Oil Painting Fractals

I was exploring artistic filters in image editing software - you know the kind that make an image look like it was really sketched with an ink pen or painted in watercolours.

The usual software wasn't doing it for me because the effects looked very fake, so I explored further and found the free FotoSketcher. Its focus is purely on such effects - and it's brilliant. I particularly like the Painitng 5 (watercolour) and Painting 6  (oil) effects - they are very realistic.

Then it struck me - what if I applied these filters to fractal images? The results, in my opinion, are fantastic! Enjoy .... and do try it yourself!