Rescaled iterations

From Fractal Wiki
Jump to navigation Jump to search

When Perturbation theory is used for deep zooms, hardware Number types for the low-precision deltas can underflow to 0. This can be worked around by rescaling iterations so that the variables are closer to 1 in magnitude.

Rescaled iterations

Recall the perturbed iteration formula for the Mandelbrot set:

[math]z \to 2 Z z + z^2 + c[/math]

Substitute throughout an unevaluated product [math]z = s w[/math] and [math]c = s d[/math] to get:

[math]s w \to 2 Z s w + s^2 w^2 + c[/math]

Divide throughout by [math]s[/math] to get:

[math]w \to 2 Z w + s w^2 + d[/math]

This can be optimized when [math]s[/math] and/or [math]d[/math] underflow to 0.

Full iterations

When [math]Z[/math] is small (e.g. it underflows to 0 in the hardware low-precision number type), the contribution of the other terms is more significant, so this iteration needs to be performed in full range (for example using Number types#Floatexp).


Rescaling needs to be performed with a full range type for [math]z[/math] and [math]S[/math], with [math]w, d, s[/math] in a hardware low-precision (and low-range) type:

z = S * w;
S = abs(z);
w = z / S;
d = c / S;
s = S;

As well as after each full iteration, rescaling needs to be performed occasionally (typically a couple of hundred iterations) when [math]w[/math] risks overflowing the hardware low-precision number type.


Derivatives can be rescaled similarly. For example for Mandelbrot set (the z in the derivatives is the value of Z+sz in the perturbation):

[math] d \to 2 d z + \frac{\partial c}{\partial k} [/math]

becomes via [math]e = s d[/math]

[math] s d \to 2 s d z + \frac{\partial c}{\partial k} [/math]


[math] e \to 2 e z + \frac{\partial c}{\partial k} / s [/math]

has the last term approximately 1 or less as s is around |z| which is usually bigger than the pixel spacing [math]\frac{\partial c}{\partial k}[/math]

rescaled by

d = S * e;
S = abs(z);
e = d / S;
t = S

i.e. use the same scaling factor for the derivative as the perturbed orbit (mixing scale factors seems more trouble than it's worth), and scale the derivative by pixel spacing instead of scaling the distance estimate at the end for screen-space colouring (this avoids overflow).

"Full" iterations need to be performed when |z| is small. Usually the perturbation is small so this is small when the reference |Z| is small, and if |z| is small when |Z| is not small a glitch is detected by Pauldelbrot's heuristic, so full iterations only need to be performed at the same time as the full iterations of the perturbed z.