Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I don't know about constant-time tests, but see Efficient computation of Julia sets and their fractal dimension by Saupe for some fast algorithms. See also The Beauty of Fractals and The Science of Fractal Images. –  lhf Aug 27 '12 at 21:40

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Though I haven't tested it, I doubt that symbolically pre-computing a high iteration will make the computation quicker. It'll probably give the compiler a hard time for generating code. Iteration is so much simpler... –  lhf Nov 5 '12 at 0:05
    
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. –  Per Alexandersson Nov 7 '12 at 13:20

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.