速度提升 - 最佳化

對稱

曼德勃羅集合關於平面中的 x 軸對稱

colour(x,y) = colour(x,-y)

它與 x 軸的交點（曼德勃羅集合的實切片）是一個區間

<-2 ; 1/4>

它可以用來加速計算（最高 2 倍）^[1]

逃逸測試

而不是檢查幅度（半徑 = abs(z)）是否大於逃逸半徑（ER）

 ${\sqrt {Z_{x}^{2}+Z_{y}^{2}}}<ER$

計算 ER 的平方

 ER2 = ER*ER

一次，並檢查

 $Z_{x}^{2}+Z_{y}^{2}<ER^{2}$

它給出相同的結果，並且更快。

內部檢測

內部檢測方法^[2]

使用檢測和不使用檢測的時間分別為：0.383 秒和 8.692 秒，因此快了 23 倍 !!!!

// gives last iterate = escape time
// output 0< i < iMax
 int iterate(double complex C , int iMax)
  {
   int i=0;
   double complex Z= C; // initial value for iteration Z0
   complex double D = 1.0; // derivative with respect to z 
   
   for(i=0;i<iMax;i++)
    { if(cabs(Z)>EscapeRadius) break; // exterior
      if(cabs(D)<eps) break; // interior
      D = 2.0*D*Z;
      Z=Z*Z+C; // complex quadratic polynomial
      
    }
   return i; 
 }

週期檢測

復二次對映的週期 - 主要文章

"在渲染曼德勃羅集合或朱利亞集合時，影像中最耗時的部分是“黑色區域”。在這些區域中，迭代永遠不會逃逸到無窮大，因此每個畫素必須迭代到最大限制。因此，可以透過使用演算法提前檢測這些區域來節省大量時間，以便它們可以立即被塗成黑色，而不是像畫素一樣逐畫素地渲染它們。FractalNet 使用遞迴演算法將影像分割成塊，並測試每個塊以檢視它是否位於“黑色區域”內。這樣，影像的大片區域可以快速被塗成黑色，通常可以節省大量渲染時間。 ...（一些）塊被檢測為“黑色區域”並立即被塗成黑色，而無需渲染。（其他）塊以通常的方式逐畫素渲染。" Michael Hogg ^[3]

 // cpp code by Geek3 
// http://commons.wikimedia.org/wiki/File:Mandelbrot_set_rainbow_colors.png
bool outcircle(double center_x, double center_y, double r, double x, double y)
{ // checks if (x,y) is outside the circle around (center_x,center_y) with radius r
        x -= center_x;
        y -= center_y;
        if (x * x + y * y > r * r)
                return(true);
        return(false);

 // skip values we know they are inside
                        if ((outcircle(-0.11, 0.0, 0.63, x0, y0) || x0 > 0.1)
                                && outcircle(-1.0, 0.0, 0.25, x0, y0)
                                && outcircle(-0.125, 0.744, 0.092, x0, y0)
                                && outcircle(-1.308, 0.0, 0.058, x0, y0)
                                && outcircle(0.0, 0.25, 0.35, x0, y0))
                        {
                          // code for iteration
                         }

心形和週期-2檢查

改進計算的一種方法是提前找出給定點是否位於心形內或週期-2瓣內。在將複數值傳遞給逃逸時間演算法之前，首先檢查是否

(x+1)^{2}+y^{2}<{\frac {1}{16}}

以確定該點是否位於週期-2瓣內，以及

q=\left(x-{\frac {1}{4}}\right)^{2}+y^{2}

q\left(q+\left(x-{\frac {1}{4}}\right)\right)<{\frac {1}{4}}y^{2}.

以確定該點是否位於主心形內。

另一個描述 ^[4]

// http://www.fractalforums.com/new-theories-and-research/quick-(non-iterative)-rejection-filter-for-mandelbrotbuddhabrot-with-benchmark/
         public static void quickRejectionFilter(BlockingCollection<Complex> input, BlockingCollection<Complex> output)
         {
            foreach(var item in input.GetConsumingEnumerable())
            {
                if ((Complex.Abs(1.0 - Complex.Sqrt(Complex.One - (4 * item))) < 1.0)) continue;
                if (((Complex.Abs(item - new Complex(-1, 0))) < 0.25)) continue;
                if ((((item.Real + 1.309) * (item.Real + 1.309)) + item.Imaginary * item.Imaginary) < 0.00345) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary - 0.744) * (item.Imaginary - 0.744)) < 0.0088) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary + 0.744) * (item.Imaginary + 0.744)) < 0.0088) continue;

                //We tried every known quick filter and didn't reject the item, adding it to next queue.
                output.Add(item);
            }
         }

另見

Claude Heiland-Allen 的心形和瓣檢查

週期性檢查

