4. Optimierung meines Mandelbrot-Explorers

Optimierung meines Mandelbrot-Explorers


  • @SeppJ Im Prizip keine. Ich möchte dies bekanntmachen, dass andere es benutzen können. Ich hab keine bessere Möglichkeit gefunden, über sowas zu diskussieren. Ich war unter anderem Login schon vor Jahren bei Euch unterwegs. Deshalb fand ich, dass sich hier die meisten gute Leute austauschen. Ausserdem finde ich das neue Format des Forums jetzt sehr gut.

    0 1 Antwort

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    dass andere es benutzen können.

    omg nein.

    https://www.mandel.org.uk/

    0 1 Antwort

  • @hustbaer Das mit der GPU interessiert mich. Allerdings habe ich so programmiert, dass ich für jedes Zahlenfomat ( Gleitkomma, Festkomma ) je eine Klasse habe. Ausserdem arbeit meine selbsterstellte Festkomma-Library mit 128 Bits Vorkomma und 640 Bits Nachkommastellen. Kann das eine GPU auch?
    Ausserdem läuft die Bilderrechnung auf beliebig vielen Threads ab. Bis dahin war ganz schön flott unterwegs. Der Zeitgewinn durch diese Optimierung war schon fast gigantisch.

    Dein Code scheint mir unbrauchbar zu sein, da es auch zyklische Iterationsfolgen gibt, die divergieren können.

    0

  • @Swordfish Danke für diesen Link. Allerdings ist das Programm dort im Vergleich ein Spielzeug, und sowas gibt es schon tausendfach seit Jahrzehnten. Ich hab da mehr Ansprüche.

    0

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    Dein Code scheint mir unbrauchbar zu sein, da es auch zyklische Iterationsfolgen gibt, die divergieren können.

    Nein, gibt es nicht. Zyklisch ist zyklisch. Du hast nur eine einzige State-Variable. Sobald die wieder den selben Wert hat, weisst du dass du einen Zyklus hast.

    0 1 Antwort

  • @hustbaer Du beziehst dich auf Folgen mit c = (0|0), oder c = (-1|0), und andere dieser Sorte. Da hast Du recht. Aber das sind nur einzelne Punkte, wärend die Restlichen Folgen auf ein anderes z hin konvergieren. Und dann nahe am Rand der M wird die Folge dann immer öfter Chaotisch und divergent. Ich hab mir solche Folgen haufenweis in den Zeitreihen angesehen. Reihen, die oft über 100k Iterationen dauerten. Ich denke Du hast kein Programm das sowas zeigen kann. Leider hab ich noch keine Lösung, wie ich hier Bilder zeigen kann. Denn dann könne ich einige Screenshots bringen.
    In Deinem Programmvorschlag verdoppelts Du iref immer. Da bin ich am Grübeln wie damit ein 3er oder 5er, usw Zyclus erkannt werden soll, oder gar einer im tausender Bereich.
    PS.: und was ist nun mit der GPU los? Da hätt ich gern eine Anleitung zu Deinem Vorschlag.

    0

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    Du beziehst dich auf Folgen mit c = (0|0), oder c = (-1|0), und andere dieser Sorte.

    Nö, ich bezieh mich auf so Folgen die zwischen ein paar Punkten hin und her springen. Keine Ahnung ob's von denen jetzt besonders viele gibt. Konvergieren die klassischen "Kringel" alle zu einem Punkt in der Mitte? Von denen gibt's nämlich haufenweise, zumindest im fetten Klopps in der Mitte. Wobei der für dich natürlich uninteressant ist 🙂

    Ich hab mir solche Folgen haufenweis in den Zeitreihen angesehen. Reihen, die oft über 100k Iterationen dauerten. Ich denke Du hast kein Programm das sowas zeigen kann.

    Hab ich tatsächlich nicht. Wenn mein Vorschlag für dich nicht brauchbar ist, hab ich damit kein Problem, ich werd nicht versuchen dir einzureden dass was funktioniert was halt nicht funktioniert. War einfach mein "best guess".

    Hast du eins mit dem man sich da mal spielen könnte? Also jetzt nicht unbedingt dein Code, gibt ja etliche Programme in der Richtung, aber ich weiss nicht welche da gut sind.

    In Deinem Programmvorschlag verdoppelts Du iref immer. Da bin ich am Grübeln wie damit ein 3er oder 5er, usw Zyclus erkannt werden soll, oder gar einer im tausender Bereich.

    Durch die Verdoppelung verdoppelt sich auch immer die Iterationsanzahl bis der Referenzwert wieder wechselt. D.h. du hast erstmal für zwei Iterationen den selben Wert, dann wieder für 2, dann für 4, dann für 8 usw.

    Wenn du jetzt einen Zyklus mit Länge 123 hast, dann wird dieser erkannt sobald der Punkt erreicht ist wo der Referenzwert für 128 Iterationen behalten wird. Weil sich ja alle 123 Werte des Zyklus wiederholen, und damit kommt irgendwann wieder der Referenzwert den man sich behalten hat. Das ist also kein Problem. Standardmethode zum Erkennen von Zyklen unbekannter Länge.

    Was eher ein Problem sein wird, ist dass die ganze Gaudi nicht sofort in den stabilen Zyklus geht, sondern erst langsam da hin driftet. (IIRC wird der stabile Zyklus sowieso nur im Limes erreicht)

    Und eben die oben erwähnte Sache dass ich nicht weiss wie häufig solche Zyklen wirklich sind. Andrerseits sollte es auch für Zyklen mit Länge 1 gehen.

    PS.: und was ist nun mit der GPU los? Da hätt ich gern eine Anleitung zu Deinem Vorschlag.

    Wie man das im Detail macht kann ich dir auch nicht sagen. Ich weiss nur dass die GPU für so Numbercrunching Sachen oft super gut geht. Was extended precision Zeugs angeht kann ich dir also nix konkret empfehlen. Ausser mal zu googeln ob du da was findest - falls es dich interessiert. Mit CUDA kannst du ja z.B. sogar C++ Code ohne grosse Einschränkungen auf der GPU laufen lassen. Also gehen müsste es IMO auf jeden Fall.

    1
    T
     1 Antwort

  • Vielleicht hilft ein kleines Beispiel was die Zyklenlänge angeht:

    z     zref
