Julia-Mengen mit Scratch

large_julia1_-0,123_0,746.jpg Scratch ist als Einsteiger-Programmierplattform auf den ersten Blick nicht wirklich prädestiniert, um stark rechenlastige Aufgaben, wie die Visualisierung von Julia-Mengen zu übernehmen. Nach der Anregung eines Artikels im MagPi-Magazin ("MagPi SE 1", S.16ff), musste ich es aber doch einmal testen. Selbst ein Raspberry PI mit Scratch hat heute ja eine zu den PCs unserer Jugend vergleichbare Rechenleistung.

Grundlagen

Den kompletten mathematische Hintergrund der Julia-Menge kann man bei Wikipedia nachlesen. Stark vereinfacht bestehen die Grundlagen der fraktalen Grafiken aus:

  • Komplexen Zahlen (Realteil + Imaginäreteil), die auf einer Ebene dargestellt werden. In x-Richtung der reale Anteil, in y der imaginäre Anteil). Ein Punkt (3,4) entspricht also der komplexen Zahl (3 | 4i). Dies ist die komplexe Zahlenebene
  • Für jeden Punkt der komplexen Zahlenebene wird iterativ ein Polynom gelöst. Dieses konvergiert der Betrag jeder Zahl für jeden Punkt unterschiedlich schnell in Richtung Null oder Unendlich. 

In diesem Projekt nutze ich (wie im Beispiel im Heft) das Polynom f(n+1) = f(n)² + c. Die Konstante c wird dabei am Anfang für die ganze Zahlenebene einheitlich vorgegeben und diese beeinflusst am Ende maßgeblich die entstehenden Bilder. Die am Rande angezeigten Bilder wurden mit den folgenden Konstanten berechnet:

large_julia2_-0,4_0,6.jpg

c (real) c (imaginär)
-0,123 0,746
-0,4 0,6
-0,1 0,651
-0,7467 0,3515
-0,8 0,156
0,687 0,312

large_julia3_-0,1_0,651.jpg

Die Rechenanweisung des Polynoms für den Punkt z (z_re|z_im) zerlegt in die realen und imaginären Anteile:

  • z_re(n+1) = z_re(n) * z_re(n) - z_im(n) * z_im(n) + c_re
  • z_im(n+1) = 2 * z_im(n) * z_re(n) + c_im
  • |z(n)| = z_re(n) * z_re(n) + z_im(n) * z_im(n)

Mathematik in Scratch

Die Gleichungen schauen in Scratch dann wie folgt aus (vergleiche auch o.g. Artikel):

large_julia4_-0,7467_0,3515.jpg scratch_julia_formel.jpg
large_julia5_-0,8_0,156.jpg


large_julia6_0,687_0,312.jpg

Für jeden Punkt wird für eine maximale Anzahl an Iterationen getestet, ob und bei welcher Iteration der Wert einen Grenzwert überschreitet (in diesem Fall = 4). Wenn er den Grenzwert überschritten wird, divergiert der Punkt in Richtung Unendlich.

Berechnung der ganzen Ebene

Die verschiedenen Variablen werden in einem zentralen "Management Objekt" festgelegt, während die Berechnungen dann in mehreren "Rechenobjekten" erfolgen. Scratch kann 480 x 360 Punkte darstellen. Eine Schleife, über diese Ebene, die für jeden Punkt mit einer sinnvollen Anzahl an Iterationen die Werte berechnet, dauert entsprechend lange. Scratch ist nicht wirklich performant und nutzt die vorhandenen CPUs nicht gut aus. Daher liegt es nahe, mehrere "Bahnen" der Ebene parallel zu berechnen. Hierfür wurde in dem o.g. Artikel das Berechnungsobjekt mehrmals kopiert und dann per Hand in jedem Objekt eine andere Bahn konfiguriert.

CSMA/CD

Den Ansatz, die Berechnungsobjekte zu kopieren, gefiel mir. Die Idee, jedes Objekt dann einzeln anfassen zu müssen, aber gar nicht. Ich war nur bereit, einmal anzugeben, wie viele Objekte es gibt. Den Rest sollen die Berechnungsobjekte bite untereinander ausmachen. Die Lösung hierfür wurde allerdings aufwendiger, als die Definition des Berechnungsalgorithmus. Als Vorbild habe ich mir das CSMA/CD-Verfahren genommen (CS = Carrier Sense, MA = Multiple Access, CD = Collision Detect - wer denkt hierbei noch an die vergessenen Terminatoren am schwarzen Kabel? Outings gerne unten in den Kommentaren!).

Ich habe in Scratch zwei Listen definiert:

  • "spuren": der kleinste x-Wert der Spur. Die Breite der Spur kann aus der Anzahl der parallelen Threads (Objekte) berechnet werden
  • "spur-thread": welcher Thread (= Berechnungsobjekt) berechnet welche Spur

Die beiden Listen werden zu Beginn im "master"-Objekt gefüllt. Die eine mit den unterschiedlichen x-Werten, die andere mit Nullen. Dann wird ein Signal an alle Berechnungsobjekte geschickt, die Berechnung zu starten.

julia_arbeitsteilung.jpgJedes Berechnungsobjekt macht dann:

- Wähle zufällig eine Slotnummer (t_nr)

- Erzeuge eine "eindeutige" ID-Nummer

- Schreibe diese ID in die Liste "spur-thread" an die Stelle t_nr

- Warte eine zufällige Zeitspanne

- Dann schaue, ob an der Stelle t_nr immer noch die eigene ID steht:
  -> Wenn ja: das Objekt hat seinen Slot gefunden
  -> Wenn nein: probiere das gleiche Verfahren erneut

Nach einiger Zeit zeigt sich, dass nur noch wenige Slots frei sind und es sehr lange dauert, bis die letzten Slots vergeben sind (der Zufallszahlengenerator von Scratch ist auch nicht ideal). Daher wird nach einer gewissen Zeitspanne (5* Anzahl der Threads) die neue Slotnummer nicht mehr zufällig ermittelt, sondern in der Liste gezielt nach freien Slots gesucht.

Jetzt kann man das Berechnungsobjekt beliebig oft kopieren und muss nur noch einmal vorgeben, wie viele Berechnungsobjekte es gibt. Getestet habe ich es mit bis zu 40 parallelen Berechnungsobjekten.

Fazit

Es geht. Auch komplexe Aufgaben lassen sich mit einer Programmieroberfläche lösen, die dafür definitiv nicht gedacht war. Es fällt aber auf, dass das Innere der Bilder, das eigentlich tief schwarz sein sollte, ab und zu  dunklen Streifen zeigt. Das lässt Rundungsfehler vermuten. Die Berechnung eines Bildes dauert auch auf einer Multi-Core-CPU mit 40 parallelen Rechenobjekten noch fast eine Stunde. So ganz optimal scheint Scratch für numerische Operationen dann doch nicht zu sein :-)

Wer das Programm testen will, kann es am Ende dieser Seite herunterladen. Ich freue mich über Anregungen oder andere Grafiken von in Scratch berechneten Fraktalen. 

Tags: 

Dateianhang: