Extremes Mandelbrot

Für sonstige Unterhaltungen, welche nicht direkt mit Lazarus zu tun haben
Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Extremes Mandelbrot

Beitrag von Mathias »

Weis einer, wie solche extremen Mandelbrote erstellt wurden ?
Ich könnte mit vorstellen, das man da einen Grossrechner braucht. Bei einem normalen PC ist bald mal Schluss, egal ob Assembler mit MPU oder mit der Nutzung der GPU.

https://www.youtube.com/watch?v=pCpLWbHVNhk
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

Hallo!

Einen Versuch auf dem PC wäre es wert, denn

Bei jedem Frame ändert sich der Zoomfaktor und damit verringert sich auch die Anzahl der darstellbaren Punkte im rekursiven Baum.

Bevor man also den nächsten rekursiven Aufruf startet muss man also checken, ob der Ausgangspunkt noch im dargestellten Rechteck liegt. Falls nicht: abbrechen.

So müsste man das auch auf einem PC hinbekommen.
Sag ich mal leichtsinnig.

Winni

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

Hi!

Der PC stösst an seine Grenzen mit Mandelbrot.

Bei einem Zoom von 100 000 fängt es an zu humpeln.
Bei 1 000 000 und mehr ist definitiv jeder einzelne Bildaufbau zu sehen.

Und bei einem Zoom von 500 000 000 sind leider die 64 Bit des Double aufgebraucht und es findet keine Rekursion mehr statt.

Man könnte jetzt noch mit Threads losschiessen, aber das schiebt die Grenzen auch nur nach oben, aber löst das Problem nicht.

Winni

Benutzeravatar
corpsman
Lazarusforum e. V.
Beiträge: 1496
Registriert: Sa 28. Feb 2009, 08:54
OS, Lazarus, FPC: Linux Mint Mate, Lazarus GIT Head, FPC 3.0
CPU-Target: 64Bit
Wohnort: Stuttgart
Kontaktdaten:

Re: Extremes Mandelbrot

Beitrag von corpsman »

Also ich setzte gern und Häufig die Mathe Lib des Verstorbenen Wolfgang Erhardt ein

Seine HP ist off, aber im Archive zum Glück erhalten geblieben. Wenn dir die Geschwindigkeit egal ist, kannst du damit wenigstens die Grenze der 64-Bit noch deutlich erweitern ;)
--
Just try it

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6198
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Extremes Mandelbrot

Beitrag von af0815 »

Winni hat geschrieben:
Mo 13. Sep 2021, 23:05
Bei 1 000 000 und mehr ist definitiv jeder einzelne Bildaufbau zu sehen.

Und bei einem Zoom von 500 000 000 sind leider die 64 Bit des Double aufgebraucht und es findet keine Rekursion mehr statt.
Du hast vorher erwähnt, das du je nach Zoom die Größe der berechneten Fläche reduzierst. Solle nicht der Zahlenraum mit skaliert werden ? Daher alle 1000 Zoomstufen der Zahlenraum entsprechend angepasst werden ?! Damit würde der Zahlenraum immer passend sein. Oder liege ich damit komplett falsch.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

TSchnuckenbock
Beiträge: 71
Registriert: Do 20. Jul 2017, 23:47
OS, Lazarus, FPC: Win7 und Win10
CPU-Target: xxBit
Wohnort: Südheide (Schnuckenland)

Re: Extremes Mandelbrot

Beitrag von TSchnuckenbock »

corpsman hat geschrieben:
Di 14. Sep 2021, 06:23
Also ich setzte gern und Häufig die Mathe Lib des Verstorbenen Wolfgang Erhardt ein

Seine HP ist off, aber im Archive zum Glück erhalten geblieben. Wenn dir die Geschwindigkeit egal ist, kannst du damit wenigstens die Grenze der 64-Bit noch deutlich erweitern ;)
Ich hatte mir damals noch viele Quellen von Wolfgang Ehrhardt runtergeladen. Also falls mal wer Code von ihm ("gammatester"?) suchen sollte und nicht mehr findet, kann mir eine PN schicken.

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Extremes Mandelbrot

