I'm writing a super-fast, super-accurate Mandelbrot set plotter. This one is unusual in that no explicit iteration limit is ever set - it will keep iterating any point until it either escapes or is determined to be in the set. This works pretty well and produces much sharper cusps than any other program I've seen.
However, the downside is that it can take an arbitrarily long to determine if any given point is in the set or not. Points on the edge of the set are (as always) the particularly tricky ones - some of them exhibit chaotic behavior for a very long time before becoming periodic or escaping.
Currently I use two methods for determining if a point is in the set. I have explicit formulae for the main cardioid and the period-2 bulb, and I look for periodic orbits using Floyd's algorithm.
I'm wondering if a third method might be practical - one that determines if a point is in the set without waiting for it to become periodic. Here's the method I'm considering.
Let the Mandelbrot iteration function f(z) = z2 + c. Suppose we have a point c, and we suspect that it might be periodic with period N. We can determine if it is or not by finding a point zf that is unchanged under N applications of f, i.e. a solution to fN(zf) = zf. There will generally be 2N such solutions, of which only N will be relevant to the case at hand. However, if we have a z that is likely to be near one of these fixed points we should be able to converge on one of them quickly by using Newton's method or something similar.
Once we have our fixed point, we take the derivative of fN with respect to c and evaluate it at zf. This is easy to do numerically - just evaluate fN at zf and a nearby point, take the difference and divide by the original distance. If the modulus of the result is 1 or less, then the attractor is stable and c is in the set. If it isn't, the point could still be in the set as we might have picked the wrong zf or N - that is we are likely to get false negatives but no false positives using this method (which is exactly what we want - if we get a false negative we can
iterate some more, try a new N and/or a new zf and eventually get the right answer).
Working through these steps symbolically gives us closed form solutions for the period-1 and period-2 attractors but if we try it for period 3 we get a polynomial of order 6 in z (23 = 8 minus the two from factoring out the period-1 attractor) - I'm not sure if we can get a closed form solution for period-3 attractors from this.
The tricky part is choosing an appropriate N and an approximation to zf for any given point. I think the way to do it is this: whenever we find a periodic point with Floyd's algorithm, iterate a further N times to figure out the period, and store the period and fixed point. When we start a new set of iterations on a point, check to see if any neighbouring points are periodic. If they are, try this method using the N from that point and the zf (appropriately adjusted for the new c). When we find a periodic point this way, we store the found N and zf just as for Floyd's algorithm.