Wie kann man den Mandelbrot algorithmus optimieren ?

Dizzy_Ti

Vice Admiral Special
Mitglied seit
11.11.2001
Beiträge
667
Renomée
0
Standort
Düsseldorf
Hi ,
wie kann man den mandebrotalgorithmus optimieren. Ich speicher derzeit alle reelen Zahlen und imaginäre Zahlen und die zufallswert für die R G B Farbe in einem Strukurvektor , damit ich falls gezoomt wird einen schnellen Bildaufbau habe.Nachdem ich alle Koordinaten habe , lass ich alles über eine Schleife unter OpenGL rendern. Dieses Zwischenspeichern kostet kostet aber Zeit.Wie geht das besser?
 
Am besten schreibst du mal deinen Code... oder du hängst dein Hirn irgendwie ans Netz und machst es für uns verfügbar *buck*
 
Code:
void TForm1::ZeichneGrafik()
 {      korr a;
 const char * vendor = glGetString(GL_VENDOR);
 mem->Lines->Add(vendor);
 Randomize();
  wglMakeCurrent(
wglGetCurrentDC(),
wglGetCurrentContext());
// Imaginär und Reele Zahlen
// Die Variable c ist nun eine konstante komplexe Zahl
//und unser z ist ebenfalls komplex
// Bei der Iteration müssen wir mit irgendeinem z anfangen
// und wir fangen am Besten mit z=0 an, z wird quadriert und c addiert
// nach den Regeln von oben. Das Ergbenis setzen wir jetzt als neues z ein
// und machen dieselbe Rechnung usw. usw., eine Iteration eben.

   glMatrixMode(GL_PROJECTION);  // Aktuelle Matrix setztn


    glLoadIdentity();

 glOrtho(-5.5,5.5,5.5,-5.5,-38.0,38.0);
   // glOrtho(0,160,490,0,-38.0,38.0);
 /*void glOrtho(	GLdouble left,
			GLdouble right,
			GLdouble bottom,
			GLdouble top,
			GLdouble zNear,
			GLdouble zFar )

                              */
glClearColor(0.0f,0.0f,0.0f,0.0f);

glClear(GL_COLOR_BUFFER_BIT|
     GL_DEPTH_BUFFER_BIT);
            glEnable(GL_NORMALIZE);
 glEnable(GL_DEPTH_TEST);

 glShadeModel(GL_SMOOTH);
 glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
 glEnable(GL_COLOR_MATERIAL);
 glEnable(GL_LIGHT0);
 glEnable(GL_LIGHTING);
 glEnable(  GL_POINT_SMOOTH);
  glHint(  GL_POINT_SMOOTH_HINT , GL_NICEST );

glDisable(GL_CULL_FACE);
     
     


   double x, y; //  '          Laufvariablen
    double x1, y1, x2, y2; // ' Mandelbrot-Ausschnitts-Koordinaten
     int depth ;         // Berechnungstiefe
      int d;          //     Laufvariable für Tiefe
      double dx, dy ; //         Schrittweite pro Pixel
     double px, py;  //         aktuelle Weltkoordinate
      double u, v;  //           Berechnungsvariablen
      double ax, ay ; //         Berechnungsvariablen
                 double  r[255];
      double g[255];
      double b[255];
      int zahler=0;

      // 255 Zufallsfarben erzeugen
      for ( zahler = 0;zahler<255;zahler++)
      {
     r[zahler]=random(11)/10.0;
      g[zahler]=random(11)/10.0;
      b[zahler]=random(11)/10.0;

      }
     // mem->Lines->SaveToFile("f:\\FARBEN.txt");
      // Ausschnitt der Grafik
      x1 = -2.0 ;
      y1 = -1.6  ;
      x2 = 1  ;
      y2 = 1.6 ;
      depth = 255; // maximal 255 (sonst mehr Zufallsfarben erzeugen!)
      dx = (x2 - x1) /3.5 ;
      dy = (y2 - y1) / 3.5 ;
      // Erzeugung des Bitmap
    for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5

       for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
         {


            px = x1 + x * dx  ;
            py = y1 + y * dy ;
            d = 0 ;
            ax = 0 ;
            ay = 0  ;
            do
             {
               u = ax * ax - ay * ay + px;
               v = 2 * ax * ay + py ;
                 ax = u ;
               ay = v  ;


               d += 1   ;
               a.rr=r[d];
               a.gg=g[d];
               a.bb=b[d];
               a.xx=ax;
               a.ii=v;
               test.push_back(a);


            }
         while ( ((ax * ax + ay * ay )<4) && (d<depth));
            }


      // Fertiges Bitmap darstellen

                              mem->Lines->Add(test.size());
               mem->Lines->Add(test.capacity());

                  if (rg->ItemIndex==0)
                  {
                      glBegin(GL_POINTS);
                }
                if (rg->ItemIndex==1)
                 {     Auswahl=1;
                 glBegin(GL_LINES);
                 }      
               for (int i=0;i<test.size()-1;i++)
                {
                glColor3f(test[i].rr,test[i].gg,test[i].bb);
                glVertex2d(test[i].xx,test[i].ii);
                glColor3f(test[i+1].rr,test[i+1].gg,test[i].bb);
                 glVertex2d(test[i+1].xx,test[i+1].ii);
                 }


                  glEnd();

             

       mem->Lines->Add("Bild wird jetzt dargestellt");

 glFlush();
glFinish();
 SwapBuffers(wglGetCurrentDC());
 
Code:
for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5

       for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
Also, niemals float sondern Integer als Schleifenzähler verwenden. Die Vergleiche von floats sind langsamer als von Integern. Und außerdem sind floats nicht präzise! Somit kannst Du den "<="-Operator vergessen ... der "=="-Fall wird nicht jedesmal auftreten.
Du solltest die float-Berechnungen in den Schleifenrumpf verschieben und die Schleifen mittels Integern kontrollieren. Das müßte schon mal ein wenig mehr Performance geben.

What every computer scientist should know about floating-point arithmetic
 
Zuletzt bearbeitet:
müsste nochmal gucken, irgendwo habe ich noch ne assembler optmierte Version rumliegen, natürlich gerade nix gefunden, ............

MFG
Sir Ulli
 
[edit]
Falls nicht noch ein Mathematiker eine Möglichkeit findet, den Algorithmus von der Logik her zu verbessern, so kannst Du immer noch versuchen, Duff's Device anzuwenden, um die Anzahl der Inkrement- und Vergleichsoperationen der inneren for-Schleife zu verringern. Einfach den Inhalt der inneren for-Schleife in ein Macro packen ... aber auf dem o.a. Link findest Du, wie das geht. Ich habe leider keine Zeit für nähere Erklärungen, falls sie nötig wären.

Viel Erfolg!
[/edit]

Ich habe die Funktion - entsprechend der für mich ersichtlichen Gültigkeitsbereiche der einzelnen Variablen - umgeschrieben. Hoffentlich habe ich mich beim Umwandeln der for-loops nicht verrechnet, was die Anzahl der Durchläufe anbelangt. ;)
Code:
double x, y; //  '          Laufvariablen
double x1, y1, x2, y2; // ' Mandelbrot-Ausschnitts-Koordinaten
double dx, dy ; //         Schrittweite pro Pixel

