Institut für Informatik
Michael Wand
Christian Ali Mehmeti-Göpel
Wintersemester 2020/21 • DIGITAL
Blatt 03
Aufgabe 03
Einführung in die SoftwareentwicklungAufgabe Ein größerer Ganzzahltyp
Letzte Änderung: 07. December 2020, 14:33 Uhr20 Punkte — im Detail
Ansicht: |
Ziel dieser Aufgabe
Aus der Vorlesung und dem letzten Blatt wissen Sie, dass alle Standarddatentypen für Ganzzahlen in C++ nur begrenzt viele Werte annehmen können. Im Normalfall reichen diese auch aus. Wir werden uns jetzt aber eine Möglichkeit anschauen, wie man diese Einschränkung umgehen kann, indem wir eine einen größeren Ganzzahlentyp definieren. Konkret definieren wir eine vorzeichenlose 192-Bit-Zahl, die sich aus drei 64-Bit-Zahlen zusammensetzen wird. An sich kann das Verfahren aber problemlos auf beliebige große Ganzzahlentypen verallgemeinert werden. Die Schwierigkeit dieser Aufgabe besteht darin, die Rechenregeln auf diese Repräsentation anzuwenden.
Als interne Repräsentation verwenden wir ein dreielementiges Array parts aus Werten vom Typ uint64_t. Unsere dargestellte Zahl ergibt sich dann durch \(\texttt{parts[2]} \cdot 2^{2 \cdot 64} + \texttt{parts[1]} \cdot 2^{1 \cdot 64} + \texttt{parts[0]} \cdot 2^{0 \cdot 64}\), wir rechnen also effektiv mit einer Zahl in der Basis \(2^{64}\).
Um den Einstieg in die Implementierung etwas zu vereinfachen, haben wir den Header für Sie bereits vollständig implementiert. Außerdem geben wir zwei Konstruktoren vor.
#include <cstdint>
struct uint192 {
uint64_t parts[3];
uint192();
uint192(uint64_t hi, uint64_t mid, uint64_t lo);
void print_binary();
void print_hex();
void print_decimal();
};
uint192 operator +(const uint192 &lhs, const uint192 &rhs);
uint192 operator *(const uint192 &lhs, const uint192 &rhs);
uint192 operator <<(const uint192 &num, uint64_t shift);
uint192 operator >>(const uint192 &num, uint64_t shift);
bool operator ==(const uint192 &lhs, const uint192 &rhs);
bool operator !=(const uint192 &lhs, const uint192 &rhs);
bool operator <(const uint192 &lhs, const uint192 &rhs);
bool operator <=(const uint192 &lhs, const uint192 &rhs);
bool operator >(const uint192 &lhs, const uint192 &rhs);
bool operator >=(const uint192 &lhs, const uint192 &rhs);
So etwa könnte Ihre cpp-Datei aussehen:
#include "uint192.h"
uint192::uint192() : uint192(0, 0, 0) {}
uint192::uint192(uint64_t hi, uint64_t mid, uint64_t lo) {
parts[0] = lo;
parts[1] = mid;
parts[2] = hi;
}
// YOUR CODE HERE
int main() {
// ...
}
- Implementeren Sie einen zusätzlichen Konstruktor mit nur einem Argument, der aus einem
uint64_tdas gleichwertigeuint192macht. - Für die Addition müssen Sie sich zuerst überlegen, wie Sie den Übertrag zwischen zwei Stellen realisieren. Ein erster Ansatz könnte wie folgt aussehen (Beispiel für 16-Bit-Zahlen):
uint16_t a = 43690; // C++14 erlaubt auch a = 0b1010101010101010; uint16_t b = 32768; // C++14 erlaubt auch b = 0b1000000000000000; uint16_t c = a + b; // c == 10922 oder c == 0b0010101010101010; uint16_t carry = ((a >> 15) + (b >> 15)) >> 1;
Machen Sie sich an einigen Beispielen klar, was der Code macht.
Dieser Ansatz funktioniert aber für einige Eingaben nicht!- Geben Sie eine Belegung für
aundban, für die der Code nicht den korrekten Übertrag liefert. - Überlegen Sie sich einen anderen Weg, der Ihnen zuverlässig die Summe zweier
uint64_tinklusive Übertrag liefert. Erklären Sie kurz, etwa als gut gekennzeichneter Kommentar im Code, wie Ihre Methode funktioniert. - Implementieren Sie damit
operator+.
uint192 a(3, ~7ull, ~42ull); uint192 b(2, 21, 46); uint192 c(6, 14, 3); // es sollte gelten: a + b == c - Geben Sie eine Belegung für
- Die Shift-Operatoren kennen Sie noch vom letzten Blatt. Implementieren Sie
operator<<undoperator>>wie im Header vorgegeben. Denken Sie daran, dass jetzt Verschiebungen um mehr als 64 Bit möglich sind!
Code zum Testenuint192 a(3, ~7ull, ~42ull); uint192 b(15, (~7ull << 2) + 3, ~42ull << 2); uint192 c(0, ~1ull, 4611686018427387893ull); // es sollte gelten: a << 2 == b // es sollte gelten: a >> 2 == c - Überlegen Sie sich, wie man die Multiplikation zweier Zahlen aus Shifts und Additionen zusammensetzen kann. Implementieren Sie auf diese Weise
operator*.
Falls Ihnen kein Ansatz dafür einfällt, erinnern Sie sich an schriftliches Multiplizieren im Dezimalsystem:Rechne 214 * 123 = 26322 * | 1 2 3 --+----------------- 2 | 2 4 6 1 | 1 2 3 4 | 4 9 2 --+----------------- + 2 6 3 2 2
Versuchen Sie, in dem Beispiel zu erkennen, wo Shifts und wo Additionen verwendet werden.
Bonus: Multiplikation durch Shifts und Additionen ist in diesem Fall nicht die effizienteste Lösung. Wenn Ihnen eine bessere Lösung zur Multiplikation einfällt, dürfen Sie auch diese stattdessen implementieren. - Implementieren Sie die Vergleichsoperatoren, also
operator==,operator!=,operator>,operator>=,operator<undoperator<=. Wenn Sie sich Arbeit sparen wollen, überlegen Sie, welche Operationen an bereits implementierte Operatoren delegiert werden können. - Natürlich wollen wir unsere Zahl auch lesbar ausgeben. Implementieren Sie zu diesem Zweck
print_binary, um die Zahl in Binärdarstellung auf der Konsole auszugeben sowieprint_hex, um die Zahl in Hexadezimaldarstellung auf der Konsole auszugeben.
- Zuletzt wollen wir etwas sinnvolles mit unserer Zahl machen. Die Fakultät von 45 lässt sich nicht in einem
uint64_tspeichern, wohl aber in einemuint192. Schreiben Sie eine Funktionuint192 factorial(uint64_t n), die die Fakultät von n in einemuint192berechnet.
Geben Sie in Ihrermain-Methode die Fakultät von 45 aus. - Bonus: Die Zahl in Binär bzw. Hexadezimaldarstellung auszugeben ist zwar hilfreich zum Debuggen, meistens interessiert uns jedoch die Zahl in Dezimaldarstellung.
Implementieren Sie also eine Funktionprint_decimal, um die Zahl in Dezimaldarstellung auf der Konsole auszugeben. Sie können hierzu ein Verfahren implementieren, das üblicherweise in Hardware realisisert wird. Das ist allerdings eher umständlich. Daher schlagen wir Ihnen eine andere Lösung vor, die einfacher zu implementieren ist:
In den unten bereitgestellten Dateien befindet sich einstructnamesuint192divmod10. Dieses implementiert die Division einesuint192durch 10 mit Rest. Möchte man eine Zahl n durch 10 dividieren, kann man mittelsuint192divmod10 result(n);einuint192divmod10-Objekt anlegen und dann überresult.quotientundresult.remainderauf den Quotienten und den Divisionsrest zugreifen. Durch iteriertes Dividieren können Sie die Dezimalstellen einzeln extrahieren.
uint192divmod10.h
#include <cstdint>
struct uint192divmod10 {
uint192 quotient;
uint64_t remainder;
explicit uint192divmod10(const uint192 ÷nd);
};
uint192divmod10.cpp
#include "uint192.h"
#include <iostream>
// für die Bonusaufgabe
constexpr uint64_t HALF = static_cast<uint64_t>(0xffffffffull);
constexpr uint64_t SHIFT = static_cast<uint64_t>(32u);
uint192divmod10::uint192divmod10(const uint192 ÷nd) {
remainder = 0;
for (uint64_t i = 0; i < 3; ++i) {
uint64_t part = 2 - i;
uint64_t upper_dividend = remainder << SHIFT | dividend.parts[part] >> SHIFT;
uint64_t upper_quotient = upper_dividend / 10;
remainder = upper_dividend % 10;
uint64_t lower_dividend = remainder << SHIFT | (dividend.parts[part] & HALF);
uint64_t lower_quotient = lower_dividend / 10;
remainder = lower_dividend % 10;
quotient.parts[part] = upper_quotient << SHIFT | lower_quotient;
}
}
// Bonusaufgabe Ende