4
$\begingroup$

I have successfully implemented a realtime Julia/Mandelbrot set generator on the GPU. Primarily out of curiosity, what I'm looking for now is a faster test algorithm.

Ideally, I want a boolean function that would tell whether a point is within the set. This is currently performed in the classic way with a bunch of iterations (maybe 100 or 1,000, or more). On the GPU, which doesn't like branching code, this is problematic.

I'm speculating that because the Julia/Mandelbrot Sets are infinitely complex, no constant time algorithm can give such an answer. However, I'm hoping that there are at least faster algorithms. I don't care about convergence rate information--just a simple yes/no function is all that is needed.

  • 0
    I don't know about constant-time tests, but see [Efficient computation of Julia sets and their fractal dimension](http://www.inf.uni-konstanz.de/gk/pubsys/publishedFiles/Saupe87.pdf) by Saupe for some fast algorithms. See also [The Beauty of Fractals](http://en.wikipedia.org/wiki/The_Beauty_of_Fractals) and *The Science of Fractal Images*.2012-08-27

2 Answers 2

3

In some instances, it might be quicker to see if the derivative converges or diverges. That is, if you want to test point $z,$ then look at $(f^n(z)-f^n(z+h))/h$ for a small value of $h.$ If this number is small, (in magnitude) then you should be inside the Mandelbrot/Julia set, if outside, this is a large number. The point is, you may use a much smaller $n$ than needed to check if $f^n(z)$ itself is large.

I have not heard of a way to "cheat" and not iterate the function in some sense. You might be able to speed up the computation by symbolically pre-computing a high iteration, and optimize the representation of the output, to make it compute quicker.

  • 0
    I had some luck with that in a slightly different setting. Notice that for an animation or similar, this might be a great speedup, since symbolic evaluation is independent of scale etc. But the symbolic computation needs to be compiled somehow.2012-11-07
1

For the Mandelbrot set, you can implement a quick test for a large part of the image using the fact that equations are known for the main cardiod and for the circular disk to the left of it (and probably for the other large bulbs). However, this does not really help with zooms.