Iteration Intuition – Tony Finch

After writing my previous entry, I noticed that the final equation is in fact just the negated log of the Douady-Hubbard potential (assuming n is practically infinite). (In the following I will use the binary logarithm throughout, lg x = log₂ x.)

\begin{matrix} - lg 𝜙_{c} (z) & ≃ & - lg \frac{lg r_{n}}{lg 2^{n}} \\ = & lg 2^{n} - lg lg r_{n} \\ = & n - lg lg r_{n} \end{matrix}

I didn’t really understand this so I sought a more intuitive explanation.

Observe that when z is large, f_c(z) is very close to f₀(z). So in the following we can treat the crinkly component c as insignificant.

\begin{matrix} z_{n} & = & f_{c}^{n} (z) ≃ z^{2^{n}} \\ lg lg z_{n} & ≃ & lg lg z^{2^{n}} \\ = & lg 2^{n} lg z \\ = & lg 2^{n} + lg lg z \\ = & n + lg lg z \end{matrix}

So the double log gives us a sort of measure of distance in terms of the number of iterations needed to get from z to z_n.

\begin{matrix} n & = & {log}_{2} 2^{n} \\ = & {log}_{2} {log}_{z} z^{2^{n}} \\ = & lg \frac{lg z^{2^{n}}}{lg z} \\ = & lg lg z^{2^{n}} - lg lg z \\ ≃ & lg lg z_{n} - lg lg z \end{matrix}

Recall that

\begin{matrix} z & = & r e^{i θ} \\ z^{p} & = & r^{p} e^{p i θ} \end{matrix}

Hence the equations in z also apply to r = |z|,

\begin{matrix} - lg lg z & ≃ & n - lg lg z_{n} \\ - lg lg r & ≃ & n - lg lg r_{n} \end{matrix}

When z is close to the set, r is slightly greater than one (plus crinkles), so lg r is a small positive number, and lg lg r is a large negative number. Hence the negation to turn it into the equivalent of an iteration count.

The equation above also relates back to the definition of the electrostatic potential and our simplifying approximation, that is,

\begin{matrix} 𝜙_{c} (z) & ≃ & lg r \end{matrix}

Thinking about what happens when we finish iterating,

\begin{matrix} r_{n} & > & R & > & r_{n - 1} \\ r_{n} & ≃ & r_{n - 1}^{2} \\ R^{2} & > & r_{n} & > & R \end{matrix}

So lg lg r_n lies between two numbers with a difference of one,

\begin{matrix} lg lg R^{2} = 1 + lg lg R \end{matrix}

When lg lg r_n is subtracted from n, it contributes a fractional part and a fixed offset determined by the bail-out radius.

Finally, on a practical note I find that a better function for colouring pixels is to take the log again:

\begin{matrix} m = lg (n - lg lg r_{n}) \end{matrix}

The extra log gives the value a more uniform gradient so it cycles through the colours evenly, and it gets much closer to the set before it flies off to infinity so less of the picture suffers from aliasing. Even better, it retains these properties as you zoom in.