namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


anwenden:ganzzahl_impl

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

anwenden:ganzzahl_impl [2014-07-13 16:14] (aktuell)
Zeile 1: Zeile 1:
 +====== 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 [[anwenden:ganzzahl|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 [[anwenden:rechnen|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 [[anwenden:ganzzahl_cpp|Implementierung]] bleibt für den Anwender der
 +[[anwenden:ganzzahl|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, 
 +[[anwenden:ganzzahl_test|Tests]] sorgfältig zu planen und durchzuführen.
 +
  
anwenden/ganzzahl_impl.txt · Zuletzt geändert: 2014-07-13 16:14 (Externe Bearbeitung)