Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Mandelbrot-Menge - Kann mir wer den Code erklären?


Palladin007 - Di 30.08.16 21:33
Titel: Mandelbrot-Menge - Kann mir wer den Code erklären?
'n Abend,

ich wollte mir auch mal die Fraktale anschauen und zeichen lassen und hab mit der Mandelbrot-Menge angefangen.
Dafür hab ich mir ein Beispiel-Projekt raus gesucht, was das tut, auf WPF portiert und dann den eigentlichen Kern heraus kristalisiert und so umgeschrieben, dass ich damit arbeiten kann.
Am Ende hab ich jetzt eine Methode, die alle Koordinaten durch geht und für jede Koordinate eine Action aufruft.
In dieser Action bekomme ich dann die Position im Control in Pixeln und die Koordinaten.

Die Koordinaten übergebe ich dieser Methode um die Farbe, die an der Position gesetzt werden soll, zu bekommen:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
private Drawing.Color GetMandelColor(Drawing.PointF coordinates)
{
    double x = 0, y = 0;
    int colorId = 0;
            
    while (colorId < _colors.Length - 1 && Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2)) < 2)
    {                
        var newX = Math.Pow(x, 2) - Math.Pow(y, 2) + coordinates.X;
        var newY = x * y * 2 + coordinates.Y;

        x = newX;
        y = newY;

        colorId++;
    }

    return _colors[colorId];
}


Die Colors bekomme ich aus einem Farb-Set mit 256 Farben, was bei dem Beispiel-Projekt dabei war.
Ich habe explizit Math.Pow verwendet, weil es in meinen Augen dann besser erkennbar ist, dass da das Quadrat berechnet wird.

Ich hab mich dazu mal hier [https://www.informatik.uni-leipzig.de/~meiler/Schuelerseiten.dir/DPlotzki/html/mndlbrt.htm] belesen.
Die Iteration ist jetzt auch nicht so kompliziert, zumindest nicht, wenn ich eine anständige Programmiersprache zum berechnen habe.

Aber so wie ich das verstanden habe, wird die Berechnung für jede Koordinate einzeln durchgeführt?
Das spiegelt sich aber überhaupt nicht in dem Code-Schnippsel wieder

Kann mir das jemand erklären?
Vielleicht hat ja unser hauseigener Mathematiker Lust? :)

Wenn ich das Konzept verstanden habe, möchte ich den eigentlichen reinen "Formel-Teil" in eine eigene Methode legen, in der Hoffnung, dass ich die eigentliche Berechnung dann z.B. als User-Eingabe in Form einer Formel ermöglichen kann, sodass bei dem Programm theoretisch jede beliebige Fraktal-Formel eingetragen werden kann.


Besten Dank :)


Mathematiker - Di 30.08.16 22:01

Hallo,
gleich vornweg, mit C# kenne ich mich nicht aus. Daher kann ich nur eine Delphi-Routine erläutern.

Für jeden Punkt der komplexen Gaußschen Zahlenebene musst du die Berechnung einzeln ausführen. In meinem Beispiel läuft der Realteil der Zeichenebene von -2.5 bis 2.5, der Imaginärteil von -2.5i bis 2.5i, d.h. jeweils Intervallbreiten von 5.


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
procedure mandelbrotmenge;
var i,j,anz,b,h:integer; 
    x,y,cx,cy,xneu,yneu:double;
