Dokumentation zu ApfelMenu Autor Bernd Braun Dieses Programm ist Public Domain Wichtig: Zum Laufen des Programms werden req.library und iff.library im Verzeichnis libs: benötigt. Beschreibung des Programms: Dies ist ein Mandelbrot-Generator. Aber kein gewöhnlicher, sondern ein besonders schneller. Obwohl in Oberon geschrieben kommt er an die besten kommerziellen Generatoren heran und übertrifft sie sogar in bestimmten Gebieten. Ausgehend vom wohlbekannten Grundalgorithmus wurde das Programm in vier Gebieten optimiert. Und zwar: 1. Benutzen von 16-Bit normierten Zahlen statt Gleitpunkt Zahlen. 2. Nachschlagen in Tabellen statt Berechnung von Quadratzahlen. 3. Nur jeden dritten Punkt berechnen statt alle. 4. Teile-und-Herrsche Algorithmus statt zeilenweise Berechnung. Weil normierte Zahlen aber nur eine begrenzte Genauigkeit haben, wurden im Programm noch nachträglich 32-Bit normierte Zahlen und REAL Zahlen implementiert. Besitzer eines Numerik-Coprozessors kommen so voll auf ihre Kosten. Beim Verwenden von normierten Zahlen bildet man einen Zahlenbereich in einen anderen ab. Hier: Bereich der rationalen Zahlen in den Bereich der natürlichen Zahlen / F. Wobei F der Normalisierungsfaktor ist. Wenn man einen Rechner mit 32-Bit Registern hat beträgt der Zahlenbereich [ -2^31, 2^31 ] mit einer Genauigkeit von 1. Mit einen Normalisierungfaktor F = 2^13 beträgt der Zahlenbereich [ -2^18, 2^18 ] mit einer Genauigkeit von 1/F. Also ca. 4 Stellen hinter dem Komma. Das ist nicht viel, aber die Berechnung geht viel schneller. Leider kann man den Normalisierungsfaktor nicht höher wählen. Der M68000 führt Multiplikationen nur mit 16 Bit aus, d.h. der Zahlenbereich schrumpft auf [ -4, 4 ] mit einer Genauigkeit von 1/F. Der Normalisierungsfaktor F sollte eine Potenz von 2 sein, damit man statt dividieren ( divs ) zu müssen den Schiebebefehl ( asl ) anwenden kann. Seien a, b, c normierte Zahlen, dann gilt für Addition: c = a + b Multiplikation: c = ( a * b ) / F Statt nun jede Quadratzahl einzeln auszurechnen wird hier zum Programmstart eine Quadratzahlentabelle aufgebaut, in der das Programm dann schnell nachschlagen kann. Der einzige Nachteil ist hoher Speicherbedarf. Alle punktorientierten Graphiken haben einen Vorteil: Wenn die Nachbarn eines Punktes dieselbe Farbe haben, kann man mit großer Wahrscheinlichkeit davon ausgehen, daß der Punkt in der Mitte auch diese Farbe hat. Das erspart einem schon die Hälfte an Berechnungszeit. Hier wurde eine Schrittweite von drei Punkten gewählt. Sind die Randpunkte in einer Farbe werden die beiden mittleren Punkte in dieser Farbe eingefärbt. Wenn nicht, wird der linke der mittleren Punkte berechnet ( wenn die Linie nach rechts gemalt wird ). Tritt jetzt eine Übereinstimmung mit dem rechten Randpunkt auf, wird der rechte der mittleren Punkte in dieser Farbe eingefärbt. Wenn die Randpunkte nicht übereinstimmen kann man die mittleren Punkte interpolieren, besser ist es jedoch sie mit der Iterationsfunktion zu berechnen. Wenn man eine zu große Schrittweite wählt, z.B. 8 Punkte, wird das Bild stark verfälscht ( Mahnendes Beispiel ist das Programm in Amiga-DOS 5/90 ). Das wirklich neue an diesem Programm ist der Teile und Herrsche Algorithmus ( engl. divide and conquer ), den ich in keinem anderen bisher gesehen habe. Damit läßt sich die Schwäche herkömmlicher Generatoren, nämlich das langsame Berechnen der 'schwarzen' Gebiete sehr beschleunigen. Dieser Algorithmus läßt sich hier anwenden, weil die Mandelbrotmenge in jedem Punkt streng monoton ist. D.h. die Menge sieht aus wie ein Berg mit einer Spitze bei dem es nur bergauf oder bergab geht. Es gibt kein Stück ebenen Boden. Es kommt nur ein einziges Mal vor, daß der Rand eines Gebietes in einer Farbe ist, im Gebiet aber noch Farbänderungen auftreten. Das passiert, wenn man das Grundbild ein wenig vergrößert. Bei Juliamengen scheitert dieser Algorithmus, weil es da auch "Inseln" geben kann. Das Grundprinzip von divide and conquer ist: Versuche ein Problem zu lösen. Ist das Problem zu groß für eine einfache Lösung dann Zerlege das Problem in mehrere Teile und versuche die Teilprobleme zu lösen. Konkret sieht das für dieses Programm so aus: Male einen Rand um ein Gebiet. Besteht der Rand nur aus einer Farbe dann Fülle das Innere des Gebietes mit dieser Farbe Sonst Teile das Gebiet in vier Teile und wende auf jeden Teil diesen Algorithmus an Wenn der Assemblerfreak jetzt lacht und höhnt, Oberon ist ja viel zu lahm, dann irrt er sich. Ein Umschreiben der zeitkritischen Prozedur iteration in Assembler bringt höchstens Prozentpunkte aber keine Größenordnungen an Beschleunigung. ( Eigene Versuche in C und Assembler ) Bedienung des Programms: Das Project Menü: Das Programm kann sofort gestartet werden, wenn man die rechte Maustaste drückt und Malen anwählt. Es wird dann das Grundbild mit der Iterationstiefe von 30 berechnet. Die Berechnung des Bildes läßt sich jeder Zeit mit dem Drücken des rechten Mausknopf beenden. Mit Farben erscheint ein Requester mit dem man alle Farben ändern kann. Ein gemaltes Bild läßt sich mit Speichern auf Diskette oder Feltplatte abspeichern, dazu erscheint ein Filerequester mit dem man die Zieldatei komfortabel eingeben kann. Mit Info erscheinen Informationen welche Version das Programm hat und von wem es geschreiben wurde. Verlassen kann man das Programm mit den Anwählen von Ende. Das Graphic Menü: Hier kann man vier verschiedene Bildschirmauflösungen auswählen. 320x256 Pixel sind voreingestellt. Mit Hires kann man die horizontale Auflösung auf 640 Pixel vergrößern. Zurück auf 320 Pixel kommt man mit dem Anwählen von Lores. Mit Interlace vergrößert man die vertikale Auflösung auf 512 Pixel. Zurück auf 256 Pixel kommt man mit Nolace. Das Zoom Menü: Mit dem Anwählen dieses Menüs wird nur ein Ausschnitt aus der Mandelbrotmenge ausgewählt. Zum Berechnen dieses Ausschnitts dann wieder Malen im Project-Menü anwählen. Bei Zoom rein erscheint ein Fadenkreuz, mit dem man den Bildausschnitt wählen kann, der als nächstes berechnet werden soll. Zuerst steuert man das Fadenkreuz zu dem Punkt, der die linke obere Ecke des Ausschnitts werden soll. Hier die linke Maustaste drücken und festhalten. Dann auf die gewünschte rechte untere Ecke zusteuern, das Fadenkreuz wandert dabei mit. Hier die Maustaste loslassen. Der gewählte Bildausschnitt erscheint umrandet. Fehlerhafte Eingaben werden mit einer Meldung bekanntgegeben. Z.B. wenn man die rechte untere Ecke vor der linken oberen Ecke auswähl oder beim Auswählen der linken oberen Ecke die Maustaste gleich wieder losläßt. Mit dem Anwählen von Zoom raus wird mit dem Faktor 2 aus dem Bild herausgezoomt. Über das Grundbild hinaus kann nicht herausgezoomt werden. Mit Reset wird das Grundbild und die Zahlendarstellung 16-Bit gewählt . Das Tiefe Menü: Hier kann man die Iterationstiefe festlegen. Voreingestellt ist 30. Je höher die Iterationstiefe ist, um so mehr Einzelheiten werden dargestellt. Die Berechnungszeit für ein Bild steigt aber proportional zur Iterationstiefe. Das Zahlen Menü: Hier wird die Zahlendarstellung gewählt. 16-Bit ist die schnellste Zahlendarstellung, danach kommt 32-Bit und dann REAL ( das sind Gleitpunkt Dezimalzahlen ). Beim Zoomen in das Bild wird automatisch immer die richtige Zahlendarstellung gewählt. Wenn man einen Mathe-Coprozessor besitzt kann man sofort auf REAL schalten.