優化Mandelbrot分形

Question

這是一個在.ppm文件中輸出mandelbrot分形的代碼。我怎樣才能優化這個？

#include<bits/stdc++.h> 
using namespace std; 

int findMandelbrot(double cr, double ci, int max_iterations) 
{ 
    int i = 0; 
    double zr = 0.0, zi = 0.0; 
    while (i < max_iterations && zr * zr + zi * zi < 4.0) 
    { 
     double temp = zr * zr - zi * zi + cr; 
     zi = 2.0 * zr * zi + ci; 
     zr = temp; 
     ++i; 
    } 
    return i; 
} 

double mapToReal(int x, int imageWidth, double minR, double maxR) 
{ 
    double range = maxR - minR; 
    return x * (range/imageWidth) + minR; 
} 

double mapToImaginary(int y, int imageHeight, double minI, double maxI) 
{ 
    double range = maxI - minI; 
    return y * (range/imageHeight) + minI; 
} 

int main() 
{ 
    ifstream f("input.txt"); 
    int imageWidth, imageHeight, maxN; 
    double minR, maxR, minI, maxI; 

    if (!f) 
    { 
     cout << "Could not open file!" << endl; 
     return 1; 
    } 

    f >> imageWidth >> imageHeight >> maxN; 
    f >> minR >> maxR >> minI >> maxI; 

    ofstream g("output_image.ppm"); 
    g << "P3" << endl; 
    g << imageWidth << " " << imageHeight << endl; 
    g << "255" << endl; 


    double start = clock(); 

    for (int i = 0; i < imageHeight; i++) 
    { 
     for (int j = 0; j < imageWidth; j++) 
     { 
      double cr = mapToReal(j, imageWidth, minR, maxR); 
      double ci = mapToImaginary(i, imageHeight, minI, maxI); 

      int n = findMandelbrot(cr, ci, maxN); 

      int r = ((int)sqrt(n) % 256); 
      int gr = (2*n % 256); 
      int b = (n % 256); 

      g << r << " " << gr << " " << b << " "; 
     } 
     g << endl; 

     if(i == imageHeight/2) break; 
    } 

    cout << "Finished!" << endl; 

    double stop = clock(); 

    cout << (stop-start)/CLOCKS_PER_SEC; 
    return 0; 
} 

我一直走到imageHeight/2，因爲在Photoshop中，我可以複製另一半。 我在想loghartimic權力，但嘗試過的東西，只有整數工程...

Answer 1

所以這是熱循環：

int i = 0; 
double zr = 0.0, zi = 0.0; 
while (i < max_iterations && zr * zr + zi * zi < 4.0) 
{ 
    double temp = zr * zr - zi * zi + cr; 
    zi = 2.0 * zr * zi + ci; 
    zr = temp; 
    ++i; 
} 
return i; 

我知道如何實現快速的CPU指令的非整數次冪，但它不會讓你脫離束縛，因爲它根本不適用於複雜數字。也不會使用std :: complex幫助。您不會爲非內聯支付任何費用，並且當您找到它們時肯定無法應用優化。所以，我能做的最好的是這樣的：

int i = max_iterations; 
double zr = 0.0, zi = 0.0; 
do { 
    double temp = zr * zr - zi * zi + cr; 
    zi = 2.0 * zr * zi + ci; 
    zr = temp; 
} while (--i && zr * zr + zi * zi < 4.0) 
return max_iterations - i; 

是的，我知道以一個整數測試圈外沒有太大買了這一切。我只發現了另一個優化器，你必須檢查它是否真的更快：

int i = max_iterations; 
double zr = 0.0, zi = 0.0; 
do { 
    double tempr = zr * zr - zi * zi + cr; 
    double tempi = zr * zi; 
    zi = tempi + tempi + ci; 
    zr = tempr; 
} while (--i && zr * zr + zi * zi < 4.0); 
return max_iterations - i; 

這就是所有的人。

Answer 2

在findMandelbrot中，在循環測試中使用表達式zr * zr和zi * zi，但如果測試成功，則重新計算相同的兩個表達式。所以，一個明顯的改善可能是緩存那些具有類似......

int findMandelbrot (double cr, double ci, int max_iterations) 
{ 
    int i = 0; 
    double zr = 0.0, zi = 0.0; 
    double zr2 = 0.0, zi2 = 0.0; 
    while (i < max_iterations && zr2 + zi2 < 4.0) { 
    double temp = zr2 - zi2 + cr; 
    zi = 2.0 * zr * zi + ci; 
    zr = temp; 
    zr2 = zr * zr; 
    zi2 = zi * zi; 
    ++i; 
    } 
    return(i - 1); 
}