Beitrag von Mathias »

Ich habe es auch schoj mit der GPU und OpenGL gemacht, das war bei mir schon einiges schneller, als mit der GPU und Assembler, obwohl ich eine NVidia Officekarte habe.
Da ist man aber auch an das Limit von Float/Double gebunden.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

Hi!

@af0815:
Nee, das geht automatisch. Das Problem liegt tatsächlich in den nur 15 Digits des Double:

Da immer mehr Stellen für den Zoom draufgehen, bleiben immer weniger Stellen zur Berechnung des Grenzwertes für jeden Pixel. In den unteren Zoom-Stufen braucht er nur 40% der loops, die er für die hohen Zooms braucht. Zum Schluß braucht er 230 bis 256 von maximal 256 Loops pro Pixel.

Die Auslagerung in Threads (in meinem Fall 8) ging auch schief, da der Overhead (pro Pixel-Zeile) deutlich mehr auffrisst, als die parallele Berechnung einbringt.

Also: Wir müssen warten auf die 128 Bit Rechner. Oder weiss jemand von einer lmplementierung von 128-Bit-Floats??

Winni

BeniBela
Beiträge: 308
Registriert: Sa 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4)
CPU-Target: 64 Bit

Re: Extremes Mandelbrot

Beitrag von BeniBela »

Winni hat geschrieben:
Di 14. Sep 2021, 20:18

Also: Wir müssen warten auf die 128 Bit Rechner. Oder weiss jemand von einer lmplementierung von 128-Bit-Floats??

Sogar mit Mandelbrot: https://blog.grijjy.com/2021/05/05/high-precision/

Aber vielleicht nicht für FreePascal

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

BeniBela hat geschrieben:
Mi 15. Sep 2021, 00:15

Sogar mit Mandelbrot: https://blog.grijjy.com/2021/05/05/high-precision/

Aber vielleicht nicht für FreePascal

Hi!

Danke für den Hinweis.

Aber das ist Delphi-only und ohne Source.
Hilft uns/mir nicht weiter.

Winni

PascalDragon
Beiträge: 825
Registriert: Mi 3. Jun 2020, 07:18
OS, Lazarus, FPC: L 2.0.8, FPC Trunk, OS Win/Linux
CPU-Target: Aarch64 bis Z80 ;)
Wohnort: München

Re: Extremes Mandelbrot

Beitrag von PascalDragon »

Winni hat geschrieben:
Di 14. Sep 2021, 20:18
Also: Wir müssen warten auf die 128 Bit Rechner. Oder weiss jemand von einer lmplementierung von 128-Bit-Floats??
Units sfpu128 (Funktionen für 128-bit Fließkommazahlen) und ufloat128 (Operator Überladungen für 128-bit Fließkommazahlen). Diese sind seit 3.3.1 standardmäßig bei allen großen Plattformen aktiviert, ansonsten können die auch von Hand gebaut werden.
FPC Compiler Entwickler

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Extremes Mandelbrot

Beitrag von Warf »

Winni hat geschrieben:
Di 14. Sep 2021, 20:18
Nee, das geht automatisch. Das Problem liegt tatsächlich in den nur 15 Digits des Double:

Da immer mehr Stellen für den Zoom draufgehen, bleiben immer weniger Stellen zur Berechnung des Grenzwertes für jeden Pixel. In den unteren Zoom-Stufen braucht er nur 40% der loops, die er für die hohen Zooms braucht. Zum Schluß braucht er 230 bis 256 von maximal 256 Loops pro Pixel.
Warum? Double ist doch ein IEEE 754 typ, besteht also aus einer mantisse (52 bit), einem exponenten (11 bit) und einem sign bit. Eine skalierung sollte also rein über den exponenten möglich sein, und Auflösung sollte damit auf jeder größenordnung gleich hoch sein (ausnahmen um die 0 rum, da sinds 53 bit statt 52). D.h. bis zu einem skalierungsfaktor von 2^1024 (was eine zahl mit c.a. 300 dezimalstellen ist) dürfte kein einziges Mantissen bit für die skalierung draufgehen.

