Tuesday, March 22, 2005

Drawing Fractals With Interval Arithmetic - Part 1

Interval arithmetic is a radical programming paradigm that allows you to write provably rigorous algorithms, which I have blogged about before.

I have written a paper about the application of interval arithmetic to the problem of fractal rendering (if one can call it a "problem"). The paper is available here:

Drawing Fractals With Interval Arithmetic - Part 1

The paper includes a fractal-explorer tool for reproducing the results, a sample of which can be seen here:


The graphic on the left is a Mandelbrot drawn with the traditional single-point approach, and the one on the right is the result of the interval approach.

Like fractals, many (if not all) chaotic systems are iterative, and this paper has implications for simulating chaotic systems regardless of whether one uses interval or single-point methods.

In Part 2 I will try and quantify the results I am seeing, and investigate more sophisticated implementations of the maths behind the Mandelbrot equation.


adam said...

on your image there is no main cardioid, so I think that your image is not good.

Rupert said...

Hi Adam,

Thank you for taking the time to comment on my interval Mandelbrot work.

Regarding your question about the main cardioid:

The area marked in black in my image should be regarded as “definitely in” the Mandelbrot set. Areas with colour have no mathematically significant status (apart from not being definitely in). Therefore the main cardioid could still be in there somewhere. It is possible that, using the interval algorithm, there is too much rounding noise to cleanly resolve the edges of the main cardioid.

I have extended this work in a second paper that introduces two new states to the colouring: “definitely out” and “indeterminate”. If the main cardioid intersected the region labelled “definitely out” in my image, I would concede that an error must have occurred.

I would welcome your comments. From your website it is clear that you know a lot about fractals, and I am keen to expose this work to close scrutiny.