The Programmer's Guide to Fractals
Written by Mike James   
Article Index
The Programmer's Guide to Fractals
Fractal Dimension
Julia Sets

Fractals encompass interesting pure math and computing - and  are very pretty to look at. It is almost a rite of passage that every programmer has to face - write some sort of fractal viewer!

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

theorycover

Contents

  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

We all know what a fractal is, sort of, even if it’s only a picture of the well known Mandelbrot set. If you don't, this video is a good introduction:

 

I wanted to start this discussion off with a short snappy definition of a fractal but, even though I think I know what the subject is about, I found it next to impossible to frame a pithy definition that means something practical.

The best I can come up with is that a fractal is something that "wiggles" so much that it manages to cover more space that it should.

The problem seems to be that theory of fractals includes a number of interesting and important ideas that can be blended together to give you more than one thing.The key common factor in all of them is that a fractal has a fractional dimension - its not one dimensional nor two but something like 0.4134 or 2.5.

So in the strict mathematical sense a fractal is something that has fractional dimension.

An easy definition but very weird and difficult to understand - how can something be 1.5 dimensional?

Fractals encompass interesting pure maths and computing. You can spend ages contemplating the theory or make direct use of them in 3D modelling, modern art, image compression or coding theory. So starting at the beginning…

I first got involved with fractals and computers while working on what I thought was a simple problem. A computer vision system was supposed to be used to measure the length of the perimeter of a shape. A TV camera was used to digitise the image and, roughly speaking, the solution to the problem was to count the pixels in the outline. At first we couldn’t get an answer that was accurate enough so we zoomed in and got a more accurate result.

The result, even allowing for the zoom factor, was bigger and as we zoomed in more the result got even bigger. We discovered that the perimeter of a real shape wasn’t actually a fixed number which could be measured to any given accuracy – the value you got depended on the accuracy.

 

mandelbrot

Benoit Mandelbrot (1924 -2010)
the man who invented the Mandelbrot set

 

It turned out that this was an encounter with a classical fractal problem first raised by Benoit Mandelbrot in the question “How long is the coastline of Britain?”.

This might seem like an entirely silly question that has nothing very deep to do with mathematics or computing but…

Suppose you go out with a meter stick and measure it then you will get a value that misses all of the wiggles that are much smaller than a meter. If you go and measure it with a 1cm ruler then the length that you measure will increase because you follow the wiggles. Each time you make your measurement finer you encounter more wiggles and the coastline gets longer. In the limit the coastline of Britain is infinite – which make you wonder why even in a small island it seems to be in short supply!

In what sense then is the coastline “fractal”?

Part of the answer is encapsulated in my rough definition of "something that "wiggles" so much that it manages to cover more space that it should.". You can see that the reason for the strange behavior is in the "wiggles" that the coast line makes as it finds its way round the country.

However there is a little more to this and just excessive wiggling. The coast line also demonstrates a deeper property of fractals that of "self similarity".

The coastline is “self similar” at a range of scales. This idea of self similarity is complicated but the rough idea isn’t difficult to understand. If you look at the coastline then what you see looks the same at any zoom factor you care to select.

It isn’t that it is exactly identical, just that the degree and type of wigglyness that you see is the same – it’s statistically the same at all levels of zoom. What this means is that if you were shown a photo of part of the coastline you would find it impossible to tell how close or what the zoom factor was on the photo by just examining how much and in what way it wiggled. The geometry of the shape is the same at all levels.

For most naturally occurring and many constructed fractals the self similarity is only statistical but it is possible to create one-dimensional curves that are exactly self similar at all levels of zoom.

For example the Sierpinski triangle looks the same no matter how much you zoom in.

 

serpinski

The Sierpinski triangle

 

 

<ASIN:0716711869>

<ASIN:0470848626>

<ASIN:0387201580>