Natürlich gilt das nur wenn du in 2er potenzen skalierst. Skalierst du z.b. um 1/10 skalierst, was ja 1/2 *1/5 ist, hast du das problem das 1/5 sich nicht als 2er potenz ausdrücken lässt weshalb sich eine solche skalierung auf die Mantisse auswirkt. Aber das ist letztendlich nur eine Limitation um die man seinen algorithmus drum rum bauen muss indem man einfach immer um einen faktor von 2 skaliert

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

Hi!

Bevor diesed Projekt - wie viele Test-Projekte - für immer auf der Festplatte vor sich hinschimmelt, hab ich das Ganze mal grundlegend überarbeitet und als kleine App für jedemann benutzbar gemacht.

Man kann:
* Einige vordefinierte Mandelbrot-Pics anzeigen lassen
* Man kann Zoom und Xoffset an Trackbars einstellen und sich anzeigen lassen.
* Es gibt einen Mini-Film, der in 960 Loops immer tiefer in die Mandelbrot-Menge reinzoomt - bis zu einem Zoom von 1 : 19.000.000.000

Außerdem können wahlweise lineare oder parallele Thread Berechnung ausgewählt werden. Bei den einzelnen Bildern ist das nicht so spannend, aber bei dem Filmchen merkt man den Geschwindigkeits-Gewinn der Threads.

Um das Ganze auf der graphischen Seite zu beschleunigen, wird alles auf eine zwischengeschaltete BGRAbitmap gezeichnet. Und da als Grundlage ein älteres Turbo-Programm genommen wurde, gibt's die 256 Turbo-VGA-Farben als Include-File eingeschlossen.

Viel Spaß!

Winni

PS.: getestet mit Suse Turmbleweed und Win7/64
Erstellt mit fpc 3.2 und Lazarus 2.012
Dateianhänge
MandelScreenshot.png
MandelScreenshot.png (174.02 KiB) 2802 mal betrachtet
Mandelbrot.zip
(610.1 KiB) 118-mal heruntergeladen

Benutzeravatar
Winni
Beiträge: 1577
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.2.2, fpc 3.2.2
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Extremes Mandelbrot

Beitrag von Winni »

Warf hat geschrieben:
Fr 17. Sep 2021, 14:46
Aber das ist letztendlich nur eine Limitation um die man seinen algorithmus drum rum bauen muss indem man einfach immer um einen faktor von 2 skaliert
Na, dann wünsch ich Dir mal ne Fussball-Übertragung bei der die Kamera nur in Zweier-Potenzen zoomt. Nach zwei Minuten rennst Du schreiend raus.

Der PC und Programmierung sind Werkzeuge. De Mensch hat sich Werkzeuge erschaffen, um sich die Welt passend zu machen. Und nicht um sich den Werkzeugen anzupassen.

Bei aller Theorie auch mal n bischen an die Praxis denken ....

Winni

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Extremes Mandelbrot

Beitrag von Warf »

Für ein Fußballspiel wäre das wohl tatsächlich gänzlich ungeeignet, aber wir reden hier ja nicht von einem Fußballspiel.

Wenn die anforderung ist eine tiefe Mandelbrot Animation zu machen, funktioniert das mit den zweierpotenzen einwandfrei. Man berechnet für die aktuelle Stufe (zoom = 2^n) und für die nächste (zoom = 2^(n+1)) und macht dann eine pixel zoom animation zwischen den beiden.
Somit spart man sich berechnungen auf jedem frame, und gleichzeitig hat man die volle Auflösung bis auf 2^-1023 runter.

Wenn einem das zu großschrittig ist, kann man ein paar bits der mantisse zum feineren zoomen zu nehmen (um dann statt in 1/2 z.b. in 3/4 schritten zu zoomen). Solang man bei vielfachen von zweierpotenzen bleibt (3/4, 7/8, etc.) müsste die anzahl an bits die dafür draufgehen konstant bleiben. Damit kann man den tradeoff zwischen Genauigkeit und Bildabständen exakt bestimmen, um einen weichen übergang zu erlauben

Antworten