Fast algorithms for external angle computations Two related problems related to the complex quadratic polynomial $f_c(z) = z^2 + c$ and Mandelbrot and/or Julia sets:

*

*find an external angle $\theta_c$ for a complex point $c$


*find a complex point $c_\theta$ for an external angle $\theta$.
Currently I can do both of these by tracing external rays (outwards for 1, inwards for 2), but it is asymptotically too slow to be practical: $O(n^2)$ where $n$ is the sum of the preperiod and period of the external angle — which is even ignoring the additional cost of multiplication of high precision numbers.
I implemented Wolf Jung's Spider Algorithm with a Path (see The Thurston Algorithm for quadratic matings, in the appendix; for finding $c_\theta$), it seems to be $O(n^2)$, and with worse constant factors (possibly even asymptotically worse?) compared to ray tracing as it needs full precision right from the start ($O(n)$ bits) and does complex square roots — ray tracing does only arithmetic and needs only enough precision to resolve the steps between ray points (which I think increases roughly linearly for the section of the ray that I'm interested in: just close enough that Newton's method can find $c_\theta$), spider path needs enough precision to resolve the starting points on the unit circle.
Are there better algorithms?  What is the asymptotic cost of the original Spider Algorithm (see Hubbard and Schleicher - The Spider Algorithm), for example?  Homotopy methods (see Chan - A comparison of solution methods for Mandelbrot-like polynomials) using differential equations seem to find all $O(2^n)$ roots in $O(n 2^n)$ time, could they be adapted to find 1 specific root in less than $O(n^2)$ time?  Would perhaps the representation of external angles as angled internal addresses (see Schleicher - Internal addresses in the Mandelbrot set and Galois groups of polynomials) be relevant here?
In practice, many of the $\theta$ I'm interested in will have angled internal addresses of particularly simple and regular forms with exponentially increasing periods, one example (from Morris - Old Wood Dish):
$$ 1 \overset{\frac12}\longrightarrow 2 \overset{\frac{16}{17}}\longrightarrow 33 \overset{\frac12}\longrightarrow 34 \overset{\frac13}\longrightarrow 69 \overset{\frac12}\longrightarrow 70 \overset{\frac13}\longrightarrow 141 \overset{\frac12}\longrightarrow 142  \cdots \\ \overset{\frac13}\longrightarrow (p-1) \overset{\frac12}\longrightarrow p \overset{\frac13}\longrightarrow (2p+1) \overset{\frac12}\longrightarrow (2p+2) \cdots$$
 A: This is more of a comment than a real answer, but it's too long for a comment:
Since you raise the question of practical computations, a long time ago I computed a small "database" of points on the Mandelbrot set, available here, containing a few tens of thousands of boundary points with rational external angles of small denominators, as well as, for points which are component roots, the corresponding component center, all being computed with machine accuracy.  (I never did anything with this database except from putting it online; I didn't really publicize it, and it didn't receive any attention of any sort.)
This may not be what interests you, because it only concerns points with small preperiod and period, and I don't think the algorithms were particularly intelligent, but if you want I can make the code available.  (Sadly, I've forgotten all about what this is about, so I can't really explain how any of it works, but there are a few comments.  From what I can see, I seem to trace the external rays approximately to a certain point, and then use Newton's method to find a periodic point with the appropriate structure — this, of course, depends crucially on the fact that the preperiod and period are small.)  Even if you don't find the code interesting, the result (linked above) might be worth looking at, if you need to check whatever better algorithm you find.
(The format of the database is itself a bit cryptic, I'm not sure what the last column means, but the first few columns are obviously the rational external angle expressed in turns, the real and imaginary part of the point, and whether the point is a Misiurewicz point, component root or component center; the last column probably has something to do with the preperiod and period.)
A: (Too long for a comment, an answer for some special cases that occur often in practice.)
For $\theta$ with "nice" angled internal address patterns, like the Old Wood Dish example, a good speedup is possible using perturbation techniques. Perturbation involves finding $f(X+x)$ in terms of $f(X)$ and some $g(X,x)$ where $g$ can operate in lower precision.
Conjecture 1: the precision required to find a root of period $n$ is $O(n)$ worst case. Call the number of bits required $k(n)$
Conjecture 2: tracing an external ray to dwell $An+B$ is sufficient for Newton's method to converge to the correct root of period $n$, for some constants $A$ and $B$. $A=3$ seems easily sufficient, $B$ depends on the escape radius.
External ray tracing with full precision costs $O(n^2 M(k(n)))$ where $M(b)$ is the cost of multiplication of $b$-bit numbers.
Finding a root of period $n$ using Newton's method given a good initial guess costs $O(n M(k(n)))$.
Ray tracing using perturbation from a nearby root of period $m$ costs $O(m M(k(m)) + n^2 M(d(n)))$, where the first term is the calculation of the orbit in high precision, and the second term is the calculation using low precision differences from the orbit.
Ray tracing and root finding can be alternated to go further along the angled internal address.
$d(n)$ is typically $O(log(n))$ depending on the location. The number of circular features around the root often doubles or quadruples each next step along the angled internal address, so the precision required goes up linearly, while the period goes up exponentially.
$n$ is typically a small constant multiplied by $m$, and $M(k(m))$ is at least linear (less than quadratic is typical).
So, as the first term dominates, perturbation techniques reduce the asymptotic cost (for nice examples at least...) of finding period $n$ roots $c$ given $\theta$ by a factor of $n$. Presumably the same applies for finding $\theta$ given $c$.
In practice, my first test of this method at period 9214 reduced runtime from 5 hours to 20 minutes, not quite as much as I'd hoped.
