4. Optimierung meines Mandelbrot-Explorers

Optimierung meines Mandelbrot-Explorers


  • @hustbaer Ergebnis des Vergleichtests:
    Die Bilder, die hier verlinkt sind zeigen farbcodiert bei welchen Itercount die Folge beendet wurde.
    Für beide Versionen, sind 16 Bilder mit Epsilon von 1e-16 bis 0,1 zu sehen.
    Version 1--> https://youtu.be/eRx978hVCV0?t=52
    Version 2--> https://youtu.be/eRx978hVCV0?t=6 (hustbaer Vers.)

    1. Der Zweck, konvergente Folgen schneller zu erkennen funktioniert bei beiden. (zumindest in diesen Test)

    2. Bei Maxiter=100k und Epsilon= 1e-16 rechnet Vers.1 2m14sec, Vers2 3m45sec, ohne optimierung wären es 47min.

    3. Beide funktionieren mit Epsilon < 1e-5. Bei tieferem Zoom entsprechend noch kleiner.

    Obwohl für den geplanten Einsatz uninteressant, würde es mich schon interessieren wie diese Muster begründet sind. Vielleicht steckt ja ein kleines Erkenntnis unbekannter Eigenschaft der MBM dahinter.

    0 1 Antwort

  • @RudiMBM
    Interessant. Hast du das initiale imin in Version 1 hand-getuned für dieses Bild (diesen Ausschnitt)? Wenn nicht wundert es mich nämlich etwas dass Version 1 schneller ist.

    0 1 Antwort

  • @hustbaer Nun, da muß ich was vorausschicken. Mein Explorer arbeiten mit einen Festkommaformat zZ. aus 360Bits + Status für z und c; Da ich in Vers1 im ersten Schritt nur i mit imin als integer vergleiche bin ich da viele schneller. Vers2 vergleicht aber in jedem Loop 360 bit 360 Bits, falls die Unterschiede nur sehr klein sind, und auf das sind wir ja mit Epsilon aus. Das dauert. Das wird sich wohl annähern, wenn z nur double ist. Float hab ich aber aus Optimierungs-Gründen verworfen, da in der MBM sich die meisten Iterationsergebnise im Bereich von 1,xxxxx bewegen. Und das wäre mit long double Epsilon 1e-18 schon viel zu ungenau. Ohwohl ich ahne was passiert, ich könnte den ganzen Test auch mit long double machen, meinen Explorer kann ich zwischen mehreren Formaten umschalten.

    0

  • @RudiMBM
    Ah, ja, macht Sinn.
    Etwas optimieren könnte man das ganze noch indem man abs_squared(z - zref) < EpsilonSquared statt abs(z - zref) < Epsilon macht. Falls du das nicht schon sowieso gemacht hast.

    Ansonsten... man könnte die Anzahl der Vergleiche auch kleiner halten. Die Zyklen werden ja vermutlich nicht so brutal lange sein - also verglichem mit Itermax meine ich. D.h. es würde wohl auch reichen pro Verdoppelung von iref nur z.B. (iref+7)/8 oder (iref+15)/16 Tests direkt hintereinander zu machen. Und zusätzlich alle 8 oder 16 Schritte, damit man beim Konvergieren zu einem einzelnen Punkt nicht viel zu lange wartet.

    ps: Noch besser wäre denke ich die "Chebyshev distance" oder "Manhattan distance" zu verwenden - damit bräuchte man dann nichtmal mehr ne Multiplikation. Das sollte dann mMn. kaum mehr merkbar sein, da die paar Additionen/Subtraktionen/Vergleiche die man da hat deutlich billiger sein sollten als das Quadrieren von z.

    0 1 Antwort

  • @hustbaer Ja, in beiden Vers. wird nur das quadrat von z verglichen. Soll ja optimiert ablaufen.

    0 1 Antwort

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    @hustbaer Ja, in beiden Vers. wird nur das quadrat von z verglichen. Soll ja optimiert ablaufen.

    Dann probier mal "Chebyshev distance" oder "Manhattan distance". Das sollte nochmal einiges bringen.

    "Chebyshev distance" ist einfach nur max(abs(x2-x1), abs(y2-y1)) und "Manhattan distance" ist abs(x2-x1) + abs(y2-y1). Bzw. halt r und i statt x und y in diesem Fall.

    Für die Entscheidung ob der Fehler klein genug ist, sollten beide ausreichend sein. (Bei der "Chebyshev distance" müsstest du noch Epsilon halbieren damit der Vergleich fair ist.)

    0 1 Antwort

  • @hustbaer Wozu das? In der Iter-Formel fällt sowieso real² und Imag² an, da brauch ich nur 1 Addition für Pytagoras abs(z)². Allerdings möchte ich erwähnen, dass ich Epslilon bereits als squared ein- und angegeben habe. Im Test war das 1e-16. Unsquared wären das dann 1e-8.

    0 1 Antwort

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    @hustbaer Wozu das? In der Iter-Formel fällt sowieso real² und Imag² an, da brauch ich nur 1 Addition für Pytagoras abs(z)².

    Ähm. Ich versteh' jetzt mal nicht wie das gehen soll. Wo sollen in der Iteration (z_r - zref_r)² und (z_i - zref_i)² anfallen?

    EDIT: Also ich rede von dieser Zeile da: if (abs(z - zref) < Epsilon)

    0 1 Antwort

  • @hustbaer sagte in Optimierung meines Mandelbrot-Explorers:

    Also ich rede von dieser Zeile da: if (abs(z - zref) < Epsilon)

    dann mach doch mal

    if ( abs( z²-zref²) < Epsilon²)

    dann brauchste nicht vorher Wurzelziehen. Und geht doch, oder?

    0 1 Antwort

  • @RudiMBM
    Geht schon, ist bloss nicht das selbe.
    (a-b)² = a² - 2ab + b² und nicht a² - b²

    Damit bekommst du einerseits zu grosse bzw. zu kleine Fehlerwerte (je nachdem ob du ausserhalb oder innerhalb des Einheitskreises bist). Beispiel: (2-3)² ist 1 aber |2²-3²| ist 5*.

    Und andrerseits bekommst du false positives.

    Also ich persönlich würde da wirklich einfach eine andere Distanz-Metrik verwenden.

    *: Ja, ich weiss dass der Bereich ausserhalb der Mandelbrotmenge liegt. War nur ein Beispiel, im "relevanten" Bereich werden die Abweichungen geringer sein. Trotzdem sind sie da, und variieren vor allem je nachdem wie weit man vom Einheitskreis entfernt ist. Und speziell im Bereich r=0.25, der ja auch halbwegs interessant sein sollte, sind die Abweichungen dann schon nicht mehr so klein.

    0 1 Antwort

  • Ihr solltet auch Bedenken, das der PC nie eine wirklichen Reihe berechnet. Sondern nur eine Näherung, die wegen der chaotischen Natur immer weiter abweicht, von der richtigen Reihe. Ist z aus zwei floats, gibts grad mal 2^63 Kombinationen. Nochmal weniger, wenn man den Exponent beschränkt. Man sollte also echt mal einfach alle z markiert, die in Zyklenlängen über x vorkommen, bzw. einfach jedes z nach x Gliedern der Zyklen. Dann hat man eine Obergrenze von Rechenschritten, mit dem für jedes z die Lösung bestimmt wird.

    0 1 Antwort

  • @TGGC z ist komplex, also bei double wären das dann schon 2^126. Und @RudiMBM (bzw. sein Programm) rechnet mit 360 Bit Fixkommazahlen. Also 2^720. Hui 🙂

    0

  • @TGGC sagte:

    Ihr solltet auch Bedenken, das der PC nie eine wirklichen Reihe berechnet. Sondern nur eine Näherung, die wegen der chaotischen Natur immer weiter abweicht, ....

    Das ist ein weitverbreiteter Irrtum, dass in der Computer-MBM-Iterations-Folge das Chaos beteiligt ist. Die Abweichungen entstehen durch die Begrenzung der Nachkommastellen. Bei den Multiplikationen werden hinten signifikante Ziffern nach rechts rausgeschoben. Bei sqrt(x) zB. werden wieder Nachkommastellen von rechts hereingeholt, und das sind in der Regel Nullen. Bei sqrt(x²) bleibt also nur die halbe Genauigkeit übrig. (Nicht in der reinen Mathematik) Ab diesen Iterationsschritt ist die Folge verfälscht, oder man kann sagen es ist eine Andere. Das wahre Chaos kann nur in einem analogen System erfolgen, Da gibt es keine Nachkommastellen, oder je nachdem unendlich viele.

    0

  • @hustbaer sagte:

    Geht schon, ist bloss nicht das selbe.
    (a-b)² = a² - 2ab + b² und nicht a² - b²

    Ich habe in in diesem Punkt wohl sehr ungeschick formuliert.
    In der Iterationsschleife wird programmiert um den neuen Betrag(z) zu erhalten:

    remain_iter = max_iter
