Überlauf bei ganzzahligen Datentypen

English

Der Umgang mit ganzzahligen Datentypen (Integers u.ä.) gehört zu den grundlegenden Fähigkeiten unserer Rechner. Das kann jede gängige Programmiersprache seit den 50er Jahren.

Es gibt jedoch einige Aspekte, wie sich die Verwendung der Ganzzahlen in verschiedenen Programmiersprachen unterscheidet.

Umgang mit dem Überlauf

Für die Größe der Ganzzahlen gibt es mehrere Ansätze:

1. Ganzzahlen werden automatisch mit so vielen Stellen gespeichert, wie nötig sind.  Wenn durch eine Rechnung ein Ergebnis entsteht, das mehr Stellen benötigt, werden entsprechend viele Stellen bereitgestellt.  Man muss sich also nicht um die Größe und den Überlauf kümmern, außer man schöpft den Hauptspeicher aus.  Beispiele: Common Lisp, Ruby
2. Ganzzahlen haben eine bestimmte Anzahl von Bits.  Wenn durch eine Berechnung ein Ergebnis entsteht, das mit der vorgegebenen Anzahl von Bits nicht ausdrückbar ist, werden die oberen Bits einfach weggeworfen, ohne dass man davon etwas merkt. Außer man macht nach jeder Operation aufwendige Überprüfungen.  Beispiele: C, Java
3. Ganzzahlen haben eine bestimmte Anzahl von Bits.  Wenn durch eine Berechnung ein Ergebnis entsteht, das mit der vorgegebenen Anzahl von Bits nicht ausdrückbar ist, wird eine Exception ausgelöst.  Mir fallen im Moment keine Beispeiele ein, die diesen Weg gewählt haben.
4. Ganzzahlen haben eine bestimmte Anzahl von Bits.  Für Ergebnisse von Multiplikation wird ein Typ verwendet, der doppelt so viele Bits hat.  Für Ergebnisse von Addition wird ein Typ mit genauso vielen Bits verwendet, aber man erhält zusätzlich noch ein Carry-Bit für den Übertrag.  Damit lassen sich durch interiertes Addieren von Teilen einer langen Zahl auch Langzahlen mit beliebig vielen Stellen addieren.  Multiplizieren, Dividieren und Subtrahieren von Langzahlen lässt sich auch auf ähnliche Weise bewerkstelligen.  Beispiel: Assembler
5. Ganzzahlen werden ganz weggelassen und man behilft sich mit Fließkommazahlen.  Beispiel: Lua

Bewertung

Lösung 1 ist das, was man für Applikationsentwicklung haben sollte.  Das Zählen von Bits, Überprüfen von Überläufen u.s.w. ist für die Entwicklung von Business-Logik einfach abwegig.  Für mich durchaus ein Argument, Ruby (oder Lisp) vor Java zu bevorzugen, wenn es um Applikationsentwicklung geht.

Die Lösung 2 ist einfach unsinnig und wohl der größte Designfehler von C und Java.  Rundung ist etwas, was man noch akzeptieren kann, aber dass stattdessen die oberen Stellen stillschweigend weggeworfen werden, ist ein „Feature“, mit dem der durchschnittliche Software-Entwickler nicht umgehen will bzw. das man auch ignoriert, weil es ja meistens gut geht und man mit dem Fehler nicht rechnet.  Außerdem wirft man mit dem Carry-Bit wichtige Information zur Implementierung von Lösung 1 weg, was bei rechenintensiver Software ungefähr eine Verdopplung der Laufzeit nach sich zieht.

Lösung 3 wäre im Gegensatz zu Lösung 2 schon grundsätzlich brauchbar, ich halte aber Lösung 4 für besser.

Lösung 4 ist akzeptabel für Low-Level-Programmierung, als nicht für Applikationsentwicklung.  Manchmal braucht man wirklich Bits- und Bytes explizit, um z.B. externe Hardware anzusteuern, Netzwerkprotokolle auf den untersten Schichten zu implementieren o.ä.  Die Möglichkeit, ein Carry-Bit dabei zumindest optional berücksichtigen, kann nicht schaden.  Leider ist dies meines Wissens (fast?) nur in Assemblersprachen so umgesetzt und wenn man eine Langzahlarithmetik zum Beispiel für Ruby implementiert, dann muss man in C ein Gebastel auf der Grundlage von Lösung 2 in Kauf nehmen, kann aber für bekannte gängige CPUs zusätzlich eine etwa doppelt so schnelle Implementierung in Assembler auf der Grundlage von Lösung 4 anbieten.

Lösung 5 ist am falschen Ende gespart.

Fazit

Viele Software-Entwickler meinen, dass sie das Thema nicht interessiert oder nicht betrifft.  Ich empfehle aber, dieses Thema ernst zu nehmen.  Die Fehler durch den stillschweigenden Arithmetiküberlauf sind sehr schwierig zu finden, weil sie überall auftreten können und weil sie beim Testen womöglich nicht einmal auffallen, da erst in der Produktion Daten auftreten, die den Überlauf auslösen. Nur Lösung 1 erlaubt es dem Applikationsentwickler, sich die Beschäftigung mit der Überlaufproblematik weitgehend zu sparen.