Rechtwinklige Dreiecke und parallel_for

Und wieder steht etwas Schulmathematik auf dem Programm, dieses Mal geht es um rechtwinklige Dreiecke. Für derartige Dreiecke gibt es den Satz des Pythagoras, er fällt eine Aussage zu den Seitenlängen solcher Dreiecke. Wir wollen im Folgenden nur Dreiecke betrachten, deren Seitenlängen ganzzahlig sind.

Schreiben Sie ein C++–Programm, das für folgende Fragestellung eine Antwort findet: Für welchen Umfang p mit p <= 2000 ist die Anzahl der verschiedenen rechwinkligen Dreiecke mit ganzzahligen Seitenlängen a, b und c am größten?

Hinweis: Die Aufgabenstellung stammt aus dem Repository „Project Euler”: Project Euler ist eine englischsprachige Website, sie enthält eine Reihe von Problemstellungen, die mit Hilfe von Mathematik und Programmierung gelöst werden können. Die Aufgabenstellung dieser Fallstudie finden Sie unter „Problem 39” vor.

Welche Parallelisierungsansätze sind für diese Aufgabenstellung denkbar? Implementieren Sie einen parallelen Algorithmus und vergleichen Sie die Laufzeiten der beiden Varianten. Mit Hilfe der Klassen std::thread, std::function, std::mutex und std::lock_guard gehen wir auf die Realisierung einer Funktion parallel_for ein.

[Read More]

Kettenrechnen

Mit dem Kettenrechnen kehren wir zu den Ursprüngen unserer Grundschulzeit zurück. Für diejenigen unter Ihnen, die dieses Thema aus Ihrem Gedächtnis verdrängt haben: Jede Kettenrechnung beginnt mit einer normalen Rechenaufgabe (z.B. „1 + 3”). Das Resultat muss im Gedächtnis behalten werden, denn es folgt eine weitere Operation (z.B. „* 5”), welche jeweils zum vorhergehenden Resultat gerechnet wird. Das neue Zwischenresultat merkt man sich ebenfalls wieder für die nächste Operation usw. usw. So verlängert sich die „Rechenkette” immer weiter. Im Beispiel der Kettenrechnung 1 + 3 * 5 - 2 * 2 - 8 / 2 sollte man 14 als Endergebnis erhalten.

Entwickeln Sie eine Funktion calc, die eine Kettenrechnung als Parameter übergeben bekommt und ihr Resultat zurückliefert:

int calc (const std::string& chain);

Offensichtlich führen viele Wege zum Ziel einer ansprechenden Realisierung. Im Lösungsteil finden Sie Lösungsansätze vor, die generische Funktionen, heterogene STL-Container, reguläre Ausdrücke und vieles mehr anwenden.

[Read More]

Variadisch + Generisch = Folding + Rekursion: Wie bitte?

Beginnend mit C++ 11 haben eine Reihe von neuen Sprachfeatures Einzug in die Programmiersprache C++ gefunden, die wir in ihrer Gesamtheit unter dem Begriff C++ 20 subsumieren können:

  • Lambda-Funktionen
  • Generische Funktionen
  • Folding
  • Variadische Templates
  • Parameter Packs
  • Rekursive Parameter Pack Expansion
  • IIFE

Sicherlich muss man all diese Konzepte erst einmal alleinstehend für sich betrachten und studieren, um sie zu erfassen und zu verstehen. Dies setze ich für das Studium dieser Fallstudie voraus. Mir kommt es darauf an, all diese Techniken miteinander zu verknüpfen! Genau dies wollen wir an Hand einer Reihe von Beispielen in dieser Fallstudie näher betrachten.

[Read More]

Expression Templates / Lazy Evaluation

Wir betrachten in dieser Fallstudie das Thema „Expression Templates” und damit in Zusammenhang stehend die Technik der genannten „Lazy Evaluation”. Auf einen einfachen Nenner gebracht: „Expression Templates” sind ein Anwendungsfall der Metaprogrammierung. Sie verschieben die Aus­wertung von Ausdrücken in eine separate Funktion, die zu einem späteren Zeitpunkt ausgeführt werden kann. An dieser Stelle wird der Begriff der „Lazy Evaluation” verständlich. Wir betrachten das Thema am Beispiel der Verknüpfung von Zeichenketten, also beispielsweise an einem Ausdruck in der Art

std::string result = "123"s + "ABC"s + "456"s + "XYZ"s + "789"s;