double  r[255];
double g[255];
double b[255];
int zahler=0;
[color=red]int i, k; [/color] // für die geschachtelten for-Schleifen

// 255 Zufallsfarben erzeugen
for ( zahler = 0;zahler<255;zahler++)
{
	r[zahler]=random(11)/10.0;
	g[zahler]=random(11)/10.0;
	b[zahler]=random(11)/10.0;
}
// mem->Lines->SaveToFile("f:\\FARBEN.txt");
// Ausschnitt der Grafik
x1 = -2.0 ;
y1 = -1.6  ;
x2 = 1  ;
y2 = 1.6 ;

dx = (x2 - x1) / 3.5 ;
dy = (y2 - y1) / 3.5 ;
 
// Erzeugung des Bitmap
for ( i = 0, x = -5.5; i < 1400; ++i, y+=0.01) // falls ich mich nicht verrechnet habe ;)
	for ( k = 0, y = 8.5; k < 1400; ++k, x+=0.01)// dito
   	{
		double px, py;  //         aktuelle Weltkoordinate
		double ax, ay ; //         Berechnungsvariablen
		[color=red]const[/color] int depth = 255 ; // Berechnungstiefe
		int d;          //     Laufvariable für Tiefe
		          	
		ax = 0.0;
		ay = 0.0;
		d = 1; // [color=red]warum mit 0 starten, wenn vorm ersten Benutzen um 1 inkrementiert wird ? [/color]
		
		px = x1 + x * dx  ;
		py = y1 + y * dy ;
		
		do
		{
			double tmp = ax * ax - ay * ay + px;
			ay = 2.0 * ax * ay + py ;
			ax = tmp;
			
			a.rr=r[d]; // [color=red]r[0] [/color] soll niemals verwendet werden?
			a.gg=g[d]; // dito
			a.bb=b[d]; // dito
			a.xx=ax;
			a.ii=ay;
			test.push_back(a);
		}
		while ( ((ax * ax + ay * ay )<4.0) && (d++<depth)); // man beachte [color=red]Postinkrement[/color] von d
	}
 
