Zbiór Mandelbrota - przyspieszanie działania

Dzień dobry
Ostatnio poczytałem trochę o fraktalach i chciałem sobie klepnąć programik programik który generowałby takowe. Natrafiłem na problem w postaci czasu generowania obrazu. Czy istnieje jakaś szybka metoda wyznaczania granic funkcji rekurencyjnych dla liczb zespolonych ? Teraz po prostu iteruje z jakimś tam swoim przybliżeniem i sprawdzam czy punkt należy do zbioru (tz. jak chcę obrazek fraktalu 600x600 to jest for(i=0;i<360 000) i liczę czy punkt leży w zbiorze dla danego piksela). Aktualnie sytuacja wygląda tak:

 /* Contains */
            
            ComplexNumber z = new ComplexNumber(realPart,imaginaryPart);
            
            for (int i=0;i<accuracy;i++)
            {
                if(z.ModulusSquare >= 4)
                    return false;
                z.SquareIt();
                z.Add(realPart,imaginaryPart);
            }
            
            return true; 

  Bitmap image = new Bitmap(size.Width,size.Height);
            BitmapEditor editor = new BitmapEditor(image);
            
            editor.LockBits();
            //Main fractal iterations
            for (int iter = 0; iter < accuracy; iter++)
            {
                ProcessAccuracyLayer(ref image,iter,area,editor);

                if (RenderCompleteCall != null)
                {
                    RenderCompleteCall(iter);
                }
            }

            editor.UnlockBits();

            return image;

Tutaj: "ProcessAccuracyLayer"

  Position coordinate;
            Size imgSize = new Size(img.Width,img.Height);
            UnitConverter converter = new UnitConverter();

            // real & imaginary (width/height) iterations on complex plain
            for (int r = 0; r < img.Width; r++)
            {
                for (int i = 0; i < img.Height; i++)
                {
                    coordinate = converter.ConvertToPlainPoint(area, imgSize, r, i);
                    if (Contains(new ComplexNumber(coordinate.X, coordinate.Y), iteration))
                    {
                        editor.SetPixel(r, i, _colorPalette.GetColor(iteration));
                    }
                }
            }

Czy da się to zrobić innym sposobem - czytałem artykuły o generowaniu zbioru i niestety nic nie znalazłem.

Pozdrawiam
Astrocyt

Sprawdź czy taka szybkość Ci odpowiada. http://bogdan.students.wmi.amu.edu.pl/education/fraktale/Mandelbrot.html
To jest aplet Javy, musisz mieć zainstalowaną Javę i zezwolić przeglądarce na uruchamianie apletów.
Jeżeli Twój kod działa bardzo wolno, to pewnie masz za duża wartość zmiennej accuracy (obliczasz zbyt dużo wyrazów ciągu).

Wykorzystaj CUDA/OpenCL, to idealny przykład.

1. zła kolejność pętli iterowania po pikselach. Skaczesz ciągle po różnych fragmentach pamięci co powoduje częsty cache miss i prowadzi do bardzo dużych problemów z wydajnością. Sama zamiana tych pętli poprawi znacznie wydajność
2. Wyciągnij te new tak by nie było tworzone na nowo dla każdego pixela, a również uzyskasz poprawę wydajności.

Wywaliłem new ComplexNumber(...) i działa tak na oko o 35-40% szybciej więc jest dużo lepiej.

@MarekR22

Mógłbyś rozwinąć o co chodzi z tą złą kolejnością iterowania i skakania po pamięci ?

Cała klasa BitmapEditor pochodzi z tej strony : http://www.codeproject.com/Tips/240428/Work-with-bitmap-faster-with-Csharp
I jeszcze mam takie pytanko. Czy zamiana zmiennych w pętli na wskaźniki i ogólnie zrobienie całej klasy MandelbrotSet na wskaźnikach (wszystkie zmienne) dadzą poprawę wydajności czy to już będą cuda na kiju ?

Dziękuję za pomoc.
Pozdrawiam
Astrocyt

Profiler. Serio. NIGDY nie próbuj optymalizować "na jana". Odpal profiler i zobacz co zabiera tyle czasu. Zaoszczędzisz sobie troche czasu, nerwów i pieniędzy które przepuściłbyś u wróżbity macieja.

Astrocyt napisał(a):

Mógłbyś rozwinąć o co chodzi z tą złą kolejnością iterowania i skakania po pamięci ?

To proste, dostęp do pamięci odbywa się z pomocą cache, który jest bardzo szybki. Jeśli procesor odnosi się do pamięci sekwencyjnie lub w ramach małego fragmentu pamięci (zwykle jest kilka takich fragmentów pamięci) to cache jest wykorzystywany optymalnie co znacznie przyspiesza aplikację.
Bitmapy są zorganizowane w ten sposób, że pojedynczy wiersz (y) jest jednym ciągłym kawałkiem pamięci, w którym znajdują się kolejne piksele dla kolejnych wartości x. Jeśli wewnętrzna pętla iteruje po x, to program częściej odnosi się do kolejnych komórek pamięci, więc zalicza mniej cache miss i aplikacja będzie działać szybciej.

z.SquareIt();
z.Add(realPart,imaginaryPart);

Nie licz na liczbach zespolonych. Traktuj je jako parę liczb (x+iy) i z tej postaci wyprowadź dwa wzory, ile wynosi nowe x i nowe y.
W ten sposób wykonasz mniej działań w każdej iteracji.

Jeżeli

to

wymnażasz pamiętając że i wyciągasz i .

Dzięki wielkie. Prędkość wyznaczania znacznie wzrosła. Na koniec (ktoś może kiedyś będzie szukać czegoś podobnego) napiszę w skrócie o zmianach.

 for (int i = 0; i < img.Height; i++)
            {
                for (int r = 0; r < img.Width; r++)
                {
                    coordinate = converter.ConvertToPlainPoint(area, imgSize, r, i);
                    if (Contains(coordinate.X,coordinate.Y, iteration))
                    {
                        editor.SetPixel(r, i, ColorPalette.GetColor(iteration));
                    }
                }
            }

Tak jak pisał Marek.

Wywaliłem klasę ComplexNumber a w klasie MandelbrotSet zrobiłem (prawdopodobnie ? ) tak jak Azarien napisał czyli :

   if((x*x) + (y*y) >= 4)
                    return false;
                double X;
                X = (x*x) - (y*y) + realPart;
                double Y = (2*(x*y))+imaginaryPart;
                x=X;
                y=Y;

Średnia szybkość wyznaczania

Mam dość starego kompa i może mi trochę mulić, ale na nowszych maszynach powinno być trochę lepiej.

Tutaj programik w fazie testowej (można powiększać a w razie za małej dokładności wyrenderować jeszcze raz z inną dokładnością)

http://www.filedropper.com/astrocytorigin

Dzięki za pomoc
Pozdrawiam
Astrocyt