曼德勃羅集合內部的大多數點在固定的軌道內振盪。它們之間可能有十個到數萬個點，但如果一個軌道到達一個它曾經到達過的點，那麼它將不斷地遵循這條路徑，永遠不會趨向於無窮大，因此在曼德勃羅集合內。

此曼德勃羅處理器包括

週期性檢查
週期-2瓣和心形檢查

在具有高最大迭代值的深度縮放動畫中，可以極大地加快速度。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Mandelbrot2
{
    public struct MandelbrotData
    {
        private double px;
        private double py;

        private double zx;
        private double zy;

        private long iteration;
        private bool inSet;
        private HowFound found;

        public MandelbrotData(double px, double py)
        {
            this.px = px;
            this.py = py;
            this.zx = 0.0;
            this.zy = 0.0;
            this.iteration = 0L;
            this.inSet = false;
            this.found = HowFound.Not;
        }

        public MandelbrotData(double px, double py,
                              double zx, double zy,
                              long iteration,
                              bool inSet,
                              HowFound found)
        {
            this.px = px;
            this.py = py;
            this.zx = zx;
            this.zy = zy;
            this.iteration = iteration;
            this.inSet = inSet;
            this.found = found;
        }

        public double PX
        {
            get { return this.px; }
        }

        public double PY
        {
            get { return this.py; }
        }

        public double ZX
        {
            get { return this.zx; }
        }

        public double ZY
        {
            get { return this.zy; }
        }

        public long Iteration
        {
            get { return this.iteration; }
        }

        public bool InSet
        {
            get { return this.inSet; }
        }

        public HowFound Found
        {
            get { return this.found; }
        }
    }

    public enum HowFound { Max, Period, Cardioid, Bulb, Not }

    class MandelbrotProcess
    {
        private long maxIteration;
        private double bailout;

        public MandelbrotProcess(long maxIteration, double bailout)
        {
            this.maxIteration = maxIteration;
            this.bailout = bailout;
        }

        public MandelbrotData Process(MandelbrotData data)
        {
            double zx;
            double zy;
            double xx;
            double yy;

            double px = data.PX;
            double py = data.PY;
            yy = py * py;

            #region Cardioid check

            //Cardioid
            double temp = px - 0.25;
            double q = temp * temp + yy;
            double a = q * (q + temp);
            double b = 0.25 * yy;
            if (a < b)
                return new MandelbrotData(px, py, px, py, this.maxIteration, true, HowFound.Cardioid);

            #endregion

            #region Period-2 bulb check

            //Period-2 bulb
            temp = px + 1.0;
            temp = temp * temp + yy;
            if (temp < 0.0625)
                return new MandelbrotData(px, py, px, py, this.maxIteration, true, HowFound.Bulb);

            #endregion

            zx = px;
            zy = py;

            int check = 3;
            int checkCounter = 0;

            int update = 10;
            int updateCounter = 0;

            double hx = 0.0;
            double hy = 0.0;

            for (long i = 1; i <= this.maxIteration; i++)
            {
                //Calculate squares
                xx = zx * zx;
                yy = zy * zy;

                #region Bailout check

                //Check bailout
                if (xx + yy > this.bailout)
                    return new MandelbrotData(px, py, zx, zy, i, false, HowFound.Not);

                #endregion

                //Iterate
                zy = 2.0 * zx * zy + py;
                zx = xx - yy + px;

                #region Periodicity check

                //Check for period
                double xDiff = Math.Abs(zx - hx);
                if (xDiff < this.ZERO)
                {
                    double yDiff = Math.Abs(zy - hy);
                    if (yDiff < this.ZERO)
                        return new MandelbrotData(px, py, zx, zy, i, true, HowFound.Period);
                } //End of on zero tests

                //Update history
                if (check == checkCounter)
                {
                    checkCounter = 0;

                    //Double the value of check
                    if (update == updateCounter)
                    {
                        updateCounter = 0;
                        check *= 2;
                    }
                    updateCounter++;

                    hx = zx;
                    hy = zy;
                } //End of update history
                checkCounter++;

                #endregion
            } //End of iterate for

            #region Max iteration

            return new MandelbrotData(px, py, zx, zy, this.maxIteration, true, HowFound.Max);

            #endregion
        }

        private double ZERO = 1e-17;
    }
}

參考文獻

T Myers：關於擾動的介紹...
拓撲最佳化解釋
導數外推來自曼德勃羅集合詞彙表和百科全書，作者 Robert Munafo，(c) 1987-2023。

[1] 如何使用集合的對稱性

[2] A Cheritat 維基：Mandelbrot_set#Interior_detection_methods

[3] Michael Hogg 的 FractalNet

[4] 分形論壇：快速（非迭代）Mandelbrot-Buddhabrot 排斥濾波器，含基準測試

[1]

[2]

[3]

[4]