Zuletzt bearbeitet:
thx das hat mir weitergeholfen.
EDIT:
Du hast dich leicht verechnet. Ich habe eine Variable die Durchläufte mitzählen lassen und da kam 1962801 raus , also wird 981400,5 pro Schleife rauskommen.
EDIT2:
Deine Errechnet Zahl und die Computergemerkte geprüfte Zahl sind beides mal langsamer und führen dazu das der Speicher zu voll wird und dadurch kommt es zu einem bad_alloc.
 
Zuletzt bearbeitet:
Hmmm ... ich wüßte nicht, wieso ich mich verrechnet haben sollte.
5,5+8,5 = 14
14 / 0,01 = 1400

Das bedeutet für mich, die Schleifen laufen jeweils bis 1400.

Aber vielleicht muß ich noch das "<=" berücksichtigen und somit sind es jeweils 1401 Durchläufe. Das würde auch mit Deiner Zählung übereinstimmen, denn 1401^2 = 1962801.

[edit]
Was den Speicherüberlauf anbelangt, so wüßte ich spontan nicht, woran das liegen sollte. Aber ich kenne auch nicht die Funktion "test.push_back(a);".
[/edit]
 
Zuletzt bearbeitet:
Die Methode push_back ist eine Methode für einen Vektoren. Er fügt an die letzte Stelle ein , was man übergeben hat. Bevor er das tut reserviert er sich den Speicher. Ich guck mal ob ich einen Fehler beim mitzählen der gesamten durchgänge gemacht habe.
EDIT:
Wenn ich nur die erste Schleife mitzählen lasse kommt dein Ergebniss raus.
Wenn ich so messe
Code:
 for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5
        
       for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
         {
         merker++;
kommt 1962801 raus.
 
Zuletzt bearbeitet:
Dann ist doch alles bestens. Die ineinander verschachtelten for-Schleifen haben eine Komplexität von O(n^2). 1401^2 = 1962801.

Aber packe den Zähler bitte mal in die do/while-Schleife. Ich möchte gerne wissen, wieviele Male die durchläuft. Die Zahl dieser Durchläufe multipliziere dann mit dem Speicherplatz, den die Structure a (was auch immer das in C++ ist) belegt. Angenommen die do/while-Schleife würde nur 1x pro Durchlauf der inneren for-Schleife ausgeführt werden, so würde der resultierende Vektor schon ca. 75 MB belegen!

[EDIT]
struct a enthält mindestens 5 double Variablen. Somit belegt struct a mindestens 5*8 bytes = 40 bytes, was sich eventuell noch auf 48 durch Alignen des Compilers erhöht.
Aber alleine schon 1962801*40 entsprechen ca. 75 MB. Bei Alignment auf 16bit boundaries wären es sogar ca. 90 MB!
Es ist also kein Wunder, daß es bei Dir zu einem Speicherüberlauf kommt.
[/EDIT]
 
Zuletzt bearbeitet:
naja nach dem Taskmanager kommt nicht 96 Mb raus , sondern 237 *chatt*
Wenn ich alles mit
Code:
--------------------------------------------------------------------------------
 for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5
        
       for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
         {
durchlaufe kommt der Fehler nicht. Eigenartig.Ok ich packe den Zähler om die do while Schleife.
EDIT:
7364503 Durchläufe
EDIT2:
was für Werte soll ich für die Forschleife jetzt nehmen ? Ich hab gerade mal die standart Werte genohmen mit der er noch keinen Fehler kriegt
 
Zuletzt bearbeitet:
Tach auch,

und zwar wollt ich mich mal kurz einklinken, da ich bald in Mathe ein Kurzreferat
zum Thema 'Die Entdeckung des Chaos' halten werde. nun kommt auch da das Mandelbrot-Diagramm
vor. Meine Frage: Worum geht es hier grad genau *kopfkratz*
wollt ihr irgendwas bestimmtes Ausrechnen, oder nur 'das Chaos' mittels Diagramm
darstellen?!
(wäre halt irgendwie nett, zur Veranschaulichung im Referat ;D)
 
Die Variable c ist nun eine konstante komplexe Zahl
Bei der Iteration müssen wir mit irgendeinem z anfangen
und wir fangen am Besten mit z=0 an, z wird quadriert und c addiert
nach den Regeln von oben. Das Ergbenis setzen wir jetzt als neues z ein
und machen dieselbe Rechnung usw. usw., eine Iteration eben. Nach diesem Prinzip kann man Mandelbrot darstellen. Das Ergebniss ist eine Komplexe Zahl , die einen reelen Zahlenwert hat und einen imaginären.Der Punkt wird dann auf der x und y Achse dargestellt , wobei x für die reele Zahl die Koordinate ist und y für den imaginären Teil. Dieses versuche ich mit meinem programm darzustellen.
 
Original geschrieben von Dizzy_Ti
7364503 Durchläufe
Heißa! Das spricht dann doch eher für mind. ~281 MB. Super Sache! *chatt*
Daß das nur langsam laufen kann, ist völlig klar. Du solltest die errechneten Ergebnisse sofort anzeigen lassen, ohne die Daten zwischenzuspeichern, wenn das denn geht.

Original geschrieben von Dizzy_Ti
was für Werte soll ich für die Forschleife jetzt nehmen ? Ich hab gerade mal die standart Werte genohmen mit der er noch keinen Fehler kriegt
Wie gesagt, Wurzel aus 1962801 ist immer noch 1401. D.h. die for-Schleifen laufen jeweils von x bzw. y = 0 bis x bzw. y < 1401.
 
mit den 1401 zeigt er jetzt ein Bild was nur schwarz ist und ein paar Punkte drauf sind.Der Verbrauch lag bei 69 Mb.
EDIT:
1963341 Durchläufe in der Do While Schleife
EDIT2:
Hab die Sichtbereich geändert , jetzt hat alles eine Farbe-
 
Zuletzt bearbeitet:
Hab mir gerade mal GTK angesehen und habs mit Glade auch gleich zum Laufen bekommen (aber irgendwie nur mit C, ohne ++).

Morgen (bzw. heute) werd ich mich dann mal dranmachen und das Mandelbrot nachproggen und auf Speed optimieren - wäre doch was für den nächsten Programmierwettbewerb ;)
 
Ein neuer Wettbewerb! Eine sehr gute Idee. Nur leider habe ich wieder keine Zeit, um mitzumachen ... und das wird sich dieses Jahr auch nicht ändern ... :-/
 
Original geschrieben von intel_hasser
Hab mir gerade mal GTK angesehen und habs mit Glade auch gleich zum Laufen bekommen (aber irgendwie nur mit C, ohne ++).

Morgen (bzw. heute) werd ich mich dann mal dranmachen und das Mandelbrot nachproggen und auf Speed optimieren - wäre doch was für den nächsten Programmierwettbewerb ;)
schon angefangen ?
 
