no way to compare when less than two revisions

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

@@ 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.