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.
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.