Nein, noch net. Muss auch erstmal sehen wie die Graphikfunktionen mit GTK ablaufen.

Und bevor ich mir nicht eine große Kanne schwarzen Tee intravenös zugeführt habe läuft heute eh nix *chatt*
 
So, jetzt sitzt ich hier mit meiner großen Kanne schwarzen Tee *buck*

Macht ca. 3 Tassen je 0.3l *chatt*
 
hab gerade die 2. Tasse vernichtet ;D

... momentan schlage ich mich mit dem Event Handling von GTK rum...
Ist garnet so einfach, bin schon am Überlegen ob ich nicht doch VB oder irgendwas anderes nehmen soll.


och nööö, jetzt wo ich einmal angefangen hab ;)
 
Schätze, wenn ich noch bis 22 Uhr weitermache bekomm ich das erste Prog hin.

Hab aber vorhin auch net weitergeproggt, sondern eben erst weitergemacht - der erste Eindruck von GTK musste sich erstmal setzen ;)


EDIT:

Sieht schonmal gut aus, hab die GUI jetzt soweit fertigeproggt - jetzt kanns an den Alg selber gehen (hat garnet mal lange gedauert für den Erstkontakt mit GTK *buck*)

Und das Schönste: Die Geschichte lässt sich auch relativ problemlos für Windoofs compilieren, mit Dev-C++ und GTK.
 
Zuletzt bearbeitet:
Zurück
Oben Unten