Jun 7, 2010

Discovering Fractals: The Discrete Logistic Map

I've discovered another fractal for you, although this one doesn't have a really pretty picture like the other ones do. Instead the beauty of this one is in how weird the behaviour is. It is a very simple equation, yet can still manage to exhibit chaotic behaviour.

Here's the equation in C:
x = a * x * (1.0 - x);
Very simple. The variable x is some variable in between 0 and 1, and a is a fixed constant between 0 and 4.

The interesting part of this is when we execute this equation over and over. For small values of a the result is kinda boring, it converges to some fixed point and stays there. However once you start increasing a, some interesting things pop up. Here is a graph with a = 2.9..4 on the x-axis, and x = 0..1 on the y-axis:
At a = 3, the system no longer has a single fixed point, and begins to oscillate between two points. And around 3.45 it forks again into 4 points, and so on. Eventually you move into regions where it is chaotic, and doesn't really settle down. However even more interesting is how the chaotic regions break up into non-chaotic regions temporarily, and then go back to being chaotic. If you zoom in on these non-chaotic intervals you end up seeing that the region looks the same as the larger picture - which is why this is a fractal, it shows self-similarity.

Why would a programmer care about this? Well it's an example of a simple, completely deterministic discrete system that does not always stabilize, depending on the values of the parameters. It's possible for us to create much more complicated software systems that maybe have the same property - if we run the system 1000 times to see how it behaves, the 1001st (th?) time may still have completely different results. Same for the 1 000 000th and 1 000 001st times. The picture above is with 1000 iterations, but when I up it to 1 000 000 iterations the picture still looks the same (just takes longer to render). Because parts of this system are chaotic, no matter how many times you iterate it will not converge.
In short, an awareness of chaotic systems might be helpful when testing your programs.

If you want to see the code that generated image I have put up a gist that you can look at.

No comments: