Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Parallele Mandelbrotmenge

Wiederholung der Komplexen Zahlen:

Bevor wir uns der Mandelbrotmenge selbst widmen, sollen an dieser Stelle nochmals die komplexen Zahlen wiederholt werden.

Die komplexen Zahlen sind die Menge \[\mathbb{C} := \mathbb{R} + i\cdot \mathbb{R} := \{a+ib \,|\, a,b\in \mathbb{R}\},\] die mit der folgenden Struktur versehen sind: Eine komplexe Zahl \(z = a+ib\) besteht damit aus zwei reellen Zahlen \(a,b\)¹ und der imaginären Einheit \(i\), die die Eigenschaft \(i^2=-1\) besitzt. Aus dieser Eigenschaft und der herkömmlichen Multiplikation und Addition auf reellen Zahlen folgen die Rechenregeln: \[\begin{aligned} \text{Addition:}\quad &(a+ib)+(c+id) &= \quad &\, (a+c) + i(b+d)\\ \text{Multiplikation:}\quad &(a+ib)\cdot(c+id) &= \quad &\, (ac-bd) + i(bc+ad)\\ \text{Absolutbetrag (entspr. Länge im } \mathbb{R}^2\text{):} \quad &|(a+ib)| &= \quad &\, \sqrt{a^2 + b^2} \end{aligned}\] Komplexe Zahlen sind glücklicherweise bereits fest in C++ implementiert. Hier ein Beispiel aus der Dokumentation:

#include <iostream>
#include <iomanip>
#include <complex>
#include <cmath>

int main()
{
    using namespace std::complex_literals;
    std::cout << std::fixed << std::setprecision(1);

    std::complex<double> z1 = 1i * 1i;     // imaginary unit squared
    std::cout << "i * i = " << z1 << '\n';

    std::complex<double> z2 = std::pow(1i, 2); // imaginary unit squared
    std::cout << "pow(i, 2) = " << z2 << '\n';

    double PI = std::acos(-1);
    std::complex<double> z3 = std::exp(1i * PI); // Euler's formula
    std::cout << "exp(i * pi) = " << z3 << '\n';

    std::complex<double> z4 = 1. + 2i, z5 = 1. - 2i; // conjugates
    std::cout << "(1+2i)*(1-2i) = " << z4*z5 << '\n';
}

Mandelbrotmenge:

Wir beginnen mit einer beliebigen komplexen Zahl \(c\in \mathbb{C}\) und definieren die Folge

Die Mandelbrotmenge \(M\) ist die Menge, für die der Absolutbetrag dieser Folge nach oben hin beschränkt ist, mathematisch ausgedrückt:

Aufgabe

1. Stellen Sie die Mandelbrotmenge mithilfe einer Qt-basierten grafischen Oberfläche dar.
   
   Hinweis: Verwenden Sie anfangs eine geringere Auflösung, damit die Berechnungen schneller sind.
   
   Hier noch ein paar Tipps:
   • Erstellen Sie zuerst eine Qt-GUI, die ein Bild anzeigen kann. (Schauen Sie dazu noch einmal in die Anlage zu Blatt 10.)
   • Generieren Sie nun ein Gitter auf den komplexen Zahlen. Das Mandelbrotmännchen ist besonders gut im Intervall \([-2,1]\times [-1,1]\) zu sehen; starten Sie also in diesem Intervall.
   • Implementieren Sie die Folge \(z_n\) für jeden Gitterpunkt in dem damit abgetasteten Koordinatensystem. (Für jeden Pixel im Bild a.k.a Gitterpunkt wird die Folge also separat berechnet).
     
     Ferner werden wir \(n\) nicht bis unendlich laufen lassen können; limitieren Sie also die maximal Anzahl an zu berechnenden Folgenelementen. (Eine Größenordnung von \(n=100\) liefert gute Ergebnisse und hat eine relativ kurze Berechnungsdauer.)
     
     Ob die jeweilige Zahl tatsächlich in der Mandelbrotmenge enthalten ist können wir also nicht bestimmen. Was wir jedoch tun können ist zu zählen, wie lange es dauert, bis die Folge die Grenze \(|z_n| > 2\) überschritt. Initialisieren Sie also vor der Schleife ein Array, das die gleichen Abmessungen hat wie das Gitter selbst und zählen Sie in genau den Einträgen hoch, in denen der Betrag der komplexe Zahl noch nicht über die 2 gekommen ist.
   • Wir wollen nun abhängig davon, wie groß die Zahl geworden ist eine Farbe festlegen. Dies kann auf verschiedene Arten und Weisen gelöst werden. Am Einfachsten ist es zwischen zwei Farben \(c_i = (r_i, g_i, b_i), i=1,2\) zu interpolieren, \[ c_1 \cdot t + c_2 \cdot (1-t), t\in [0,1], \] oder noch einfacher: schwarz für kleine Werte und Weiß für große Werte zu wählen.
2. Nun zum Bezug Parallelisierung: Implementieren Sie auch hier das parallele Rechnen aus Aufgabe 1; Sorgen Sie dafür, dass das Bild in gleichmäßige quadratische Blöcke unterteilt wird und nun unabhängige Threads das Bild bemalen sobald die Rechnungen fertig sind. Es gibt hierbei viele Möglichkeiten das Problem zu lösen. Jede Lösung, bei der man sieht, dass Abschnitte abhängig von der Berechnungsdauer der Menge unterschiedlich schnell werden ist korrekt.
   
   Hinweis: Sie können mit repaint das Fenster zwischendurch neuzeichnen.
3. Bonus Sie werden sicher bemerkt haben, dass einige Teile des Bildes deutlich schneller fertig sind als andere. Überlegen Sie sich ein einfaches Schema, wie diese Last verteilt werden kann und implementieren Sie dies.
4. Bonus: Was passiert, wenn Sie die Anzahl der Schleifendurchläufe erhöhen / senken?
5. Bonus: Was passiert, wenn Sie die Schranke 2 verändern? Können Sie erklären warum Sie das beobachten?
6. Bonus:
   Fügen Sie nun Maus-Interaktion hinzu, indem Sie den Nutzer die Möglichkeit geben hinein- und hinauszuzoomen und das Bild zu verschieben. Sie können dazu beispielsweise das MousePressEvent verwenden. (Siehe Skript: e.X(),e.Y() liefert Ihnen die Koordinaten in Ihrem selbstdefinierten Gitter.
   
   Achten Sie bei der Anzeige (und vor allem beim Zoomen) darauf, dass die x-Achse und die y-Achse gleich skaliert sind, da sonst das Ergebnis verzerrt aussieht.

[1] Die komplexen Zahlen unterscheiden sich von der Menge \(\mathbb{R}\times\mathbb{R}\) der zwei-dimensionalen reellen Vektoren nur dadurch, dass zusätzlich ein „richtiges“ Produkt zwischen Paaren von solchen Vektoren (also den komplexen Zahlen) definiert ist. Die Schreibweise mit dem „\(i\)“ ist historisch bedingt und verwirrt vielleicht eher.