xx = x*x
yy = y*y
xy = x*y
betrag_z² = xx + yy
WHILE (betrag_z² <= max_betrag_z²) AND (remain_iter > 0)
  remain_iter = remain_iter - 1
  x  = xx - yy + cx
  y  = xy + xy + cy
  xx = x*x
  yy = y*y
  xy = x*y
  betrag_z² = xx + yy
 // hier der break-Test
END

    Aus betrag_z² wird letztlich betrag_zref² ermittelt, und wenn ich beide Quadrate subtrahiere (großes - kleines), bleibt eine Restfläche übrig. Wenn die kleiner ist als Epsilon² bin ich fertig.

    0

  • @RudiMBM
    Also anders gesagt: du nimmst in Kauf dass dein "effektives" Epsilon abhängig vom Betrag von z schwankt. Korrekt?

    Dann kann mMn. der Unterschied nur mehr sein dass deine "Variante 1" die Konvergenz mit weniger Zyklen erkennt als die auf meinem Vorschlag basierende "Variante 2". Denn wenn du dir die Anzahl an Operationen ansiehst die du hier pro Schritt benötigst, also speziell die Multiplikationen, dann können eine Subtraktion und ein Vergleich das nicht so drastisch langsamer machen.

    BTW: Hast du mal probiert was passiert wenn du beide Abbruchbedingungen kombinierst? Also eine Variante "1&2"?

    0 1 Antwort

  • @hustbaer sagte in Optimierung meines Mandelbrot-Explorers:

    Also anders gesagt: du nimmst in Kauf dass dein "effektives" Epsilon abhängig vom Betrag von z schwankt. Korrekt?

    Wieso soll es schwanken? Epsilon und Epsilon² ist über alle Bildpunkte und Zwischeniterationsergenisse eine Konstande. Ich hab es ja schon mal erwähnt: Die Hüllkurve. zB. c = (0.5,0.5) das ist ein Grundzyclus. Im Verlauf der Iteration werden sich die Iterationsergenisse einem bestimmt Punkt z annähern. Dadurch werden sich der Betrag(z von i) und der Betrag(z von i-x) annähern. Unterschreitet die Differenz Epsilon dann.... Erstaunlicher Weise funktioniert das auch bei allen anderen Zyclen. (Aber die Begründung dafür würde einen neuen Thread benötigen)

    "Variante 1" die Konvergenz mit weniger Zyclen erkennt als die auf meinem Vorschlag basierende "Variante 2"

    Ich bin nicht sicher wieviele Iterationen jeweils nötig sind, vielleich sogar mehr, aber es ist sicher, dass in Vers.1 viel weniger Codezeilen pro Iteration ausgeführt werden.

    zu BTW: ich hab keinen Plan dazu.

    Jetzt sollte aber noch der Begriff "Zyclus" vs. Iteration geklärt werden, wie mir auffällt. Ich glaube wir sprechen da von verschiedenen Parametern. c = (-1|0) wäre ein 2er Zyclus.

    0

  • @RudiMBM

    Wieso soll es schwanken? Epsilon und Epsilon² ist über alle Bildpunkte und Zwischeniterationsergenisse eine Konstande.

    Ja, sorry, ich hab das wohl etwas zu undeutlich formuliert. Mit "effektives" Epsilon meine ich die Distanz (|a-b|) zwischen den beiden Punkten. Da du eine andere Formel für das Abbruchkriterium verwendest (a²-b²) gibt es keinen fixen Grenzwert für die Distanz |a-b|.

    Jetzt sollte aber noch der Begriff "Zyclus" vs. Iteration geklärt werden, wie mir auffällt.

    Sorry, ich meinte damit Iterationen.

    aber es ist sicher, dass in Vers.1 viel weniger Codezeilen pro Iteration ausgeführt werden.

    Naja, wie viele Codezeilen es sind ist nicht unbedingt wichtig, weil nicht jede Codezeile gleich lange dauert. Eine Addition von zwei 360 Bit Zahlen ist viel schneller als eine Multiplikation von zwei solchen Zahlen und diese ist wiederrum viel schneller als eine Division usw.

    Ist dein Code Open-Source? Falls ja könnte ich mir den ja mal ansehen und selbst ein wenig damit rumspielen.

    0 1 Antwort

  • @hustbaer Hätte ich nichts dagegen. Der Code ist bisher privat und unveröffendlicht. Was interessiert Dich? Der ganze Explorer, oder nur Fixpoint (Ist nur für diese Anwendung gemacht (geeignet?)). Ist halt alles mit c++Builder 2009 gemacht und nicht unbedingt State of the Art.

    |a-b| wäre natürlich ideal. Aber 1. will nicht Rechnzeit mit sqrt() verschwenden, und 2. a²-b² funktioniert annähernd genausgut.

    0

  • OK. Ich hab meine aktuelle Programmversion auf https://github.com/RudiMBM/DeepChaos bereitgestellt. Da ist das, was hier besprochen wurde, schon drin.
    Ich wünsch einen schönen Osterspaß.

    0

  • Danke. Und sorry für die späte Antwort. Ich werde es mir mal ansehen, schauen ob ich das mit Visual Studio zum Laufen bekommen.

    ps: Achje, nein, wenn dann hätte mich der Source interessiert. Um verschiedene Dinge auszuprobieren.

    0 1 Antwort
Anmelden zum Antworten