Fakultäten, Binomialkoeffizienten und Herr Legendre

Die Fakultät ist in der Mathematik eine Funktion, die einer natürlichen Zahl n das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet: n! = 1 * 2 * 3 * … * n. In der Kombinatorik spielt die Fakultät ebenfalls eine große Rolle, weil n! die Anzahl der Möglichkeiten ist, unterschiedliche Gegenstände der Reihe nach anzuordnen. Bei diesen Überlegungen kommen auch Binomialkoeffizienten ins Spiel. Sie geben an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann.

Sowohl Fakultäten als auch Binomialkoeffizienten weisen eine unangenehme Eigenschaft auf: Ihre Werte können sehr schnell sehr groß werden – und sind damit in Variablen des Typs long oder size_t nicht mehr darstellbar. Ein Satz von Legendre verschafft hier Abhilfe: Er befasst sich mit der Frage, wie oft ein Primfaktor in der Primfaktorzerlegung von n! für ein n ∈ N vorkommt – um damit eine alternative Darstellung für Fakultäten und Binomialkoeffizienten zu ermöglichen, die das Problem des Überlaufs umgehen kann.

Wir betrachten in dieser Fallstudie die Berechnung von Fakultäten und Binomialkoeffizienten sowohl in ihrer klassischen Definition als auch mit Hilfe des Satzes von Legendre als Produkt von Primfaktorzerlegungen.

[Read More]

Umgekehrte polnische Notation (UPN)

Die Notation eines mathematischen Ausdrucks, wie wir ihn aus der Mathematik kennen, zum Beispiel 2 * (7 + 5), bezeichnet man als Infix-Notation. Das Gegenstück dazu heißt Postfix-Notation oder UPN (umgekehrte polnische Notation, engl. reverse polish notation oder abgekürzt RPN). Die umgekehrte polnische Notation wurde 1920 von dem Polen Jan Lukasiewicz erfunden, um mathematische Ausdrücke ohne Vorrangregeln (Klammern) schreiben zu können.

In dieser Fallstudie behandeln wir einen Taschenrechner für arithmetische Ausdrücke in UPN-Darstellung. Reguläre Ausdrücke (std::sregex_iterator, smatch) und Type Traits (std::is_integral, std::is_floating_point) fließen neben anderen Modern C++–Sprachmitteln in der Implementierung mit ein.

[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 

Spiegelzahlen – auch Palindrome genannt

Eine natürliche Zahl, die identisch ist mit ihrer Kehrzahl wie z.B. 131, wird Palindrom genannt. In dieser Fallstudie betrachten wir eine nicht deterministische Methode zur Berechnung beliebig großer Palindrome.

Die in C++ eingebauten elementaren Datentypen (wie int oder long) stellen keine echte Hilfe dar, wenn wir potentiell unendlich große Palindrome berechnen wollen. Zu diesem Zweck entwerfen wir im Folgenden zunächst eine Klasse Number, mit deren Hilfe sich sehr große Zahlen darstellen lassen. Im Anschluss daran gehen wir auf die Klasse PalindromCalculator ein, um Palindrome zu berechnen.

[Read More]

Exakte Arithmetik ganzer Zahlen

Die ganzzahligen Standarddatentypen in C++ wie short, int usw. besitzen allesamt die Eigenschaft, dass ihr Wertebereich limitiert ist. Für viele Anwendungen ist dies nicht nachteilig, da sich speziell mit den Datentypen int und long oder auch size_t ziemlich große Zahlen darstellen lassen. Für manche Anwendungen ist die Verarbeitung von ganzen Zahlen beliebiger Größe jedoch unabdingbar. Wir stellen im Folgenden eine Klasse BigInteger vor, die eine exakte Arithmetik vorzeichenbehafteter ganzer Zahlen beliebiger Größe zur Verfügung stellt.

[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]