Mit „Expression Templates” lernen Sie einen alternativen Ansatz kennen, einen geschachtelten (arithmetischen) Ausdruck zu berechnen mit dem Vorteil, nahezu alle temporären Objekte zu vermeiden, die bei der klassischen Berechnung eines solchen Ausdrucks entstehen würden.

[Read More]

Benutzerdefinierte Literale: Übersetzungszeit oder Laufzeit?

Durch Überladen des so genannten Literaloperators operator"" lassen sich neue Formate für benutzerdefinierte Literale definieren. Diese setzen sich aus einem Standard-Literal und einem benutzerdefinierten Suffix zusammen. Damit kann man in einem C++–Programm beispielsweise schreiben:

100.5_kg
0xFF00FF_rgb
10010101_b

Wie sich benutzerdefinierte Literale in Ihrem Programm definieren lassen und welche Stolperfallen Sie dabei beachten sollten, können Sie in dieser Fallstudie nachlesen.

[Read More]
Cpp_17 

Being constexpr or not being constexpr: Konstante Ausdrücke in C++

Die Berechnung von Ausdrücken zur Übersetzungszeit wurde in C++–17 auf ein neues Niveau angehoben. Längst haben wir es nicht mehr mit nur konstanten Literalen oder einfachen Ausdrücken, bestehend aus einer Summation oder Multiplikation, zu tun. In C++–17 können zur Übersetzungszeit Variablen, Funktionen und auch ganze Klassen bzw. deren Objekte mit entsprechenden Konstruktoren zur Übersetzungszeit ausgeführt bzw. erzeugt werden.

Von Interesse ist dieser Aspekt in der Anwendung zum Beispiel für die Embedded Programmierung, wenn es darum geht, möglichst viele Daten vom Übersetzer berechnen zu lassen, um diese mit Hilfe des Kompilats in das ROM (Read-Only-Memory) einer speziellen Hardware zu packen.

Welche Möglichkeiten sich mit constexpr in C++ 17 eröffnen, zeigen wir an einer Reihe von Fallbeispielen in dieser Studie auf.

[Read More]
Cpp_17 

Parallele Suche nach Primzahlen mit “Hindernissen”

Die Suche nach Primzahlen – also Zahlen, die nur durch sich selbst und durch 1 teilbar sind – war lange Zeit eine der zentralsten Bestandteile der Zahlentheorie. Primzahlenjäger können neben den zahlreichen Erkenntnissen der Zahlentheoretiker heutzutage auf eine zusätzliche Hilfestellung zurückgreifen, den Computer. Wir wollen im Folgenden ein Programm entwickeln, das mit Hilfe mehrerer Threads zu zwei fest gegebenen natürlichen Zahlen n und m die Anzahl aller Primzahlen p mit npm bestimmt.

Für die Koordination der Threads setzen wir „Hindernisse” ein, also C++–20 std::latch-Objekte. Studieren Sie in dieser Anwendung, wie die Primzahlensuche mit mehreren Threads auf diese Weise koordinierbar ist.

[Read More]

Das Springerproblem

Das Springerproblem ist auf den Schweizer Mathematiker Leonhard Euler (1707 – 1783) zurückzuführen. Dieser stellte sich vor über 200 Jahren, genauer gesagt im Jahre 1758, die folgende Frage: „Gegeben sei ein leeres Schachbrett. Gibt es eine Zugfolge, mit der der Springer alle (schwarzen und weißen) Felder des Bretts genau einmal besucht?”.

Hmmm, eine gute Frage, wird sich der geneigte Leser jetzt sagen. Möglicherweise kann man sie innerhalb von wenigen Minuten selbst beantworten, schließlich ist ein Schachbrett mit seinen 8×8 Feldern nicht so wirklich groß. Stellt man nach einer ersten Phase euphorischen Suchens ernüchternd fest, dass das Problem doch nicht ganz so einfach zu lösen ist, kommt man vielleicht auf den revolutionären Gedanken, dem Problem mit Hilfe eines Softwareprogramms auf den Leib zu rücken. Dies ist natürlich möglich, wie wir in dieser Fallstudie am Beispiel von Modern C++ zeigen werden.

Neben der Implementierung einer Backtracking-Strategie betrachten wir auch Überlegungen, wie sich das Suchen von Zugfolgen parallelisieren lässt. Die Methode std::async und Objekte, die es „erst in der Zukunft” gibt (std::future<T>), kommen zum Einsatz.

[Read More]