begin
  b:=paintbox1.width; 
  h:=paintbox1.height;
  
  for i:=1 to b do begin
   for j:=1 to h do begin
     cx:=5*i/b-2.5;          //Transformation des Pixels in komplexe Zahl
     cy:=5*j/h-2.5
     x:=0; y:=0
     anz:=0;
     repeat
       xneu:=x*x-y*y+cx;     //klassisches Apfelmännchen 
       yneu:=2*x*y+cy; 
       x:=xneu; 
       y:=yneu; 
       inc(anz);
     until (x*x+y*y>4or    //bei Betrag der komplexen Zahl >=2 ist die Divergenz der Folge sicher
           (anz>100);        //Genauigkeit der Berechnung
     paintbox1.canvas.pixels[i,j]:=rgb(2*anz, 2*anz, 2*anz);   //keine schöne Farbwahl
  end end;
end;

Die Berechnung breche ich ab, wenn entweder Divergenz sicher ist, d.h. x²+y²>4 ist (keine Wurzel!), oder die Konvergenz "wahrscheinlich" ist. Hier nehme ich 100 Iterationen; für eine exaktere Darstellung entsprechend mehr.

Für eine allgemeine Routine, d.h. mit beliebigen komplexen Funktionen und nicht nur z²+c, wirst du wohl einen Parser für komplexe Funktionen brauchen und damit die komplexe Zahl xneu + i yneu berechnen.
Ich hoffe, dass ich deine Frage richtig verstanden habe.

Beste Grüße
Mathematiker

Nachtrag: Ich hänge den Parser für komplexe Funktionen (Delphi!) mal an. Der Code ist "exotisch", da ein paar Teile aus verschiedenen Quellen zusammengestückelt wurde.
Ich verwende die Routine in http://www.entwickler-ecke.de/viewtopic.php?t=109773&start=0&postorder=asc&highlight=phasenplot .


FinnO - Di 30.08.16 22:06

Moin,

da beginnt man gerade, eine Antwort zu schreiben, da ist der Mathematiker schneller. Mein Wrap-Up des Mandelbrot-Algorithmus:


Quelltext
1:
2:
3:
4:
5:
6:
Für jeden Pixel in deinem Bild:
  Transfomiere den Pixel in eine Komplexe Zahl z
        z = z^2 + z;
  Zähle nach wie vielen Iterationen z noch in der Mandelbrotmenge enthalten ist. 
            Oder breche ab wenn Anzahl der Iterationen > Konstante
  Färbe den Pixel entsprechend der Anzahl der Iterationen.


Und (fast genau so lang) in JavaScript hier [http://jsfiddle.net/12mc9gff/1/].

Gruß
Finn


gerd8888 - Di 30.08.16 22:23

Ich kenne dieses Beispiel auch. Es steht z.B. im Buch von Henning Mittelbach (Programmierkurs Turbo Pascal), die guten alten Bücher.
Benoit Mandelbrot (1924 - 2010)


Palladin007 - Di 30.08.16 22:26

Die Konstante (bei mir 2) ist also der Grenzwert, ab dem nicht weiter gerechnet wird, soweit so klar.
Aber woher bekomme ich denn die Konstante?
In meinem Beispiel sind auch noch die folgenden Werte dabei:
Zitat:
xMin = -2.1
yMin = -1.3
xMax = 1
yMax = 1.3

Also die jeweiligen Minimum/Maximum-Werte jeder Achse.
Da weiß ich auch nicht, woher die kommen. Sie scheinen die jeweiligen Maximum/Minimum-Werte, die es in der Mandelbrot-Menge gibt, einzugrenzen, sodass das Koordinatensystem nicht zu groß oder zu klein sind.
Kann es sein, dass ich die Werte berechnen muss, indem ich die ganze Mandelbrot-Berechnung einmal so durch führe und schaue, was die jeweiligen Minimum/Maximum-Werte sind?



Und wie hängt die Berechnung mit der Formel zusammen?
Wie komme ich von der Formel:
Zitat:
Z(n) = Z(n-1)² + C

zu der Berechnung im Code bzw. umgekehrt?

So wie ich die Formel verstanden habe, würde ich die so im Code umsetzen:

C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
private double Mandelbrot(double value)
{
    var result = 0d;

    for (int i = 0; i < 100; i++)
    {
        result = result * result + value;
    }

    return result;
}

Was aber jetzt nicht wirklich das ist, was ich hier habe ...




Die Formel zu parsen, darum kümmere ich mich dann schon, mir geht's rein um das Verständnis ^^
Ich weiß auch nicht, ob ich mit deinem Parser klar komme, Mathematiker, ich kann Delphi zwar halbwegs lesen, aber sobald es komplexer wird, muss ich aussteigen :D
Aber darum kümmere ich mich, wenn es soweit ist, erst einmal möchte ich soweit sein, jede dieser Formeln in eine Methode umsetzen zu können, die mir sagt, ob ein Punkt in der Menge ist oder nicht, denn dann ist das ganze austauschbar und fügt sich nahtlos in den Rest ein.



Edit:

Zitat:
Transfomiere den Pixel in eine Komplexe Zahl z


Wie meinst Du das, FinnO?


FinnO - Di 30.08.16 22:42

user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Die Konstante (bei mir 2) ist also der Grenzwert, ab dem nicht weiter gerechnet wird, soweit so klar.
Und wie hängt die Berechnung mit der Formel zusammen?
Wie komme ich von der Formel:
Zitat:
Z(n) = Z(n-1)² + C

zu der Berechnung im Code bzw. umgekehrt?


Ah, ich erkenne das Problem. Alle Codebeispiele, die bisher vorgebracht wurden, arbeiten nicht mit nativen Datentypen für komplexe Zahlen. Eine Komplexe Zahl z \in \mathbb{C} kann z.B. so aufgeschrieben werden: z = x + y\cdot i mit i = \sqrt{-1}. Man nennt dann x den Realteil und y den Imaginärteil der komplexen Zahl. Demzufolge ist dann das Quadrat der komplexen Zahl z:

z^2 = (x + iy)(x + iy) = x^2 + 2i\cdot x\cdot y + i^2 y^2. Teilt man dieses Ergebnis wieder nach Realteil und Imaginärteil auf, erhält man:
Re{z^2} = x^2 - y^2 und Im{z^2} = 2xy. Durch messerscharfes hingucken lässt sich so die Formel im Code erkennen.


user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Zitat:
Transfomiere den Pixel in eine Komplexe Zahl z


Wie meinst Du das, FinnO?


Die Pixelkoordinaten einer Zeichenfläche sind ja üblicherweise Integer zwischen 0 und der jeweils maximalen Größe der Fläche. Deine Mandelbrotfunktion möchte aber eine komplexe Zahl als Eingabewert. Man muss also eine beliebige Transformation wählen, die die Pixelposition auf eine solche Zahl abbildet, man kann z.B. den Y-Wert des Pixels als Imaginärteil und den X-Wert des Pixels als Realteil verwenden.

user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:

So wie ich die Formel verstanden habe, würde ich die so im Code umsetzen:

C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
private double Mandelbrot(double value)
{
    var result = 0d;

    for (int i = 0; i < 100; i++)
    {
        result = result * result + value;
    }

    return result;
}

Was aber jetzt nicht wirklich das ist, was ich hier habe ...


Der Code würde in C# (minus meine Syntaxfehler, die ich hier beim Blindtippen mache) richtig lauten:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
using System.Numeric;

private int Mandelbrot(Complex<double> value)
{
    var result = value;
    var i = 0;

    while(i < 100 && Complex<double>.Abs(value) < 2)
    {
        result = Complex<double>.Pow(result, 2) + value;
  i++;
    }

    return i;
}


Siehe hierzu auch die Dokumentation von System.Numerics [https://msdn.microsoft.com/en-us/library/system.numerics.complex(v=vs.110).aspx].
Den Rückgabewert dieser Funktion muss man dann auf eine Farbe abbilden.

BG
Finn


Delete - Di 30.08.16 22:44

- Nachträglich durch die Entwickler-Ecke gelöscht -


Palladin007 - Di 30.08.16 23:24

Das mit den komplexen Zahlen hat mir gefehlt, jetzt gibt das auch alles Sinn :D
Danke für den Tipp ^^ (Complex ist nicht generisch :P)

Ich hab in der Zwischenzeit das ganze auch mal auf asynchron umgebaut, lief mit dem vorherigen Code dadurch rund doppelt so schnell.
Mit deiner Variante leicht angepasst (max iterations als Parameter) hab ich dann aber das Problem, dass mir das Ding den ganzen Rechner zum hängen bringt, weil sich das Programm irgendwo aufhängt und dabei konsequent alle Kerne blockiert :D

Ich weiß noch nicht, woran das liegt, kann aber auch an meinen Änderungen liegen.



Bis dahin habe ich aber noch zwei Fragen:

Die Werte (in meinem Beispiel xMin, yMin, xMax und yMax) beschreiben die Grenzen des Koordinatensystems, welcher Bereich dargestellt wird.
Liege ich richtig in der Annahme, dass ich die nicht "einfach" berechnen kann, sondern nur, indem ich ausprobiere, ob die Menge in dem dadurch aufgezeigten Bereich liegt?
Sprich: Ich setze Fix-Werte, rechne das für alle Punkte einmal durch und wenn die Menge größer ist, erhöhe ich entsprechend, bis ich die Minimal/Maximal-Werte habe
Oder gibt es da eine einfachere bzw. schnellere Möglichkeit?

In jedem Code, den ich bisher dazu gesehen habe, wird die Summe aus dem Quadrat der beiden Werte auf > Zahl geprüft.
Bei mir ists die 2, bei Mathematiker ist es die 4.
Woher kommt der Wert? Ist damit der Maximalwert gemeint, der sowohl auf der Y- als auch der X-Achse erlaubt ist? Und wenn ich vorher errechnet habe, dass der X-Wert nicht über 2 sein kann, kann ich in dieser Prüfung getrost auf 2 setzen?




PS:
Ich hab meinen Fehler gefunden.
In der Prüfung, bei Complex.Abs hatte ich den Wert, der als Parameter mitgegeben wurde, nicht der zuvor berechnete Wert.
Jetzt läuft alles wunderbar :)


Mathematiker - Mi 31.08.16 06:57

Hallo,
user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
In jedem Code, den ich bisher dazu gesehen habe, wird die Summe aus dem Quadrat der beiden Werte auf > Zahl geprüft. Bei mir ists die 2, bei Mathematiker ist es die 4.
Woher kommt der Wert? Ist damit der Maximalwert gemeint, der sowohl auf der Y- als auch der X-Achse erlaubt ist? Und wenn ich vorher errechnet habe, dass der X-Wert nicht über 2 sein kann, kann ich in dieser Prüfung getrost auf 2 setzen?

Die Berechnung wird abgebrochen, wenn der Betrag der komplexen Zahl sqrt(x^2+y^2) größer als 2 ist.
Zur Beschleunigung der Berechnung spare ich mir das Wurzelziehen und teste ob x^2+y^2>4. Mehr ist das nicht.
Die 2 ergibt sich aus einem nicht ganz einfachen Beweis, dass beim Erreichen dieses Betrages der komplexen Zahl nur noch Divergenz zu erwarten ist, d.h. die komplexe Zahl wird dem Betrag nach bei jeder weiteren Berechnung größer.

Beste Grüße
Mathematiker


OlafSt - Mi 31.08.16 10:00

Ich nenne das mal eine sehr clevere Methode der Optimierung.

Wie viele hätten versucht, eine noch schnellere Version von SQRT zu basteln und viel Zeit dafür aufgewandt... Anstatt es einfach wegzulassen und mit dem Nicht-Wurzelgezogenen 4 (was ja 2^2 ist) zu arbeiten. Respekt, @Mathematiker.


Th69 - Mi 31.08.16 12:41

Dies ist aber eine altbekannte Optimierung. Hat man z.B. auch beim Ermitteln, ob zwei Punkte einen bestimmten Radius unter- bzw. überschreiten:

Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
// in Pseudocode

// statt
IF (SQRT((x1-x2)^2 + (y1-y2)^2) < R)

// dann
IF ((x1-x2)^2 + (y1-y2)^2 < R^2)
// bzw.
IF ((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) < R*R)


Palladin007 - Mi 31.08.16 12:45

Ok, dann nehme ich die Wurzel bei mir auch mal raus :D
Braucht auch noch zu lange, für meinen Geschmack, mal schauen, wo ich da optimieren kann. Ich will ja nicht bis zur Darstellung warten müssen


Zitat:
Die 2 ergibt sich aus einem nicht ganz einfachen Beweis, dass beim Erreichen dieses Betrages der komplexen Zahl nur noch Divergenz zu erwarten ist

Lohnt es sich, das zu berechnen?
Ich möchte ja auch andere Formeln darstellen können, ändert sich dieser Wert denn nich auch mit der Formel?


Palladin007 - Mi 31.08.16 14:52

So, die Berechnung dauert bei mir jetzt unter 200ms, vorher über 5 Sekunden.
Der Flaschenhals war das SetPixel von Bitmap, das mache ich jetzt manuell byte für byte im unsafe-Code. Dazu noch komplett parallel.
Außerdem macht der Complex-Typ das recht langsam. Ich hab es jetzt auf die manuelle Berechnung und ohne Math-Klasse reduziert.


Allerdings habe ich jetzt immer noch das Problem: Wenn ich sehr weit ran zoome, dann wird irgendwann nicht weiter berechnet, das sieht dann nur noch sch**** aus.
Kann das daran liegen, dass ich mit double arbeite? Ich hab testweise mal decimal genommen, allerdings dauert jetzt jede Berechnung über 12 Sekunden, das geht garnicht...


PS:
Wenn wer den Code haben will, einfach Bescheid sagen.
Ist aber unkommentiert und C#, Delphi-Leute werden es also nicht ganz so einfach haben :P


Mathematiker - Mi 31.08.16 15:59

Hallo,
user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Wenn ich sehr weit ran zoome, dann wird irgendwann nicht weiter berechnet, das sieht dann nur noch sch**** aus.
Kann das daran liegen, dass ich mit double arbeite?

Double sollte i.A. genügen. Allerdings musst du für kleinere Intervalle die maximale Anzahl von Iterationen erhöhen. Bei hohen Vergrößerungen nutze ich 5000 Iterationen. Das dauert zwar länger, aber die Berechnung wird exakter.
Übrigens ist bei meiner Mandelbrotlösung (http://mathematikalpha.de Teilprogramm Chaostheorie/Mandelbrotmenge, Juliamenge) eine maximale Vergrößerung von 1 : 60 Billionen möglich. Dann genügt die Genauigkeit von double nicht mehr.

user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Zitat:
Die 2 ergibt sich aus einem nicht ganz einfachen Beweis, dass beim Erreichen dieses Betrages der komplexen Zahl nur noch Divergenz zu erwarten ist
Ich möchte ja auch andere Formeln darstellen können, ändert sich dieser Wert denn nich auch mit der Formel?

Ja, leider. Die Abbruchbedingung ist vom Fraktaltyp abhängig. Ich kenne keine Möglichkeit, wie man diese Grenze ermittelt. Daher nutze ich meist die 2 und es funktioniert ganz gut.

Beste Grüße
Mathematiker


Palladin007 - Mi 31.08.16 19:40

Ich hab mir jetzt mal dein Programm herunter geladen und ausprobiert.
Da ich bei mir das Problem hatte, dass das Bild ziemlich unschön aussieht, wenn ich sehr weit rein zoome, hab ich das bei deiner Variante auch mal ausprobiert.
Im Dateianhang gibts einen Screenshot davon

Es verzerrt sich auch
Wenn ich näher ran gehe, verstärkt sich der Effekt nur noch.


Erwarte ich da zu viel von der Mandelbrot-Menge? Ist das so nahe, dass es da diese Muster einfach nicht mehr gibt?
Oder liegt das an was Anderem?


PS:
Und wie schaffst Du es, dass es bei 10k Iterationen trotzdem nach relativ schnell geht? :D
Laut der Anzeige rechts oben nur 3 Sekunden


Palladin007 - Mi 31.08.16 20:01

Oder ist das die Ungenauigkeit von double bzw. dem Typ, den Du verwendest?

Ich hab bei mir ein Check eingebaut, der prüft, dass MinX kleiner als MaxX sein muss.
Mit dem Check kann ich gar nicht so nahe heran gehen, da die Werte vorher schon als Gleich aufgefasst werden.


Mathematiker - Mi 31.08.16 20:02

Hallo,
user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Es verzerrt sich auch. Wenn ich näher ran gehe, verstärkt sich der Effekt nur noch.

Das ist normal und geschieht, wenn x-Intervall und y-Intervall nicht die gleiche Auflösung haben. Dazu habe ich in der Schalterleiste den 7.Schalter "Auflösung anpassen".
Ist das y-Intervall für die Höhe der Ausgabe(Bitmap?) zu klein, im Vergleich zum x-Intervall, wie in dem von dir angehängten Bild, so gibt es diese Verzerrung.

user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
Und wie schaffst Du es, dass es bei 10k Iterationen trotzdem nach relativ schnell geht? :D
Laut der Anzeige rechts oben nur 3 Sekunden

Die Berechnung erfolgt mittels ASM. In Kombination mit scanline, bei dem nur die Farben zeilenweise in einem Bitmap geändert werden und zu gegebener Zeit das Bitmap kopiert wird, wird es dann hinreichend schnell.

Beste Grüße
Mathematiker

Der nachfolgende Delphi-Text funktioniert allein natürlich nicht und ist vielleicht auch nicht besonders schön, aber vielleicht hilft er dir doch ein kleines Bisschen.


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
PROCEDURE PaintApple;
VAR radius,a,b,da,db,xf,yf,invers : double;
          i,it,xs,ys : word;
    rowrgb : pbytearray;
BEGIN
  it :=ein_int(e1);
  da := (_x2-_x1) / breite;
  db := (_y2-_y1) / hoehe;
  radius := 9;
  QueryPerformanceCounter(Time1);
  b := _y2;
  FOR ys:=0 TO hoehe-1 DO BEGIN
    rowrgb:=tempbitmap.scanline[ys];
    b := b - db;
    a := _x1;
    FOR xs:=0 TO breite-1 DO BEGIN
      a := a + da;
      xf:=a;
      yf:=b;
    ASM
         FLD     radius
         FLD     xf
         FLD     yf
         FLD     st
         FMUL    st,st
         FLD     st(2)
         FMUL    st,st
         FLD     st(2)
         FLD     st(4)
         XOR     cx,cx
@itloop: INC     cx
         CMP     cx,it
         JE      @noloop
         FMUL
         FADD    st,st
         FADD    st,st(3)
         FLD     st(1)
         FSUB    st,st(3)
         FADD    st,st(5)
         FST     st(3)
         FMUL    st,st
         FSTP    st(2)
         FLD     st
         FMUL    st,st
         FADD    st,st(2)
         FCOM    st(6)
         FSTSW   ax
         FSUB    st,st(2)
         FXCH    st(3)
         AND     ah,1
         JNZ     @itloop
@noloop: MOV     i, cx
         FINIT
      END;
      if i>=it then begin
        if farbverlauf then i:=(round(100.0*modus*(sqr(a)+sqr(b)))) mod 256
                       else i:=0
      end
      else i:=(modus*i) mod 256;
      farbfeld[xs,ys]:=i;
      rowrgb[3*xs]:=pal[i].b;
      rowrgb[3*xs+1]:=pal[i].g;
      rowrgb[3*xs+2]:=pal[i].r;
    END;
    QueryPerformanceCounter(Time2);
    if time2-time1>abbruchtime then begin
      application.processmessages;
      if abbruch then exit;
      PB1.canvas.draw(0,0,tempbitmap);
      time1:=time2;
    end;
  END;
  PB1.canvas.draw(0,0,tempbitmap);
END;


Delphi-Laie - Mi 31.08.16 22:53

user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
Ich nenne das mal eine sehr clevere Methode der Optimierung.

Wie viele hätten versucht, eine noch schnellere Version von SQRT zu basteln und viel Zeit dafür aufgewandt... Anstatt es einfach wegzulassen und mit dem Nicht-Wurzelgezogenen 4 (was ja 2^2 ist) zu arbeiten.


Derlei Banalitäten sollten eigentlich jedem intellektuell flexiblen (!!) Abiturienten einfallen. Stichwort: (Un-)Gleichungsbehandlung, (Un-)Gleichungstransformation in Richtung Vereinfachung. Dazu muß (müßte) man "nur" simples mathematisches Rüstzeug anwendungsbereit in einem anderen Fach anwenden.


mandras - Sa 03.09.16 00:41

Falls Interesse besteht, kann ich einen alten Text von mir einmal neu formatieren und hier einstellen.
Dort hatte ich ein paar Erklärungen zum einfachen Apfelmännchen geschrieben incl.
Vergleich der Geschwindigkeit auf verschiedenen Rechnern, mit verschiedenen Sprachen (Delphi, Fortran u.a.)
und auch zusätzliche Optimierungsmöglichkeiten (Kreis/Zykloidentest).
Sind so ca. 8-9 Seiten, Alter: Alt. Südhang, eher süffig. Aus meiner Dozentenzeit (also - ich denke so 15 Jahre her)


Mathematiker - Sa 03.09.16 07:47

user profile iconmandras hat folgendes geschrieben Zum zitierten Posting springen:
Falls Interesse besteht, kann ich einen alten Text von mir einmal neu formatieren und hier einstellen.

Danke für das Angebot.
Ich persönlich habe immer Interesse an Texten zu mathematisch-chaostheoretischen Sachen.

Beste Grüße
Mathematiker


mandras - Sa 03.09.16 21:42

Ich habe die Ausführungen ohne weitere Änderungen als PDF gespeichert.
Ist wie gesagt schon ein paar Jährchen alt.


Delphi-Laie - Sa 03.09.16 23:09

Tja, vor vielen Jahren - es muß zum Ende der DDR-Zeit gewesen sein - fand ich irgendwo (Computerzeitschrift?) mal ein Beispielprogramm für Fraktale auf der Basis hyperkomplexer Zahlen (vermutlich Quaternionen). Das mußte ich unbedingt haben - für später zum Ausprobieren. Die Kopiertechnik Anfang der 90er (aus der Zeit müßte die Kopie stammen, mir liegt jedenfalls keine Kopie vor, wie ich sie noch aus DDR-Zeiten kannte - da roch das Kopierpapier anfangs immer so gewöhnungsbedürftig) war leider noch nicht so berauschend. Folge war, daß ich das Programm später, als ich selbst einen Computer hatte, leider nicht genau abtippen konnte, ich versuchte es wiederholt, war aber nichts zu machen.

Ich kann mich jedenfalls noch lebhaft daran erinnern, daß die in der Zeitschrift gezeigten Fraktalbilder von atemberaubender Schönheit waren. Da kann das Apfelmännchen, so faszinierend es in seiner ersten Begegnung ist (zugegeben erst mit den Vergrößerungen, zuerst kommt es nur als ausgefranste Kardioide daher) mit seinen "simplen" komplexen Zahlen leider nimmer mithalten.

Schade drum...sonst wäre es wohl auch hier.


Palladin007 - So 04.09.16 14:35

Hallo mandras und danke für den Text. Ich schau mir das in einer ruhigen Stunde mal an.


Bis dahin hab ich aber eine Bitte an Mathematiker:
Kannst Du mir deinen Assembly-Code-Schnipsel erklären? :D
Ich hab so meine Schwierigkeiten, da durch zu blicken :/
Bisher kenne ich nur CIL und das ist dann doch etwas anders

Oder zumindest, was Du dort anders gemacht hast, was nur auf Assembly-Ebene geht.
Ich möchte das in CIL nachbauen, dafür muss ich das aber verstehen.


Mathematiker - So 04.09.16 19:34

Hallo,
anbei der ASM-Text mit Erklärung

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
      ASM
         FLD     radius    { 9        }
         FLD     a         { cx       9 }
         FLD     b         { cy       cx    9     }
         FLD     st        { y        cy    cx    9    }
         FMUL    st,st     { y²       cy    cx    9    }
         FLD     st(2)     { x        y²    cy    cx    9     }
         FMUL    st,st     { x²       y²    cy    cx    9     }
         FLD     st(2)     { y        x²    y²    cy    cx    9     }
         FLD     st(4)     { x        y     x²    y²    cy    cx    9   }

         XOR     cx,cx
@itloop: INC     cx        // CX ist der Iterationszähler
         CMP     cx,it     // überschreitet CX den Wert it,
         JE      @noloop   // dann keinen Bildpunkt setzen.

         { y = 2xy + cy }
         FMUL              { xy       x²    y²    cy    cx    9     }
         FADD    st,st     { 2xy      x²    y²    cy    cx    9     }
         FADD    st,st(3)  { (y)      x²    y²    cy    cx    9     }
         { x = x² - y² + cx }
         FLD     st(1)     { x²       (y)   x²    y²    cy    cx    9     }
         FSUB    st,st(3)  { x²-y²    (y)   x²    y²    cy    cx    9     }
         FADD    st,st(5)  { (x)      (y)   x²    y²    cy    cx    9     }
         { x² = x*x }
         FST     st(3)     { (x)      (y)   x²    (x)   cy    cx    9     }
         FMUL    st,st     { (x²)     (y)   x²    (x)   cy    cx    9     }
         FSTP    st(2)     { (y)      (x²)  (x)   cy    cx    9     }
         { y² = y*y }
         FLD     st        { (y)      (y)   (x²)  (x)   cy    cx    9     }
         FMUL    st,st     { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         { x² + y² < 9 ??? }
         FADD    st,st(2)  { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FCOM    st(6)     { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FSTSW   ax
         FSUB    st,st(2)  { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         FXCH    st(3)     { (x)      (y)   (x²)  (y²)  cy    cx    9     }
         AND     ah,1
         JNZ     @itloop   { falls Folge innerhalb des Kreises, dann weiter }
@noloop: MOV     i, cx
         FINIT
      END;


Beste Grüße
Mathematiker


Palladin007 - So 04.09.16 22:41

Tut mir Leid, wenn ich mich so blöd anstelle, aber ich versteh deine Beschreibung mit den geschweiften Klammern nicht :D

Vielleicht hilfts ja, wenn ich die Befehle verstehe.

FLD - Ich dachte, dass das ein Feld lädt/setzt, aber was passiert dann z.B. bei Zeile 7?
FMUL - Multiplikation der beiden angegebenen Felder
XOR - Exclusive Or, aber warum dann zwei mal das gleiche Feld?
INC - Um eins erhöhen
CMP - Vergleicht zwei Werte (und legt das Ergebnis -1/0/1 auf den Stapel?)
JE - Springt zu einer Stelle im Code
FADD - Addiert die Werte - Aber auch hier die Frage: Was bedeutet die Zahl in den Klammern?
FSUB - Subtrahiert die Werte

Und bei dem Rest steig ich aus :D


Kennst Du eine gute Liste, wo die ganzen Befehle aufgeführt sind?
Ich hab keine gefunden :/


Mathematiker - Mo 05.09.16 08:34

Hallo,
user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
versteh deine Beschreibung mit den geschweiften Klammern nicht :D

In den Klammern steht die jeweilige Belegung des Stacks nach(!) der Operation.
FLD transportiert den jeweiligen Wert auf den Stack. Alle Rechenoperationen werden hier mit Werten auf dem Stack durchgeführt.

Es ist zwar lustig, den meine ASM-Kenntnisse sind auch nur rudimentär, aber ich versuche eine Erklärung. Sollte irgendetwas nicht exakt sein, bitte nicht "schlagen". :mrgreen:


Delphi-Quelltext
1:
2:
3:
         FLD     radius    { 9        }
         FLD     a         { cx       9 }
         FLD     b         { cy       cx    9     }
Laden der Abbruchbedingung (hier 9 (nicht wie sonst 4, warum eigentlich, im Moment weiß ich es selbst nicht mehr) und Real- cx und Imaginärteil cy der Konstanten auf den Stack


Delphi-Quelltext
1:
         FLD     st        { y        cy    cx    9    }                    
Holt den Stackwert cy und legt ihn zusätzlich als Variable y auf den Stack


Delphi-Quelltext
1:
         FMUL    st,st     { y²       cy    cx    9    }                    
Der obere Stackwert wird quadriert


Delphi-Quelltext
1:
         FLD     st(2)     { x        y²    cy    cx    9     }                    
Der obere Stackeintrag ist st(0), d.h. mit st(2) wird cx, der dritte Wert im Stack, geladen und zusätzlich als x oben auf den Stack gelegt


Delphi-Quelltext
1:
         FMUL    st,st     { x²       y²    cy    cx    9     }                    
x² wird berechnet


Delphi-Quelltext
1:
2:
         FLD     st(2)     { y        x²    y²    cy    cx    9     }
         FLD     st(4)     { x        y     x²    y²    cy    cx    9   }
die Größen für y und x werden nochmals auf den Stack kopiert


Delphi-Quelltext
1:
         XOR     cx,cx                    
der Iterationszähler (CX-Register) cx soll garantiert 0 sei, mit XOR wird cx 0, gleichgültig was vorher in cx steht


Delphi-Quelltext
1:
2:
3:
@itloop: INC     cx        // CX ist der Iterationszähler
         CMP     cx,it     // überschreitet CX den Wert it,
         JE      @noloop   // dann keinen Bildpunkt setzen.
CMP prüft, ob der Registerinhalt CX größer wird als die maximale Iterationszahl it. Wenn ja, wird zum Ende der ASM-Routine gesprungen


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
         { y = 2xy + cy }
         FMUL              { xy       x²    y²    cy    cx    9     }
         FADD    st,st     { 2xy      x²    y²    cy    cx    9     }
         FADD    st,st(3)  { (y)      x²    y²    cy    cx    9     }
         { x = x² - y² + cx }
         FLD     st(1)     { x²       (y)   x²    y²    cy    cx    9     }
         FSUB    st,st(3)  { x²-y²    (y)   x²    y²    cy    cx    9     }
         FADD    st,st(5)  { (x)      (y)   x²    y²    cy    cx    9     }
         { x² = x*x }
         FST     st(3)     { (x)      (y)   x²    (x)   cy    cx    9     }
         FMUL    st,st     { (x²)     (y)   x²    (x)   cy    cx    9     }
         FSTP    st(2)     { (y)      (x²)  (x)   cy    cx    9     }
         { y² = y*y }
         FLD     st        { (y)      (y)   (x²)  (x)   cy    cx    9     }
         FMUL    st,st     { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         { x² + y² < 9 ??? }
         FADD    st,st(2)  { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FCOM    st(6)     { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FSTSW   ax
         FSUB    st,st(2)  { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         FXCH    st(3)     { (x)      (y)   (x²)  (y²)  cy    cx    9     }
         AND     ah,1
         JNZ     @itloop   { falls Folge innerhalb des Kreises, dann weiter }
Die ganzen Befehle berechnen "kryptisch" die neuen Werte (x)=x²-y²+cx und (y)=2xy+cy und die Abbruchbedingung x²+y² durch ständiges Holen und Ablegen von Werten auf dem Stack.

FCOM führt einen Vergleich durch (https://courses.engr.illinois.edu/ece390/archive/spr2002/books/labmanual/inst-ref-fcom.html, unter dieser Adresse gibt es eine lange Liste von ASM-Befehlen mit Beschreibung), FSTP kopiert auf dem Stack (http://x86.renejeschke.de/html/file_module_x86_id_117.html), FSTSW siehe http://x86.renejeschke.de/html/file_module_x86_id_120.html und FXCH tauscht Werte (http://x86.renejeschke.de/html/file_module_x86_id_126.html).


Delphi-Quelltext
1:
2:
3:
@noloop: MOV     i, cx
         FINIT
      END;
Austritt aus der Berechnung mit Kopieren der Anzahl von Iterationen cx in die Variable i.

Ich vermute, meine "Erklärung" hilft nicht so richtig weiter. Aber, wie gesagt, meine ASM-Kenntnisse sind nicht gerade berauschend.
Ich denke, hier müssen die Profis 'ran. Wahrscheinlich können sie es besser erklären.

Beste Grüße
Mathematiker


Palladin007 - Mo 05.09.16 09:07

Kann es sein, dass es schnellerläuft, weil Du komplett auf dem Stack arbeitest?
Du baust im Prinzip darauf, dass der Stack im Cache landet, was ja deutlich schneller ist als der "langsame" RAM.
Du hast nämlich kaum die eigenen Variablen vom Code darüber verwendet, stattdessen arbeitest Du nur auf dem Stack, was ich eher umständlich finde. Wenn der Stack auf dem Cache landet, wäre das aber ein deutlicher Vorteil.

Den ersten Teil hab ich denke ich kapiert, bei dem zweiten Teil hab ich noch so meine Probleme :D
Aber ich schau mir mal die ASM-Befehls-Liste an, vielleicht hilft das weiter.


Eine Frage, die mir aber immer wieder kommt:

Delphi-Quelltext
1:
2:
FLD     st        { y        cy    cx    9    }
FMUL    st,st     { y²       cy    cx    9    }

Entfernt FMUL (und auch andere) den letzten Stack-Wert vom Stack, bevor es sein Ergebnis drauf legt?
So sieht das nämlich auch an anderer STelle aus und da frage ich mich: Warum? Ist das nicht langsamer, weil eine zusätzliche Operation ausgeführt wird?
Bei IL wird (wenn ich mich nicht irre) einfach nur weiter gestapelt.



PS:
Und danke für die viele Mühe :)


OlafSt - Mo 05.09.16 09:44

Nein, Freunde. Alle auf dem Holzweg.

Der gezeigte Assemblercode ist 80x87-Code, also Assemblercode für den mathematischen Coprozessor von Intel, der seit dem 80486 (abgesehen vom 80486SX, wo die FPU abgeschaltet wurde) fest in die Standard-CPU integriert ist. Davor mußte die FPU, wie man das Ding heute nennt, extra dazugekauft werden, hatte folglich einen Extra-Sockel (der dann meistens aus Kostengründen weggelassen wurde) und schweineteuer war. So kostete der 8086 damals 400DM, der passende 8087 dazu fast 2000DM. Dafür waren Fließkommaberechnungen aber auch Faktor 200 schneller. Dies brachte die Apfelmännchenberechnung von knapp 24 Stunden auf etwa 30 Minuten Rechenzeit herunter.

Der 8087 arbeitet Stack-orientiert und nicht, wie die normalen 80x86-CPUs, registerorientiert. Ergo muß man die Werte, mit denen man rechnen will, erstmal auf den FPU-Stack pushen (der nichts mit dem normalen Stack zu tun hat), was mit FLD (Floating Point Load) passiert. Alle anderen Operationen in der FPU arbeiten mit dem Top-Of-Stack-Wert, der grundsätzlich als "ST" bezeichnet wird. Damit man auch andere Stack-Werte ansprechen kann, gibt es auch ST(1), ST(2) etcpp. IIRC hat der FPU-Stack 8 Plätze.

Ergo wird ein FMUL ST,ST den Top-Of-Stack-Wert mit dem Top-Of-Stack-Wert multiplizieren - was dem quadrieren entspricht. Der Rest ist in der Befehlsreferenz zum 8087 nachlesbar. Ansonsten hat man sich da an die Intel-Konvention gehalten: Das F steht als Kennzeichen für FPU immer vor dem eigentlichen Mnemonic, als erstes wird das Ziel der Operation genannt.

Die meisten FPU-Befehle haben einen "Partner", der mit einem abschließenden "P" gekennzeichnet ist (FMUL und FMULP z.B.). Dieses P steht für "Pop" und zieht den obersten Wert vom FPU-Stack herunter. Somit würde ein

FLD 9
FMUL ST,ST

zwar die 9 quadrieren, auf dem FPU-Stack läge aber nun die 81, gefolgt von der 9. Mit

FLD 9
FMULP ST,ST

wird die 9 auch quadriert, aber vor Ablage des Ergebnisses vom FPU-Stack genommen. Ergo liegt dort nur noch die 81.


Mathematiker - Mo 05.09.16 09:58

Hallo OlafSt,
Danke für die ausführliche Erklärung.
Ich nutze diese ASM-Routine seit vielen, vielen Jahren (mindestens seit 2000) und habe nie richtig verstanden, was da eigentlich geschieht; und mir auch keine große Gedanken gemacht. :autsch:

Interessant wäre für mich nun, wie eine für die 80x86-CPUs optimierte Routine aussehen würde. Könnte man da noch einmal etwas Geschwindigkeit herausholen?
Bei der Berechnung von Mandelbrotmengen wäre dies sicher interessant.

Beste Grüße
Mathematiker


Palladin007 - Mo 05.09.16 10:57

Auch von mir ein Danke :)

Das erklärt auch, warum ich so wenig über die Befehle gefunden habe :D



Aber dennoch ist die Berechnung bei Mathematikers Programm deutlich schneller als bei mir.
Allerdings hab ich bei mir alles mir bekannte optimiert, was ich optimieren konnte, die Berechnung bei max. 100 Durchläufen und Vollbild dauert ja auch "nur" 100ms.


OlafSt - Mo 05.09.16 13:13

IMHO ist in Sachen Fließkommaberechnung die FPU noch immer das Maß der Dinge. Keine noch so schnelle x86-Routine kann so schnell multiplizieren wie ein FMUL der FPU. Das liegt einfach daran, das die x86-CPUs reine Integer-ALUs haben, die ganzen Fließkommaoperationen also manuell nachbilden müßten. Dies kann unmöglich schneller sein als eine FPU-Operation, die direkt "in Transistoren gebaut" ist.

Was aber schneller sein könnte, wäre eine optimiertere Version der schon bestehenden Routine. Wenn ich daran denke, das man mit SSE4-Befehlen heutzutage 4 Doubles auf einen Schlag miteinander multiplizieren kann... Dies wurde bedeuten, das hier mit einem Befehl 4 Pixels des Apfelmännchens zugleich berechnet. Dies allein wäre ja ein Faktor 4 schneller, dann kommt ja noch die extrem verbesserte Implementierung der SSE-Befehle hinzu. Da ließe sich also sicher noch ordentlich Luft rausquetschen - erfordert dann aber auch eine SSE4-taugliche CPU (Core2 Duo und aufwärts, wenn ich das recht im Kopf habe).

Fragt mich nicht, wie so was aussehen würde - ich bin zu lange aus der Materie raus ;)

Ach ja: Noch mehr Speed kann man rausholen, wenn man die Grafikkarte den ganzen Kram berechnen läßt (CUDA ist das Zauberwort). Die Grafikchips sind nochmal einige dutzen mal schneller als die Intel-FPUs, weil sie eben extrem spezialisiert sind. Dafür kann auf einem Radeon X9 leider kein Windows laufen ;)

[Edit]

ich habe mal etwas geforscht. hier [http://www.codeproject.com/Articles/12350/Generating-Fractals-with-SSE-SSE] findet sich ein Programm mit SSE/SSE2-Instruktionen, das ein Apfelmännchen berechnet. 1024x768, 256 Iterationen, 30ms. Auf einem Pentium IV, der schon 8 CPU-Generationen zurück ist ;)

Der Autor zeigt auch sehr eindrücklich, wie extrem kompliziert Assemblerprogrammierung schon damals war, wenn man es wirklich schnell haben wollte. Da mußte man das Pipelining und die Caches beachten, damit möglichst viele Operationen nebeneinander verarbeitet werden konnten. Heute wäre das nochmal einige Nummern komplexer, weil man ja nun mehrere CPU-Kerne hat, die jeder für sich mehrere Instruktionen parallel laufen lassen können und diese in ihren Pipelines quasi nebeneinander verarbeiten...

Wäre sicher mal spannend, sich 6 Monate Auszeit zu nehmen, und sich da reinzufuchsen... :D Wer will, kann hier [http://www.iquilezles.org/www/articles/sse/sse.htm] einsteigen in die Materie.


Gammatester - Mo 05.09.16 14:00

user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
IMHO ist in Sachen Fließkommaberechnung die FPU noch immer das Maß der Dinge. Keine noch so schnelle x86-Routine kann so schnell multiplizieren wie ein FMUL der FPU. Das liegt einfach daran, das die x86-CPUs reine Integer-ALUs haben, die ganzen Fließkommaoperationen also manuell nachbilden müßten. Dies kann unmöglich schneller sein als eine FPU-Operation, die direkt "in Transistoren gebaut" ist.
Für die Fraktalberechnung als Ganzes muß das Rechnen mit FPU nicht unbedingt schneller sein, früher gab's FRACTINT das nur mit Integer-Rechnungen wesentlich schneller Bilder berechnet (mit Hilfe kluger Heuristiken). Ich habe es schon lange nicht mehr benutzt, aber es scheint noch weiterentwickelt zu werden (siehe http://www.fractint.org/ oder https://de.wikipedia.org/wiki/Fractint).


OlafSt - Mo 05.09.16 19:19

Das mag sein - doch ist dies ein Spezialfall. Ein Spezialfall kann niemals allgemeingültig sein und ich bin fest überzeugt, das FractInt nie und nimmer gegen eine SSE4-Version oder gar CUDA/OpenCL ankäme ;)


Delphi-Laie - Mo 05.09.16 22:30

user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
Heute wäre das nochmal einige Nummern komplexer, weil man ja nun mehrere CPU-Kerne hat, die jeder für sich mehrere Instruktionen parallel laufen lassen können und diese in ihren Pipelines quasi nebeneinander verarbeiten...


Das Zauberwort heißt Multithreadingprogrammierung; das Betriebsprogramm kümmert sich dabei darum, daß alle Prozessoren/Prozessorkerne genug zu tun haben. Solang es aber Ausgaben auf dasselbe Gerät, vorzugsweise Bildschirm, gibt, muß synchronisiert werden, und der "Flaschenhals" ist da.

Für die Assemblerprogrammierung empfehle ich die Bücher des Autors Peter Monadjemi.


jfheins - Mo 05.09.16 22:44

So richtig flott wird es doch erst, wenn du alle 8 Therad der CPU mit SSE (oder AVX) Code fütterst, der in 2 Takten 4 Pixel auf einmal ausrechnet.

Ein Bild ist ja auch sehr einfach parallelisierbar, du zerteilst es einfach in Streifen und gibt jedem Thread einen Teil des Bildes.
Klar, fertig ist es erst, wenn alle Threads fertig sind. Aber wenn das schnell genug läuft, merkt man von der Synchronisierung wenig.

Von Intel gibt es da auch interessante Balkendiagramme: https://software.intel.com/en-us/articles/introduction-to-intel-advanced-vector-extensions#highlighter_339467
Gibt es eigentlich eine Möglichkeit, von AVX/SSE in Delphi Gebrauch zu machen, ohne direkt Assembler benutzen zu müssen?


Palladin007 - Di 06.09.16 03:07

Ich bin auf meinem System jetzt bei ca. 190ms, wenn das Fenster Vollbild geöffnet wird.
Ca. 5ms wären zwar noch drin, aber dadurch wird der Code nur unübersichtlicher, daher hab ich das gelassen.
Maximale Iterationen hab ich auf 100 stehen, auf 1000 braucht's dann rund 1200ms.

Ich hab den Code versucht, so zu kommentieren, damit auch reine Delphi-Jünger damit klar kommen:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
public abstract class Fractal
{
    private static Color[] BlackWhiteColorSet { get; } = new Color[] { Color.Black, Color.White };

    private double _minX, _minY, _maxX, _maxY;
    private Color[] _colorSet;

    // Maße des Koordinatensystems
    public double MinX
    {
        get { return _minX; }
        set { _minX = value; }
    }
    public double MinY
    {
        get { return _minY; }
        set { _minY = value; }
    }
    public double MaxX
    {
        get { return _maxX; }
        set { _maxX = value; }
    }
    public double MaxY
    {
        get { return _maxY; }
        set { _maxY = value; }
    }

    public int MaxIterations { get; set; }
    public Color[] ColorSet
    {
        get { return _colorSet; }
        set
        {
            // Ist value == null, dann wir ein ColorSet mit schwarz/weiß verwendet
            _colorSet = value ?? BlackWhiteColorSet;
        }
    }

    protected Fractal()
    {
        ColorSet = BlackWhiteColorSet;
        MaxIterations = 100;
    }
        
    // zoomt schrittweise in das Koordinatensystem
    public void Zoom(double zoomRate)
    {
        Zoom(ref _minX, ref _maxX, zoomRate);
        Zoom(ref _minY, ref _maxY, zoomRate);
    }
    public void Zoom(double zoomRate, double centerX, double centerY)
    {
        Zoom(ref _minX, ref _maxX, zoomRate, centerX);
        Zoom(ref _minY, ref _maxY, zoomRate, centerY);
    }

    private void Zoom(ref double min, ref double max, double zoomRate)
    {
        Zoom(ref min, ref max, zoomRate, max + (max - min) / 2);
    }
    private void Zoom(ref double min, ref double max, double zoomRate, double center)
    {
        var distanceX = max - min;
        var newDistanceX = distanceX / zoomRate;
        var oldCenter = min + (max - min) / 2;

        min = min + (distanceX - newDistanceX) / 2 + center - oldCenter;
        max = min + newDistanceX;
    }

    public Bitmap DrawBitmap(int width, int height)
    {
        // Stellt im RAM ein Bild dar, auf dem gezeichnet werden kann
        var bitmap = new Bitmap(width, height);

        try
        {
            DrawFractal(bitmap);
        }
        catch
        {
            // Tritt ein Fehler auf, wird das Bild nicht mehr benötigt und frei gegeben werden
            bitmap.Dispose();
            throw;
        }

        return bitmap;
    }
    public unsafe void DrawFractal(Bitmap bitmap)
    {
        var width = bitmap.Width;
        var height = bitmap.Height;

        // Wie viele Pixel gibt es pro Coordinaten-Schritt
        var xSteps = (MaxX - MinX) / width;
        var ySteps = (MaxY - MinY) / height;

        // blockiert die Menge der Pixel von dem Bild im RAM und macht sie über das zurückgegebene Objekt änderbar
        // Dadurch kann ich die Pixel direkt im RAM setzen und manuell optimieren
        var bitmapData = bitmap.LockBits(new Rectangle(00, bitmap.Width, bitmap.Height), ImageLockMode.ReadWrite, bitmap.PixelFormat);

        try
        {
            var pixelFormatSize = Bitmap.GetPixelFormatSize(bitmap.PixelFormat);
            var bytesPerPixel = pixelFormatSize / 8;
            var firstPixelPtr = (byte*)bitmapData.Scan0;
                
            // Parallel.For ist eine for-Schleife, welche die Durchläufe in eigenen Threads ausführt
            // Beginnt bei 0, endet bei (width * height)
            // Der Zähler ist pixelId
            Parallel.For(0, width * height, pixelId =>
            {// begin Parallel.For

                // Da ich durch die gesamte Menge der Pixel zähle, muss die eigentliche Position berechnet werden
                var yPos = pixelId / width;
                var xPos = pixelId - width * yPos;
                    
                var xCoord = xPos * xSteps + MinX;
                var yCoord = yPos * ySteps + MinY;
                    
                var line = firstPixelPtr + yPos * bitmapData.Stride;
                var byteX = xPos * bytesPerPixel;
                var color = CalculateColor(xCoord, yCoord);

                // Farb-Werte setzen:
                // Je nach Pixel-Format ist ein Pixel unterschiedlich groß
                // 32bit - 4 Byte - ARGB
                // 24bit - 3 Byte - RGB
                // 8bit  - 1 Byte - Alle Farbwerte sind gleich
                if (pixelFormatSize == 32)
                {
                    line[byteX] = color.B;
                    line[byteX + 1] = color.G;
                    line[byteX + 2] = color.R;
                    line[byteX + 3] = color.A;
                }
                else if (pixelFormatSize == 24)
                {
                    line[byteX] = color.B;
                    line[byteX + 1] = color.G;
                    line[byteX + 2] = color.R;
                }
                else if (pixelFormatSize == 8)
                    line[byteX] = color.B;

            }); // end Parallel.For
        }
        finally
        {
            // Sicher stellen, dass die Bild-Daten auch bei einer Exception wieder frei gegeben werden
            bitmap.UnlockBits(bitmapData);
        }
    }
    private Color CalculateColor(double xCoord, double yCoord)
    {
        // Berechnung für das Fractal
        var iterations = IterateFractal(xCoord, yCoord);
        // Ein bisschen Prozentrechnung
        var colorIndex = (double)iterations / MaxIterations * (ColorSet.Length - 1);
        return ColorSet[(int)colorIndex];
    }

    protected abstract int IterateFractal(double x, double y);
}


Die Ableitung für die Mandelbrot-Menge:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
public class MandelbrotFractal : Fractal
{
    public MandelbrotFractal()
    {
        // Standart-Werte setzen
        MaxIterations = 100;
        MinX = -2;
        MinY = -1;
        MaxX = 1;
        MaxY = 1;
    }

    protected override int IterateFractal(double x, double y)
    {
        // Die Berechnung
        var xBuffer = x;
        var yBuffer = y;
        var maxIterations = MaxIterations;
        var usedIterations = 0;

        while (usedIterations < maxIterations && xBuffer * xBuffer + yBuffer * yBuffer < 4)
        {
            var newXBuffer = xBuffer * xBuffer - yBuffer * yBuffer + x;
            var newYBuffer = xBuffer * yBuffer * 2 + y;

            yBuffer = newYBuffer;
            xBuffer = newXBuffer;

            usedIterations++;
        }

        return usedIterations;
    }
}


Ich hoffe, das kann man gut lesen und jemand macht sich die Mühe, sich das mal anzuschauen :D


Wirklich zufrieden bin ich mit der Performance noch nicht. 190ms bei Vollbild und max. 100 Iterationen klingt zwar schnell, aber Mathematikers Variante braucht bei maximal 10000 Iterationen nur rund 3 Sekunden, das ist immer noch viel schneller als meine Variante. Auf Assembler-Ebene (bzw. IL) weiß ich nicht, was ich da groß optimieren kann. Ich muss mir Mathematikers ASM-Code nochmal ruhig zu Gemüte führen, damit ich den endlich bis ins Detail verstehe, vielleicht kann ich dann ja doch was raus ziehen.


Was mich auch stört:
Durch die Prozentrechnung beim Bestimmen, welche Farbe verwendet wird, verändert sich die Färbung bei hohen maximalen Iterationen natürlich.
Wenn ich z.B. eine Mischung aus Schwarz und verschiedenen Orange/Rot-Werten nehme (Mathematiker hat das in seinem Programm unter Feuer aufgeführt), dann habe ich bei max. 100 Iterationen ein schönes Bild, bei 1000 aber beinahe komplett schwarz.
Hat jemand eine Idee, wie ich das anpassen kann?


Blup - Di 06.09.16 16:59

Die Multiplikationen beim Vergleich können eingespart werden.

C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
 var xBuffer2 = xBuffer * xBuffer;
 var yBuffer2 = yBuffer * yBuffer;

 while (usedIterations < maxIterations && xBuffer2 + yBuffer2 < 4)
        {
            yBuffer = xBuffer * yBuffer * 2 + y;
            xBuffer = xBuffer2 - yBuffer2 + x;

            usedIterations++;

            xBuffer2 = xBuffer * xBuffer;
            yBuffer2 = yBuffer * yBuffer;
        }

 return usedIterations;


Warum überhaupt Prozentrechnung für das bestimmen der Farbe? Üblicherweise wird der Farbindex aus der Anzahl der Iterationen modulo der Größe der Farbpalette bestimmt.

Moderiert von user profile iconTh69: Code- durch C#-Tags ersetzt


Palladin007 - Di 06.09.16 17:42

Der Vorschlag, das Quadrat nur einmal zu berechnen, bringt kaum eine Verbesserung, vielleicht zwei, drei Millisekunden.
Wenn ich auf max. 1000 Iterationen stelle, kriege ich etwa 50ms raus geschlagen.
Das liegt aber auch daran, dass Du in der Schleife nicht zwischenspeicherst, das hab ich also auch wieder raus genommen.

Wirklich herausragend ist das aber auch noch nicht.
Ich könnte mir auch vorstellen, dass dort garnicht so groß optimiert werden muss, sondern das Abarbeiten der Schleife bzw. das Zeichen vom Bild, allerdings kenne ich da keine Technik, wie ich noch mehr Zeit raus holen kann.

Zitat:
Warum überhaupt Prozentrechnung für das bestimmen der Farbe? Üblicherweise wird der Farbindex aus der Anzahl der Iterationen modulo der Größe der Farbpalette bestimmt.


Das wusste ich nicht. DIe Prozentrechnung hab ich aus einem Beispiel, das ich anfangs nach WPF portiert habe.

Wenn ich so den colorIndex berechne:

C#-Quelltext
1:
colorIndex = iterations % ColorSet.Length;                    

Dann sieht das bei hoher Genauigkeit auch deutlich besser aus bzw. so wie ich es eben erwarte.
Bei niedriger Genauigkeit ist das Weiß aber nicht mehr wirklich weiß. Ich hab mal zwei Bilder angehängt mir Vorher/Nachher.

Modulo ist aber auch ein bisschen schneller, bei max. 1000 Iterationen sind das rund 10ms.


OlafSt - Di 06.09.16 22:01

Blöde Frage: Würde dies hier nicht auch genügen ?


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
protected override int IterateFractal(double x, double y)
    {
        // Die Berechnung
        var xBuffer = x;
        var yBuffer = y;
        var maxIterations = MaxIterations;
        var usedIterations = 0;

        while (usedIterations < maxIterations && xBuffer * xBuffer + yBuffer * yBuffer < 4)
        {
            xBuffer = xBuffer * xBuffer - yBuffer * yBuffer + x;
            yBuffer = xBuffer * yBuffer * 2 + y;

            usedIterations++;
        }

        return usedIterations;
    }


Dann braucht die IL nicht ständig neue Temp-Variablen erstellen, die der GC dann wieder wegräumen muß, außerdem sparen wir uns die ständige Zuweisung an die Buffervariablen, die ansonsten nie mehr benutzt werden...

Weiterhin frage ich mich, ob man mit Math.Pow(xBuffer,2) nicht schneller wäre.


Palladin007 - Di 06.09.16 22:26

Das hab ich schon gemacht, danke

Der Gedanke kam mir auch, als ich den Vorschlag von Blup ausgetestet habe.


jfheins - Mi 07.09.16 00:05

Ich würde dir auch noch empfehlen, großere Arbeitspakete zu schnüren. Wenn du jeden Pixel als einzelnes Arbeitspaket in der Parallel.For Schleife laufen lässt, hast du viel Overhead.
Versuch' doch mal, die Parallel-For Schleife über die Zeilen laufen zu lassen und dann im Rumpf die komplette Zeile zu berechnen.


Palladin007 - Mi 07.09.16 03:39

Das macht keinen Unterschied
Das besste waren 5ms schneller, aber das kann auch eine durch das System bedingte Schwankung sein, das war nämlich auch min. genauso oft langsamer.

Den Grund sehe ich in der Arbeitsweise von Parallel.For
Das nimmt sich nämlich die Anzahl Durchläufe und teilt sie gleichmäßig auf die verfügbare Anzahl Threads (default => Anzahl Kerne) auf.
Habe ich 1000x1000 Pixel, dann führt jeder Thread exakt bei mir (4 logische Kerne) 250k Berechnungen durch.
Hab das in einem anderen Thema hier mal getestet, dass so echt gleichzeitige Abläufe möglich sind, zumindest wenn ich mir pro Berechnung einen Zeitstempel und die ThreadId geben lasse. Für jeden Thread bekomme ich dann die exakt gleichen Zeitstempel.

Probelmatisch wird das erst, wenn die Anzahl der Berechnungen sich nicht durch die Anzahl verfügbarer Threads teilen lässt, dann starte Parallel.For nach der Abarbeitung nämlich neue Threads um den Rest abzuarbeiten und das kostet Zeit. Das passiert (zumindest bei mir) aber nicht, da sich die Anzahl Pixel durch 4 teilen lässt.


Blup - Mi 07.09.16 14:16

user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
Blöde Frage: Würde dies hier nicht auch genügen ?
...

Das Ergebnis sieht vieleicht ähnlich aus. Aber das entspräche aber nicht mehr der orginalen Apfelmänchen-Berechnungsvorschrift, da ein Teil der Berechnung schon mit einem geänderten Wert erfolgt.