1     -
2     1
3     1
4     3
5     3
1     3
2     3
3     2
4     2
5     2
1     2
2     2   <-- treffer
3     2
4     2
5     2
...   ...

    Stimmt jetzt nicht genau mit meinem Code zusammen, aber sollte verdeutlichen dass man mit Verdoppelung der Abstände zwischen den "Samples" sämtliche Zyklen findet, egal wie lange die sind.

    0
  • T
    Gesperrt

    @hustbaer sagte in Optimierung meines Mandelbrot-Explorers:

    Kringel

    Danke @hustbaer. Habe das Wort einmal im Zusammenhang mit kubischen Splines gelesen (benutzte selbst das Wort Schlaufen), dann vergessen (aber nicht die Existenz) und vergebens gesucht. Und heute - oh Glück - da lese ich das Wort wieder. Vielen Dank.

    0

  • @titan99_ Ja, ich wusste nicht wie ich sonst sagen soll. Und ich wollte es auch nicht umständlich beschreiben. Und dann ist mir das Wort "Kringel" eingefallen 🙂

    Wobei es eben fürchte ich eher Spiralen sind. Andrerseits sollte das alles egal sein, so lange man Epsilon klein genug wählt.

    0 1 Antwort

  • @hustbaer In dem Abschnitt, in dem Du das Wort Kringel benutzt hast, folgt deiner Meinung nach, mich würde "der fette Klops in der Mitte" nicht interessieren, und das hellseherisch als natürlich zu betrachten. Das wollte ich bisher nicht diskustieren, aber es hat mich gekränkt. Gerade der Unterschied des Verhaltens im großen Klops zu den kleinen Klöpsen fand ich spannend. Und gerade die kleinen Klöpse in diesen Algorithmus zu intergrieren ist die Herausforderung. Im großen Klops ist das leicht. Dann gibt es ja noch die ganz kleinen Klöpse, nicht zu vergessen die Satelliten mit all ihren superkleinen Klöpschen.

    Dein Programm werde ich mal testen, dauert ein bischen - Kommentar kommt - und das sachlich, aber ich vermute schon, Dein Algo funktioniert nur im großen Klops. Wenn doch mea culpa.

    Zu Deinem letzten Post an titan99: ja, es sind Spiralen, und es sind Spialen in Spiralen, Und pro Klöpschen noch ne Spirale drauf. Und das, bis Dir der Kopf schwindelig wird. Guck mal in die Wikipedia MBM:Intermediär wechselhaftes Verhalten , da gibts einen kleinen Einblick. Sollte Dein Algo diese Folge richtig decodieren, wäre ich platt.
    Nicht zu vergessen, dieser Wiki-Edit mit Bildern stammt von mir.

    1 1 Antwort

  • @RudiMBM sagte in Optimierung meines Mandelbrot-Explorers:

    @hustbaer In dem Abschnitt, in dem Du das Wort Kringel benutzt hast, folgt deiner Meinung nach, mich würde "der fette Klops in der Mitte" nicht interessieren, und das hellseherisch als natürlich zu betrachten. Das wollte ich bisher nicht diskustieren, aber es hat mich gekränkt.

    Ähm, OK. Sorry, war nicht meine Absicht. Nur wieso kränkt dich das? Meine Einschätzung davon was dich interessiert war falsch. War ja aber doch nicht böse/abwertend gemeint.

    Dein Programm werde ich mal testen, dauert ein bischen - Kommentar kommt - und das sachlich, aber ich vermute schon, Dein Algo funktioniert nur im großen Klops. Wenn doch mea culpa.

    Du musst dich auch nicht entschuldigen wenn deine Einschätzung des Erfolgs des von mir vorgeschlagenen Algorithmus falsch ist, und schon gar nicht präventiv. Wenn du es ausprobieren und dann das Ergebnis berichten magst freut mich das 🙂

    0 1 Antwort

  • @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
Anmelden zum Antworten