namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:ganzzahl_impl

Ganzzahl : Implementierung beliebig genauer Ganzzahlen

Wer die Weisheit sucht, ist ein Weiser.
Wer glaubt, sie gefunden zu haben, ist ein Narr.
— Seneca

Gesucht ist eine korrekt und schnell arbeitende Lösung. Warum probierst du es nicht selbst? Hinter der Deklaration char* data; in der Klassendefinition steht die ganze Welt der Möglichkeiten offen. Mehrere Ansätze sind denkbar.

Der einfachste ist, die Zahlen als Zifferzeichenketten zu speichern, wobei negativen Zahlen das Minuszeichen vorangestellt ist. Auf diese Weise sollte die Ganzzahlarithmetik als schriftliches Rechnen wie in der Grundschule formulierbar sein. Das Debuggen im vertrauten Dezimalsystem ist leichter. Für den Entwurf der Algorithmen kann das nützlich sein. Insbesondere die Division durch mehrstellige Zahlen ist anspruchsvoller als es auf den ersten Blick scheint.

Hinweise zur Implementierung

Für ernsthafte Anwendungen ist eine speichersparende und effiziente Umsetzung erforderlich. Der dynamische Hauptspeicher ist zwar groß, aber nicht unbeschränkt. Bei hoher Speicherauslastung steigt die Zahl der Zugriffe zur Auslagerungsdatei (swap partition). Die Systemleistung sinkt dann deutlich. Speicher- und Laufzeiteffizienz bedingen sich gegenseitig.

Basiswechsel

Auf heutigen binären Computern ist ein Basiswechsel vorteilhaft. Warum lohnt sich das trotz der zusätzlichen Mühe des Umrechnens bei Ein- und Ausgaben? Die Dezimaldarstellung einer Zahl ist verschenderisch: Eine Dezimalziffer nimmt nur 10 von 256 möglichen Zeichenwerten an. Statt 8 Bit werden durchschnittlich ld 10 = 3,322 Bit je Ziffer genutzt. Im 256er Zahlsystem (Ziffern 0..255) sind die Zahlen weniger als halb so lang. Auf einem binär arbeitenden Rechner wird dann der Speicher optimal genutzt.

Mit der Basis 65536 = 0x10000 halbiert sich die Ziffernzahl nochmals (bei doppelt so breiten Ziffern: 16 Bit). Da fast alle Rechenoperationen ziffernweise arbeiten, werden für Zahlen mit weniger Ziffern auch weniger Schleifendurchläufe benötigt. Beim Multiplizieren und Dividieren wirkt sich das sogar quadratisch auf die Rechenzeit aus (zwei ineinander geschachtelte Schleifen). Für die Ziffernbreite gibt es allerdings auch eine Obergrenze: die Verarbeitungsbreite der Maschine (Registergröße).

Verzögertes Kopieren

Bei jeder Wertübergabe wird der Speicher kopiert. Bei großen Zahlen ist dies ein aufwendiger Prozess. In manchen Fällen wird ein Wert viele Male kopiert, aber nie verändert. Solche Variablen können auf einen gemeinsamen Speicherblock zugreifen. Erst die letzte darauf zugreifende Variable gibt den dynamischen Speicher wieder frei. Dazu muss mitgezählt werden, wieviele Variablen auf diesen Speicher zugreifen (Referenzzähler). Ändert eine Variable ihren Wert, dürfen die anderen Werte jedoch nicht mitgeändert werden. Vor der Wertänderung muss eine Kopie des Speichers vereinzelt werden. Diese Technik wird als "lazy copying" oder "copy on write" bezeichnet.

Speicherblockgröße

Speicherblöcke können nicht vergrößert werden. Braucht eine Zahl eine Ziffer mehr, muss neuer Speicher angefordert, der alte Inhalt umkopiert und der alte Speicher freigegeben werden. Dieser aufwendige Vorgang sollte möglichst selten stattfinden. Zu diesem Zweck wird unter Umständen vorsorglich mehr Speicherplatz bereitgestellt als tatsächlich gebraucht wird. "Überflüssige" Ziffern müssen nicht unmittelbar freigegeben werden. Erst beim Umkopieren (lazy copy) wird soweit wie nötig eingekürzt.

Von der Speicherverwaltung werden nur Blöcke einer bestimmten Grundgröße oder Vielfache davon angefordert. Diese Maßnahme wirkt der Speicherfragmentierung entgegen. Beim Anfordern von Speicher steigt die Wahrscheinlichkeit, wieder einen freien Block passender Größe zu finden, auch nach längerer Nutzung.

Datenaufbau

Zu einer Ganzzahl müssen also Anzahl der Referenzen, aktuelle und ohne Reallokation mögliche Größe, Vorzeichen und die Ziffernfolge selbst gespeichert werden. Die Länge der Ziffernfolge ist erst zur Laufzeit (dynamisch) bestimmbar.

"Magische" Werte

Die Zahl 0 (in Worten: Null) kommt so oft vor, dass es Verschwendung wäre, jedesmal einen eigenen Speicherblock dafür bereitzustellen, etwa wenn ein Feld von Ganzzahlen erzeugt wird. Standardkonstruktoren greifen auf eine gemeinsame Darstellung des Nullwertes zu, die von außen nicht zugänglich sein darf. Eine globale Variable darf die Nulldarstellung jedoch nicht sein, weil die Initialisierungsreihenfolge über Modulgrenzen hinweg nicht steuerbar ist. Ein zweiter Grund für eine spezielle Darstellung der Null ist, dass +0 und -0 nicht unterschieden werden. Es gibt nur eine Null. Zu allen anderen ganzen Zahlen n gibt es ein Entgegengesetztes -n.

Es ist zur Laufzeitverkürzung sinnvoll, noch zwei weitere besondere Werte schnell greifbar zu haben:

  • die Darstellung der Zahl 1 für Inkrement und Dekrement,
  • die Zahlenbasis b selbst als Ziffernfolge [1|0] zur Basis b zwecks Ganzzahlkonvertierung.

Geheimnisprinzip

Die Implementierung bleibt für den Anwender der Klassenschnittstelle hinter einem Zeiger char* verborgen. Diese Maßnahme zielt darauf, Anwender von unerwünschten Direktzugriffen abzuhalten. Erkauft wird sie durch bewußt eingesetzte Typecasts, ein Grund mehr, Tests sorgfältig zu planen und durchzuführen.

anwenden/ganzzahl_impl.txt · Zuletzt geändert: 2014-07-13 16:14 (Externe Bearbeitung)