Fractals/perturbation

Fast deep zoom

Perturbation method

"The thing we call perturbation consist of 2 things: Calculate one pixel with high precision and use it as a reference for all other pixels.

This method will fail though, however thanks to Pauldelbrot we have a trustable method of detecting the pixels where the reference fails to compute the pixel with hardware precision. These pixels can be rendered with a reference closer to these pixels, so a typical perturbation render use several references. This method gives a speedup at about 10 times on depths of 10^100 Use a truncated Taylor series to approximate a starting value for a specific iteration, which make you able to skip all previous iterations. This method gives a speedup of typically Another 10 times on depths of 10^100, and together the speed up is typically 100 times. This, which we call Series Approximation, is where we have issues since we do not have any solid theoretically way of finding when too many iterations are skipped - for all pixels in the view. The more terms you include in the Taylor series, the more iterations you are able to skip. So if you stay below say 50 terms, it is not likely that you ever encounter any issues. Because some views can be correctly rendered 1000 or 100,000 times faster than full precision for each pixel with many terms - can you imagine a month turned into seconds! shocked K.I.Martin originally used only 3 terms " - Kalles Fraktaler

Description

Very highly magnified images require more than the standard 64-128 or so bits of precision most hardware floating-point units provide, requiring renderers use slow "bignum" or "arbitrary precision" math libraries to calculate. However, this can be sped up by the exploitation of perturbation theory. Given

$z_{n+1}=z_{n}^{2}+c$

as the iteration, and a small epsilon, it is the case that

$(z_{n}+\epsilon )^{2}+c=z_{n}^{2}+2z_{n}\epsilon +\epsilon ^{2}+c$

or

$z_{n+1}+2z_{n}\epsilon +\epsilon ^{2}$

so if one defines

$\epsilon _{n+1}=2z_{n}\epsilon _{n}+\epsilon _{n}^{2}$

one can calculate a single point (e.g. the center of an image) using normal, high-precision arithmetic (z), giving a reference orbit, and then compute many points around it in terms of various initial offsets epsilon-zero plus the above iteration for epsilon. For most iterations, epsilon does not need more than 16 significant figures, and consequently hardware floating-point may be used to get a mostly accurate image. There will often be some areas where the orbits of points diverge enough from the reference orbit that extra precision is needed on those points, or else additional local high-precision-calculated reference orbits are needed. This rendering method, and particularly the automated detection of the need for additional reference orbits and automated optimal selection of same, is an area of ongoing, active research. Renderers implementing the technique are publicly available and offer speedups for highly magnified images in the multiple orders of magnitude range.

Newton-Raphson zooming

One can "use newton's method to find and progressively refine the precision of the location of the minibrot at the center of a pattern. This allows them to arbitrarily select a magnification between the location they started at and the final minibrot they calculate to be at the center of that location."

Glitches

Glitches

glitches in perturbation method How to detect glitches:

• heuristic developed by Pauldelbrot ( most common)
• heuristic using interval arithmetic developed by knighty

How to choose reference point ( by Claude):

• simple method: "take the first reference to be the center of the image, and correct any glitches that result (including those resulting from the reference escaping too early) by adding more references within the glitches, recalculating only those pixels that need it. A simple approach can still yield accurate results, albeit in less than optimal time"
• " trying periodic points (the nuclei of the minibrot islands deep in the set) and preperiodic points (the Misiurewicz points at the centers of spirals), both of which can be found by Newton's method (finding their (pre)periods is a bit harder, but not impossible). Higher-period "structural" minibrot nuclei seem to be the most favoured as they are relatively easy to find while also emitting fewer glitched pixels than lower period nuclei"

Types of glitches by Claude: 1. Reference escapes early, this type can be avoided by picking a non-escaping reference 2. Too-different dynamics (detected easily by Pauldelbrot's heuristic, detected accurately by gerrit's backwards error analysis, think knighty had another method too)

Type 1 can be improved by picking a random glitched pixel as the new reference and retrying

Type 2 can sometimes be fixed by using pixel with minimum |z| at the glitch iteration (possibly using derivative for 1 step of Newton's method to make it closer to a miniset), but often picking a random pixel works just as well - the advantage for minimum |z| comes for Mandelbrot set where you don't need to restart iterations from the beginning because minisets are periodic through 0 and the period is the glitch iteration (I use this in my mandelbrot-perturbator thing)

KF uses an algorithm I don't really understand for finding the "glitch center" based on pixel regions, but also has options for random choice and minimum |z| (without the fancy stuff from mandelbrot-perturbator). Locations:

• "a minibrot near -2+0i at very deep zooms, chances are you'll end up with a Moire mess of stars, instead of concentric rings of rays (because the rays will be regularly spaced finer than the pixel spacing, leading to interference)."

Knighty's SMB which I think is still a bit faster than KF though being more of a testbed than a usable renderer puts the glitches in distinct sets (G1,.., Gn) with same iteration number where glitch was detected. Next references will then be 1 random pixel from each of the G1,..,Gn and is used only to recalculate the pixels in each set G. Secondary glitches simply generate another set G and you just put then in some queue or stack and keep going at it till no more G sets left. When dealing with glitched pixels you can use the same series expansion as a starting point. ( Gerrit)

Rebasing

Rebasing means resetting the reference iteration to the start when the pixel orbit (i.e. Z+z , the reference plus delta) gets near a critical point (like 0+0i for the Mandelbrot set). If there is more than one critical point, you need reference orbits starting at each of them, and this test can switch to a different reference orbit. For this case, pick the orbit o that minimizes |(Z−Zo)+z| , among the current reference orbit at iteration whatever, and the critical point orbits at iteration number 0 . Rebasing means you only need as many reference orbits as critical points (which for simple formulas like the Mandelbrot set and Burning Ship means only one), and glitches are avoided rather than detected, needing to be corrected later. This is a big boost to efficiency (which is nice) and correctness (which is much more important).

Effects

• Effects

Perturbation algorithm with series approximation ( 100 times faster on zoom levels around e100! )

Precision

For deeper zooms there are 3 options:

• double/float64 (until e300 or so, some hardware has greatly reduced performance vs float32)
• float32 + separate int32 exponent ("floatexp") (or int16 could work for intermediate zooms until e9800 or so)
• fully software floating point (two uint32, one for mantissa, the other for sign and exponent)
• prec = 53 - log2(view_radius)) See also code: code.mathr.co.uk/fractal-bits/mandelbrot-perturbation-error/mandelbrot-perturbation-error.c

history

• 2 independent descriptions :
  • Fast Mandelbrot set with infinite resolution by Sergey Khashin (July 9, 2011)
  • perturbation method by K.I. Martin (2013-05-18) ( only use 3 Series Approximation terms )
• Pauldelbrot's glitch detection method
• extending Martin's description to handle interior distance estimation too by Claude Heiland-Allen

Programs

• SuperFractalThing in Java by K.I. Martin
• mightymandel by Claude Heiland-Allen
• mandelbrot-perturbator by Claude Heiland-Allen : http://code.mathr.co.uk/mandelbrot-perturbator/
• persianney : fractalNotes.pdf
• Kalles Fraktaler for windows
• perturbation_algebra and et
• interactive SageMath worksheet explaining how it works, try changing the formula
• FractalZoomer
• MandelbrotPerturbation by ShiromMakkad

Compare

• parabolic perturbation
• reference-compression algorithm

References

• 2021-05-14 deep zoom theory and practice by Claude
• 2022-02-21_deep_zoom_theory_and_practice_again
• m-perturbation