Programmiertechnik/Rechnerarithmetik
- 20min
- mittel
- gute Programmierkenntnisse
Stellt man mithilfe eines Computerprogramms oder beim Programmieren in einer beliebigen Programmiersprache numerische Berechnungen an, so erhält man gelegentlich verblüffende Ergebnisse – beispielsweise treten oft unerwartet Rundungsfehler auf. Während man in der Praxis in vielen Fällen über diese Rundungsfehler hinwegsehen kann, erreicht man gelegentlich doch einen Punkt, an dem man entweder auf entsprechend genaue Berechnungen angewiesen ist oder die Rundungsfehler durch Verwendung entsprechend großer Zahlen auf einmal wieder an Bedeutung gewinnen. An dieser Stelle ist es dann wichtig zu wissen, durch welche Effekte diese Fehler oder Ungenauigkeiten zustande kommen, um sie beheben, ausgleichen, oder umgehen zu können – und auch schon in der Fehlersuche kann das Wissen über die Existenz solche Effekte erheblich Zeit sparen.
Dieser Artikel soll die verschiedenen Effekte, die in der Rechnerarithmetik – also dem computergestützten Rechnen – auftreten können, nennen und ihr Zustandekommen erklären. Die Häufigkeit und Schwere, mit der die einzelnen Effekte zum Tragen kommen, hängt dabei nicht zuletzt auch von der verwendeten Programmiersprache ab, da die Art, in der Zahlen gespeichert und verarbeitet werden, einen großen Einfluss auf die entsprechenden Effekte hat. Dennoch werden die besprochenen Effekte – aus Gründen der Performance – in den meisten Programmiersprachen nicht immer von Haus aus ausgeglichen, selbst wenn das mit entsprechendem Aufwand möglich wäre.
Inhaltsverzeichnis
Zahlendarstellung im Computer
Zum besseren Verständnis der Effekte, die auftreten können, soll zunächst darauf eingegangen werden, wie ein Computer Zahlen speichert. Hier gibt es eine ganze Menge verschiedener Methoden, für JavaScript (oder PHP) sind aber nur zwei von Bedeutung.
Für den menschlichen Umgang mit Zahlen hat sich das Dezimalsystem durchgesetzt. Wie dieses System funktioniert, haben wir alle in der Schule kennengelernt: Um eine Zahl aufzuschreiben, verwenden wir die Ziffern 0 bis 9. Ist die Zahl größer als 9, bilden wir Päckchen der Größe 10, 100, 1000, und so weiter, und schreiben auf, wieviele Päckchen der jeweiligen Größe wir haben. Für Werte, die keine ganze Zahl darstellen, schreiben wir ein Komma und dahinter die Zehntel, Hunderstel, Tausendstel und mehr.
Im Gegensatz zu den römischen Zahlen ist dieses System offen. Ich kann jederzeit ein um den Faktor 10 größeres Päckchen bilden, oder eins meiner Bruchteilpäckchen weiter zehnteln. Die Anzahl der Ziffern ist weder vor noch nach dem Komma begrenzt. Für einen Computer ist das eine unangenehme Situation, denn sein Speicherplatz hat Grenzen, und je mehr Speicherstellen für eine Zahl benötigt werden, desto länger dauert es, sie zu verarbeiten. Darum setzen die Designer eines Computers Grenzen fest, innerhalb derer ein Computer Zahlen verarbeiten kann, und können so den Speicherplatz ermitteln, den der Computer für eine Zahl benötigt.
Allerdings ist es so, dass der Speicher eines Computers nicht dezimal arbeitet. Statt dessen besteht er aus Schaltern, die an oder aus sein können, wodurch sich die möglichen Zahlenwerte 0 und 1 ergeben. Um größere Zahlen darzustellen, müssen mehrere dieser Schalter kombiniert werden. Genau so, wie wir für Zahlen größer als 10 mehrere Dezimalziffern kombinieren, kombiniert der Computer Binärziffern. Im Dezimalsystem gibt es zehn Ziffern, deshalb hat jede Stelle einen um den Faktor 10 höheren Stellenwert. Das Binärsystem des Computers kennt nur zwei Ziffern, und darum hat dort jede Stelle einen um den Faktor 2 höheren Stellenwert.
Natürliche Zahlen ohne Nachkommastellen
Um zu verstehen, wie solche Zahlen gespeichert werden, betrachten wir als Beispiel eine Gruppe von vier Speicherstellen. Die Speichergruppe befindet sich in der ersten Zeile, darunter ist der Stellenwert jeder dieser Speicherstellen angegeben.
1 |
0 |
1 |
1
|
| 8 | 4 | 2 | 1 |
Wir haben also ein Achterpaket, kein Viererpaket, ein Zweierpaket und ein Einerpaket. Das ergibt im Dezimalsystem 11. Um das nicht jedesmal zu umständlich schreiben zu müssen, wollen wir festlegen, dass wir die „Päckchengröße“, auf der eine Zahl basiert, hinter dieser Zahl tiefgestellt angeben. Unser Zahl im Zweiersystem würde damit 10112 geschrieben werden, und der Gegenwert im Zehnersystem so: 1110.
Die einzelnen Speicherstellen einer solchen Speichergruppe bilden auf diese Weise die Ziffern einer Binärzahl. Im Englischen entstand daraus der Begriff bit, kurz für binary digit (Binärziffer). Da bereits die vierte Binärstelle den Stellenwert 8 hat, können wir alle Ziffern von 0-9 mit Hilfe von vier Bits darstellen.
Computer lesen aus ihrem Speicher allerdings keine einzelnen Bits, sondern immer Bitgruppen. Die kleinste Bitgruppe, auf die zugriffen werden kann, wird als Byte bezeichnet. Unser Einführungsbeispiel würde eine Bytegröße von 4 Bits verwenden, bei heutigen Computern besteht ein Byte aber zumeist aus 8 Bits. Der eigentliche Speicherzugriff erfolgt aber kaum noch byteweise, sondern man fasst mehrere Bytes zu einem Wort zusammen. Ein heutiger 64-bit Computer hat demnach eine Wortlänge von 8 Bytes.
Frühere Computer haben tatsächlich einzelne Ziffern einer Dezimalzahl in Bytes gespeichert und sie so verarbeitet. Wenn man berücksichtigt, dass eine Gruppe von 8 Bits 256 unterschiedliche Zustände einnehmen kann, also für ebensoviele verschiedene Werte stehen kann, ist das eine ziemliche Verschwendung. Da es aber einige Berechnungen braucht, um größere Zahlen zwischen Binärsystem und Dezimalsystem umzurechnen, nahm man das in Kauf und schuf sogar die optimierte Darstellung, ein Byte in zwei Halbbytes zu teilen und in je vier Bits eine Dezimalziffer zu speichern.
Mittlerweile ist das ferne Vergangenheit. Heutige Computer operieren mit 32 oder 64 Bit langen Bitgruppen, um damit ganze Zahlen darzustellen. Die größte mit 64 Bits darstellbare Zahl beträgt 18446744073709551615 - allerdings nicht für JavaScript. Dazu später mehr.
Exkurs: Ganzzahliger Überlauf und die Erfindung der negativen Zahlen
Wenn ein Computer so entworfen wurde, dass er mit Bitgruppen einer bestimmten Länge rechnet, stellt sich natürlich immer die Frage, was zu tun ist, wenn diese Länge für die zu verarbeitenden Zahlen nicht ausreicht. Aus Sicht der Computerhersteller ist diese Frage einfach: es ist ein Anwendungsproblem. Wenn ein Programm zwei 32-bit Werte addiert und die Summe eigentlich 33 Bits bräuchte, dann geht dieses 33-te Bit nicht in die Summe ein. Es wird lediglich in einem Überlaufkennzeichen vermerkt, damit das Programm entscheiden kann, was es weiter tun will.
Für Sprachen wie JavaScript oder PHP ist diese Situation nicht relevant, weil sie intern anders rechnen. Diese Überlaufproblematik hatte aber Folgen für die Art, wie Computer negative Ganzzahlen darstellen, und damit auch die Arbeitsweise der Bitverschiebungsoperatoren <<, >> und >>, weshalb dieser Exkurs im Artikel aufgenommen sein soll.
Wenn man Daten verarbeitet, deren Werte auch negativ sein können, möchte man natürlich vermeiden, dieses Vorzeichen separat speichern zu müssen. Die Lösung sieht so aus, dass man den verfügbaren Zahlenraum für Ganzzahlen halbiert. Die untere Hälfte ist für die positiven Zahlen da. Für die negativen Zahlen verwendet man den Trick, dass man - rein mathematisch - den Stellenwert des ersten nicht mehr darstellbaren Bits hinzuaddiert.
Dazu ein Beispiel. Nehmen wir an, wir hätten einen 4-bit Computer. Dieser kennt die Stellenwerte 1, 2, 4 und 8. Damit können wir in einem Datenwort die Werte von 00002=0 bis 11112=1510 darstellen. Der Stellenwert des ersten nicht mehr darstellbaren Bits ist 16. Um mit negativen Zahlen rechnen zu können, verwenden wir nur noch die Werte 0 bis 7 für die nicht-negativen Zahlen. Die negativen Zahlen verschlüsseln wir, indem wir 16 hinzuaddieren:
| negativ | verschlüsselt | binär |
|---|---|---|
| -1 | 15 | 11112 |
| -2 | 14 | 11102 |
| -3 | 13 | 11012 |
| ... | ||
| -7 | 9 | 10012 |
| -8 | 8 | 10002 |
Diese Darstellung trägt den Namen Zweierkomplement. Man erhält sie nämlich auch dadurch, dass man jede Binärziffer von der Zahl 2 abzieht. Addiert man das Ergebnis nachher passend zum Stellenwert auf, summieren sich diese 2er zum Stellenwert des ersten nicht mehr darstellbaren Bits und verschwinden deshalb, wie zuvor die 16, als Überlauf. Der Computer macht es allerdings nocheinmal anders. Er schaltet jedes einzelne Bit um (er invertiert es), was gleichbedeutend damit ist, es von 1 abzuziehen. Das ist technisch viel einfacher, als allgemeine Arithmetik zu betreiben. Formal heißt das, dass er eine 4-bit Zahl insgesamt von 11112 = 1510 abzieht. Wie Sie sehen, ist die Zahl, von der subtrahiert wird, nun um 1 zu klein. Es ist aber gleichgültig, ob man 15 + 1 - X oder 15 - X + 1 rechnet. Das macht sich der Prozessor zu nutze. Er flippt zuerst die Bits um, und addiert dann 1 hinzu. Etwas um „+1“ hochzuzählen (zu inkrementieren) ist ebenfalls eine einfachere Operation als die Addition zweier beliebiger Zahlen.
Auf diese Weise erreicht man zweierlei:
- Eine negative Zahl ist daran zu erkennen, dass ihr höchstes Bit gesetzt ist
- Man kann positive Zahlen und negative Zahlen einfach mit dem vorhandenen Rechenwerk für Ganzzahlen addieren
Warum geht das? Nehmen wir an, wir hätten eine positive Zahl a und eine negative Zahl b. Die positive Zahl ist ganz normal binär gespeichert, für die negative Zahl wurde aber der Wert b' = 16+b gespeichert. Addiert man nun die gespeicherten Bitmuster so, als wäre gar kein Vorzeichen da, ergibt sich die Summe a+b' = a+b+16. Und weil der Computer eine Wortlänge von 4 Bit hat, geht der Summand +16 verloren, bzw. er wird als Überlaufkennzeichen gespeichert. Damit bleibt a + b übrig.
Beispiel:
Sei a = 510 = 01012 und und b = -310. b würde als b' = 1610 + b = 1310 = 11012 gespeichert.
Die binäre Addition von 01012 und 11012 ergibt:
| 0 | 1 | 0 | 1 | erster Summand | |
| 1 | 1 | 0 | 1 | zweiter Summand | |
| 1 | 1 | Übertrag | |||
| 1 | 0 | 0 | 1 | 0 | Summe |
Die 1 an der 5. Bitposition wird im Übertragskennzeichen gespeichert, und als Ergebnis bleibt 00102 = 210 übrig. 5 + (-3) = 2. Stimmt!
Natürlich handelt man sich auf diese Weise Folgeprobleme ein. Beispielweise würde die Addition 5 + 6 den Wert 11 ergeben, was für -5 steht. Aber aus binärer Sicht ist das kein Überlauf, das Übertragskennzeichen würde also nicht gesetzt werden. Die Prozessorhersteller haben das gelöst, indem sie außer dem Übertragskennzeichen noch ein Überlaufkennzeichen eingeführt haben, das Überträge von der vorletzten auf die letzte Bitposition meldet.
Zahlen mit Nachkommastellen
Um nicht nur ganze Zahlen, sondern auch Dezimalzahlen darstellen zu können, benötigt man weitere Techniken. Eine kann darin bestehen, dass man weiterhin mit ganzen Zahlen rechnet und die verwendeten Zahlen vor der Speicherung multipliziert. Banken und Versicherungen tun das in ihrer Buchführung, die verwendete Arithmetik arbeitet nach genauen Vorschriften mit Hunderstel-Cent.
Für technische Anwendungen ist dieser Ansatz hingegen nicht so nützlich. Hier ist nicht die absolute Genauigkeit wichtig, sondern eine bestimmte Anzahl signifikanter Ziffern für jeden Wert. Um das zu verdeutlichen: Es hilft nichts, mit Werten zu rechnen, die auf ein Millionstel genau sind, wenn ich mit Satellitenfrequenzen rechne. Oder mit Signallaufzeiten von Lichtimpulsen innerhalb eines Raumes. Um solche Zahlen effizent speichern und verarbeiten zu können, bestimmt man den Stellenwert der höchsten verwendeten Ziffer und dividiert die Zahl dadurch. Das Ergebnis ist, dass man genau eine Ziffer vor dem Komma hat und alle übrigen Ziffern dahinter stehen. Von diesen Ziffern speichert man so viele, wie der für eine Zahl verfügbare Speicherplatz zulässt, und rundet die Zahl an dieser Stelle. Diesen gerundeten Wert speichert man zusammen mit der Stellenposition des Stellenwertes, durch den man dividiert hat.
Ein Beispiel im Zehnersystem: Gegeben sei die Zahl 124,796875. Die höchste verwendete Ziffer ist die 1 mit Stellenwert 100. Wir dividieren die Zahl also durch 100 und erhalten die genormte Exponentialdarstellung 1,24796875 · 102. In dieser Darstellung bezeichnet man den Ziffernteil 1,24796875 als Mantisse und die Zahl 2, die die Größenordnung angibt, als Exponent.
Nun sei angenommen, wir könnten nur 4 Ziffernstellen speichern. Dann würde man hinter der 4 runden und das Wertepaar (1248, 2) als Mantisse und Exponent speichern, um so den Fließkommawert 1,235 · 102 zu repräsentieren.
Computer arbeiten hingegen binär, deshalb rechnen wir 124,79687510 zunächst einmal in eine Binärzahl um. Dabei hilft uns die JavaScript-Methode toString(2), mit der wir das Ergebnis 124,79687510 = 1111100,1100112 erhalten. Das sind 7 Ziffern (oder Bits) vor dem Komma, wir dividieren also durch 26 und erhalten die binäre Exponentialdarstellung 1,111100110011 · 26.
Eine Besonderheit der binären Darstellung ist, dass vor dem Komma nun unweigerlich eine 1 steht. Die Norm IEEE 754, die die Regeln für diese Zahlendarstellung beschreibt, legt deshalb fest, dass diese 1 gar nicht gespeichert wird. Der Computer weiß einfach, dass sie da sein muss. Die 16-bit Variante "binary16" von IEEE 754 teilt den verfügbaren Platz in 10 Bits für die Mantisse und 5 Bits für den Exponenten auf. Das verbleibende Bit nimmt das Vorzeichen der Zahl auf. Für unsere Beispielzahl bedeutet das, dass wir die Binärziffern 1111001100 speichern können und 11 verwerfen müssen. Den Exponenten speichert man etwas anders, die Norm legt einen Grundwert (bias) fest, der auf den Exponenten addiert wird. Für binary16 ist dies die 15, man könnte in den verfügbaren 5 Bits also Exponenten von -15 bis +16 speichern (die Exponentwerte 0 und 31 sind allerdings für die aus JavaScript bekannten Werte NaN und Infinity reserviert).[1]. Gespeichert würde also die gerundete Mantisse 11110011012 und 21 als Exponent mit Bias.
JavaScript verwendet das binary64-Format für Fließkommazahlen. Dieses stellt 52 Bits für die Mantisse und 11 Bits für den Exponenten bereit, woraus sich der Wert 253-1 für Number.MAX_SAFE_INTEGER herleitet.
Aber weshalb haben wir nun eine so schrecklich krumme Dezimalzahl für das Beispiel verwendet? Nun ja, es gibt gewisse Probleme, um die ich mich mit dem Beispiel herumgedrückt habe, und ich gebe dafür an Janosch zurück.
Nicht exakt darstellbare Zahlen
<form name="demo" action="#">
<p>Schon einfache Berechnungen mit JavaScript können Rundungsfehler aufweisen:</p>
<input type="text" id="ausdruck" value="0.1 + 0.2 + 0.3">
<button>Berechnen!</button>
<output id="ergebnis"></output>
</form>
<script>
var demoForm = document.forms.demo;
demoForm.addEventListener("submit", function (submitEvent) {
demoForm.ergebnis.value = eval(demoForm.ausdruck.value);
submitEvent.preventDefault();
});
</script>
Beobachtung: Schon bei einer „einfachen“ Rechnung ergeben sich sichtbare Rundungsfehler – woher kommen sie, wenn die eingegebenen Zahlen doch exakt sind?
Das Konzept nicht exakt darstellbarer Zahlen ist uns eigentlich schon aus der Schulmathematik wohlbekannt und kommt immer dann zum Tragen, wenn man über den Bereich der ganzen Zahlen hinausgeht. Man denke nur an einen Bruch mit dem Nenner 7 – es gibt keine Möglichkeit, 1/7 mit einer Dezimalzahl exakt darzustellen. Wir behelfen uns mit dem Periodenstrich und schreiben 1/7 = 0,142857. Der Periodenstrich besagt, dass die überstrichenen Ziffern sich für eine „genaue“ Darstellung des Zahlenwertes unendlich oft wiederholen müssten.
Bevor wir nun auf die Eigenheiten des im Rechner intern verwendeten Binärsystems eingehen können, müssen wir noch einen kleinen Exkurs einschieben – das folgende Unterkapitel kann von fortgeschrittenen Lesern, die sich mit der Darstellung gebrochener Zahlen in beliebigen Zahlensystemen auskennen, natürlich übersprungen werden.
Gebrochene Zahlen in beliebigen Zahlensystemen
Wir sind es gewohnt, mit gebrochenen Zahlen im Dezimalsystem umzugehen. Tatsächlich sind wir den Umgang damit derart gewohnt, dass wir nicht bewusst bemerken, was genau hinter der Darstellung steht – was das Verständnis von gebrochenen Zahlen in anderen Zahlensystemen erschwert. Aus der Grundschule kennt man die Benennung der Ziffern einer ganzen Zahl als Einer, Zehner, Hunderter – und ganz analog lassen sich die Nachkommastellen als Zehntel, Hundertstel, Tausendstel auffassen. Man kann damit jede Dezimalzahl in eine Summe von Vielfachen der Basis 10 und ihrer Potenzen zerlegen (in der Mathematik spricht man bei einer solchen Darstellung von einem 10-adischen Bruch).
Um zu verdeutlichen, dass die Zahl 123,546 als eine Kombination von Zehnerpotenzen aufzufassen ist, wurde sie um eine tiefgestellte 10 erweitert.
Führt man sich diesen Zusammenhang vor Augen, so lässt sich die Bedeutung einer gebrochenen Zahl im Binärsystem ganz einfach analog erklären – die Darstellung auf Basis von Zweierpotenzen nennt man 2-adische oder dyadische Zahlen (gesprochen dy-a-disch). Um klarzustellen, welche Zahlenbasis gemeint ist, erweitert man die Darstellung um eine tiefgestellte 2.
= 4 + 2 + 0 + 1/2 + 0 + 1/8 = 6,312510
Damit können wir eine Antwort auf die Frage geben, in welchem Zahlensystem es eine exakte Darstellung von 1/7 mit endlich vielen Ziffern geben könnte.
Im Siebener-System kann die rationale Zahl 1/7 mit endlich vielen Nachkommastellen dargestellt werden – im Dezimalsystem nicht.
Nicht exakt darstellbare Zahlen im Binärsystem
Das Binärsystem ist bekannterweise die Form, in der Computer Zahlen speichern und verarbeiten. Im Gegensatz dazu verwendet der Anwender – und meist auch der Programmierer – zur Eingabe von Zahlen das Dezimalsystem. Das kann schon bei scheinbar unbedenklichen Zahlen zu Problemen führen. Die einfachsten gebrochenen Zahlen, die sich der Anwender vorstellen kann, sind die Potenzen der Dezimalbasis – also Zahlen wie 0,1 oder 0,001. Diese Zahlen stellen den Computer vor unlösbare Schwierigkeiten – denn sie sind im Binärsystem, also mit Potenzen von 2, nicht exakt mit endlich vielen Ziffern darstellbar.
Leider ist der Computer aber nicht in der Lage, unendlich viele Ziffern zu speichern oder zu verarbeiten – die Ziffernfolge muss also ab einer bestimmten Länge (abhängig von Programmiersprache und System) abgeschnitten werden. Daraus ergibt sich der eingangs gezeigte Rundungsfehler.
0,0001100112 = 0.09960937510
Rundungsfehler bei Speicherung einer "exakten" Dezimalzahl im Binärformat, angenommen es wären lediglich die ersten 5 Nachkommastellen durch den Computer speicherbar. Die scheinbar unbedeutende Änderung im Binärsystem (es wird nach "nur" 5 Stellen abgeschnitten) hat im Dezimalsystem deutlich spürbare Auswirkungen. Mehr Ziffern machen es besser, es wird aber nie eine exakte Darstellung möglich sein.
Das Beispiel zeigt auch, dass schon einfachste Dezimalzahlen im Binärsystem relativ viele Stellen benötigen, um auch nur einigermaßen exakt zu sein. Die maximale Präzision, die mit Fließkommazahlen erreicht werden kann, wird dabei durch die Programmiersprache und (soweit die Programmiersprache hier Einfluss ermöglicht) den verwendeten Datentyp festgelegt. So sind zum Beispiel die Datentypen float (32 Bit) und double (64 Bit) üblich. Diese Datentypen speichern die Zahlen in einer standardisierten Darstellung (IEEE 754) und können dann noch 23+1 bzw. 52+1 Bit für tatsächlich zählende Ziffern aufbringen. Auch das kann bei scheinbar einfachen Zahlen zu spürbaren Rundungsfehlern führen.
Typische Präzision einer float-Fließkommazahl. Das float-Format von IEEE 754 stellt 23 Binärziffern und eine führende 1, also insgesamt 24 Ziffern zur binären Speicherung zur Verfügung. Schon bei für den Anwender einfach vorstellbaren Zahlen ist damit ein Präzisionsverlust deutlich spürbar.
Viele Programmiersprachen versuchen, diesen Effekten entgegen zu wirken. So ist heutzutage in vielen Sprachen die double precision das Standardformat für Fließkommazahlen. Bei entsprechendem Abstraktionsgrad der verwendeten Programmiersprache werden gelegentlich auch zusätzliche Techniken eingesetzt, um Rundungsfehler zu vermeiden. Diese sind allerdings nicht unfehlbar – und man muss sich jederzeit im Klaren darüber sein, dass in Endergebnissen falsch gerundete Stellen vorkommen können, deren Ursachen in der Binärdarstellung liegen.
console.log(0.1+0.2+0.3);
//Ergebnis: 0.6000000000000001
console.log(0.1+0.1+0.1+0.1+0.1+0.1);
//Ergebnis: 0.6
console.log(0.2+0.2+0.2);
//Ergebnis: 0.6000000000000001
console.log(0.3+0.3);
//Ergebnis: 0.6
Beobachtung: Das Vorkommen von darstellungsbedingten Rundungsfehlern ist kaum zweifelsfrei vorherzusagen.
Eine sehr anschauliche Darstellung des Verhaltens von IEEE 754 Fließkommazahlen findet sich bei H. Schmidt.
Datentyp-basierte Effekte
Im vorigen Abschnitt wurden Zahlen besprochen, die für den Computer nicht exakt binär darstellbar sind. Tatsächlich kommen aber auch bei exakt binär darstellbaren Zahlen problematische Effekte vor – meist bedingt durch Eigenheiten des Datentyps, mit dem die entsprechenden Zahlen gespeichert werden. Wir befassen uns in diesem Abschnitt also, um den Unterschied noch einmal klar zu machen, nicht mehr primär mit gebrochenen Zahlen, sondern insbesondere auch mit ganzen Zahlen.
Grundsätzlich sind Datentypen zunächst einmal immer durch den zur Verfügung stehenden Speicherplatz limitiert. Lange Zeit waren Datentypen mit 32 Bit die Standard-Datentypen in den meisten Programmiersprachen (Java: Stichworte int, float), inzwischen wird, mit zunehmender Verbreitung von 64-Bit-Prozessoren und insgesamt verringertem Speichermangel oft auf 64 Bit für Standard-Datentypen gesetzt (Java: Stichworte long, double).
Dabei unterscheidet man weiterhin zwischen der Speicherung als Fließkommazahl oder als Festkommazahl. Die einfachsten Beispiele für Festkommazahlen sind die gewöhnlichen ganzen Zahlen – und die korrespondierenden Ganzzahl-Datentypen (Java: int, long). Diese Ganzzahl-Datentypen – und allgemein alle Festkommazahl-Datentypen – zeichnen sich dadurch aus, dass sie (je nach dem ihnen zur Verfügung stehenden Speicherplatz) nur ganz bestimmte Wertebereiche besitzen. Festkommazahlen sind also nicht primär durch die Anzahl zählender Ziffern begrenzt, sondern vielmehr durch den zugeordneten Wertebereich. Der Wertebereich einer gewöhnlichen 32-Bit-Festkommazahl umfasst etwa 4,3 Milliarden verschiedene Zahlen.
Die Speicherung einer Fließkommazahl wurde im vorhergehenden Abschnitt schon angerissen. Der Standard IEEE 754 definiert dabei, wie die einer Fließkommazahl zur Verfügung stehenden Bits zur Speicherung der entsprechenden Zahl verwendet werden. Dabei entfällt ein Teil der Bits auf die sogenannte Mantisse, also den Teil der Zahl, der die zählenden Ziffern (binär) darstellt. Ein weiterer Teil der Bits entfällt auf den sogenannten Exponenten – vergleichbar mit dem Exponenten von 10, wenn man eine Dezimalzahl in wissenschaftlicher Schreibweise darstellt. Bei einer Zahl in single precision (float) wären das beispielsweise 23 Bit für die Mantisse und 8 Bit für den Exponenten (das letzte "fehlende Bit" entfällt auf das Vorzeichen). Eine Fließkommazahl wird daher von zwei Seiten limitiert – einerseits durch die maximale Anzahl zählender Ziffern (Mantisse), andererseits durch den maximalen Wertebereich des Exponenten (dieser gibt quasi die Größenordnung der Zahl an). Trotz dieser doppelten Limitierung sind Fließkommazahlen durch die Kombination aus Mantisse und Exponent in ihrem Wertebereich deutlich flexibler als Gleitkommazahlen – der Wertebereich einer single precision-Fließkommazahl erstreckt sich bei beiden Vorzeichen zwischen den Größenordnungen 10-45 und 1038.
In vielen Programmiersprachen hat der Programmierer Kontrolle über die Wahl des Datentyps, mit dem er arbeiten möchte. Je nachdem kann man schon vorher abschätzen, ob der Eine oder der Andere der hier genannten Effekte auftreten wird und ob dadurch Probleme drohen; der Datentyp kann dann situationsangepasst gewählt werden. Diese Möglichkeit entfällt in Sprachen mit sehr hohem Abstraktionsniveau (wie beispielsweise JavaScript), da die entsprechende Programmiersprache die Wahl des Datentyps übernimmt und zur Laufzeit gegebenenfalls auch dynamisch anpasst. In solchen Sprachen ist es dann oft auch schwieriger, den einen oder anderen Effekt zu kontrollieren oder vorherzusagen.
Fließkomma-Addition von Zahlen ungleicher Größenordnung
//Ergebnis: 500000000000000000000
//Ergebnis: 500000000000123500000
Beobachtung: Bei der Addition von Fließkommazahlen ganz unterschiedlicher Größenordnung kann es vorkommen, dass die kleinere Zahl im Ergebnis verschwindet – oder ein Teil davon.
Dieser Effekt ist – auch in seiner Begründung – ganz ähnlich zum letzten besprochenen Effekt im ersten Abschnitt. Grund für dieses unpräzise Ergebnis ist die Limitierung der Mantisse – also der Anzahl zählender Ziffern – in der Fließkommadarstellung. Sobald die zählenden Ziffern nicht mehr ausreichen, um die gesamte Zahl darzustellen, muss am Ende gerundet werden – zu Ungunsten etwaiger deutlich kleinerer Zahlen, die soeben aufaddiert wurden. Selbstverständlich ist auch die Subtraktion von dieser Problematik betroffen.
Tatsächlich ist es so, dass die Fließkommadarstellung zwar einen größeren Wertebereich hat, dieser jedoch ist deutlich weniger dicht mit möglichen Werten besetzt, als es in einer Festkommadarstellung der Fall wäre. Oder kurz und prägnant: Nicht jede ganze Zahl innerhalb des Wertebereichs einer Fließkommadarstellung ist darin auch tatsächlich darstellbar. Die Dichte der darstellbaren Ganzzahlen nimmt dabei mit größer werdendem Exponenten deutlich (sogar exponentiell) ab.
Arithmetischer Unterlauf
Der arithmetische Unterlauf ist ein Effekt, der bei der Verwendung von Fließkommazahlen auftritt. Der Effekt tritt immer dann auf, wenn eine Zahl, die als Fließkommazahl gespeichert werden soll, betragsmäßig kleiner ist als die kleinste darstellbare Zahl im entsprechenden Datentyp. Der Wert der Zahl wird dabei grundsätzlich auf 0 gerundet; je nach Programmiersprache und Umgebung kann ein arithmetischer Unterlauf auch zu einer sichtbaren Warnung oder einem Fehler führen.
Das IEEE 754 Zahlensystem besitzt dabei eine Besonderheit. Wenn ein arithmetischer Unterlauf eintritt, wird das Vorzeichen des Ergebnisses beibehalten. Der Wert 5-324 ist die kleinste positive Zahl, die ein IEEE 754 double-Wert darstellen kann. Teilt man diesen Wert durch 10, ergibt sich 0. Tut man das gleiche mit -5-324, ergibt sich der besondere Wert -0. Diese beiden Werte sind normalerweise nicht unterscheidbar, werden aber relevant, wenn man sie an einer Stelle verwendet, wo die Verwendung von 0 zu einem Überlauf führt (z.B. Division durch 0). Eine Division durch 0 ergibt im IEEE 754 System den speziellen Wert Infinity, während die Division durch -0 zu -Infinity führt.
Diese Unterscheidung ist zumeist ohne Bedeutung. In JavaScript haben Sie keine direkte Möglichkeit, einen Wert gezielt auf +0 oder -0 abzufragen. Sie können es nur indirekt tun, indem Sie durch den Nullwert dividieren und prüfen, ob sich Infinity oder -Infinity ergibt.
Arithmetischer Überlauf
Festkommazahlen können im Allgemeinen positiv und negativ sein. Da ein Computer kein Vorzeichen, sondern eben nur Nullen und Einsen speichern kann, muss die interne Repräsentation von negativen Festkommazahlen durch positive erfolgen. Dabei hat sich aus technischen Gründen das sogenannte Zweierkomplement durchgesetzt, d. h. man erhält eine negative Zahl aus der entsprechenden positiven Zahl, indem man ihre Bits invertiert (Nullen in Einsen verwandeln und umgekehrt) und dann 1 addiert (die Überträge beim Addieren, die über die feste Anzahl verfügbarer Bits hinausgehen, werden ignoriert). Dadurch bekommt das höchstwertige Bit (die Stelle ganz links) eine Art Vorzeichenfunktion (negative Zahlen haben im höchstwertigen Bit eine 1, positive eine 0).
0101 1010
inv. ---- + 0001
1010 ------
1011
Bilden des Zweierkomplements der Binärdarstellung der Zahl 5, bei einer angenommenen Speicherkapazität von 4 Bit.
Arithmetischer Überlauf ist vor allem dafür bekannt, bei Festkommazahlen aufzutreten. Zwar ist dieser Effekt auch bei Gleitkommazahlen prinzipiell möglich, dort aber weit weniger üblich und wird oft auch durch andere Behandlung (z. B. dem Wert positive infinity im IEEE 754) verhindert. Arithmetischer Überlauf tritt dann auf, wenn das Ergebnis einer Berechnung nicht mehr innerhalb des festgelegten Wertebereichs liegt. Tatsächlich beginnen in der Binärdarstellung direkt nach den positiven Zahlen des Wertebereichs die negativen Zahlen desselben Wertebereichs, wie man sich durch Bilden der Zweierkomplemente klarmachen kann.
00012 = 110
…
01012 = 510
01102 = 610
01112 = 710
10002 = -810
10012 = -710
10102 = -610
10112 = -510
…
11112 = -110
In der Zweierkomplement-Darstellung sind die Binärzahlen, die negative Zahlen repräsentieren, größer als die Binärzahlen, die positive Zahlen repräsentieren. Per Definition ist grundsätzlich die kleinste darstellbare Zahl betragsmäßig größer als die größte darstellbare Zahl; in diesem Fall sind die Zahlen -8 und 7 die Grenzen des 4-Bit-Wertebereichs.
Dieser Umstand zeigt also schon ganz klar, welches Ergebnis man erhalten wird, wenn man über den (positiven) Wertebereich hinaus addiert: Eine negative Zahl.
01102 = 610
0101 + 0110 ------ 1011
Beim Subtrahieren mit Ergebnis unterhalb der unteren Grenze des Wertebereichs ergibt sich natürlich der analoge Effekt – auf die kleinstmöglich darstellbare Zahl folgt die größtmöglich darstellbare Zahl.
Selbstverständlich ist auch hier die Behandlung eines arithmetischen Überlaufs wieder Sache der verwendeten Programmiersprache oder des Programmierers – so ist es möglich, dass eine Programmiersprache entweder keine Überläufe zulässt, oder aber bei Vorkommen von Überläufen entsprechend warnt. Grundsätzlich gilt: Sofern der Programmierer einen Einfluss auf die Wahl des Datentyps hat, sollte dieser so gewählt werden, dass im zu erwartenden Betriebszustand nie ein Überlauf auftreten kann. Mögliche arithmetische Überläufe stellen weiterhin oft sicherheitsrelevante Probleme in fertigen Systemen dar, sofern deren Auftreten nicht vorher bedacht und behandelt wurde.
Numerische Effekte
Während wir Menschen es im mathematischen Umfeld gewohnt sind, algebraisch, also mit Symbolen und Rechenregeln, zu rechnen, und dabei höchstens im Endergebnis runden zu müssen, gehen Computerberechnungen meist auf numerische Rechnungen zurück, in denen Zahlen in ihrer endlichen Repräsentation verwendet werden. Auch hier gibt es Effekte, die – über die bisher behandelten darstellungsbedingten Genauigkeitsverluste hinaus – in unerwarteter Weise auftreten können.
Auslöschung
Dieser Effekt, auch geläufig unter seiner englischen Bezeichnung, cancellation, bezeichnet in der Numerik einen Genauigkeitsverlust bei der Subtraktion ähnlich großer Gleitkommazahlen. Man geht dabei davon aus, dass beide an der Subtraktion beteiligten Ausgangszahlen schon mit Rundungsfehlern behaftet sind. Im Umgang mit Computerberechnungen ist das – als Folge der Zusammenhänge aus dem vorigen Abschnitt – auch grundsätzlich der Fall. Der Effekt tritt also nicht direkt in Folge dessen auf, dass ein Computer die Berechnungen ungenau durchführt, sondern vielmehr da bei entsprechend fehlerbehaftet gespeicherten Werten gar keine genauere Berechnung mehr möglich ist.
Die erste Zeile zeigt die Subtraktion zweier fast gleich großer Fließkommazahlen – die aber nur in den ersten vier Ziffern nicht fehlerbehaftet sind. Die zweite Zeile zeigt die selbe Rechnung, allerdings dieses Mal mit Zahlen, die nicht fehlerbehaftet sind. Während es logisch erscheint, mit den Zahlen, die (trotz Rundungsfehler) gespeichert sind zu rechnen, ergibt sich dadurch in diesem Beispiel eine Abweichung von 11% zwischen dem Ergebnis der exakten, um Rundungsfehler bereinigten Rechnung und der vermeintlich korrekten, logisch erscheinenden Berechnung – und das obwohl die relativen Fehler der Eingangszahlen im Bereich eines hundertstel Prozents lagen. Der relative Fehler hat sich also in einer Operation etwa um den Faktor 1000 vergrößert.
Der Name Auslöschung bezieht sich darauf, dass die Anzahl korrekter Stellen bei einer solchen Berechnung drastisch verringert wird – waren vor der Rechnung noch die Hälfte der zählenden Ziffern korrekt und nicht von Rundungsfehlern beeinflusst, so ist nach der Berechnung der Anteil von fehlerbehafteten Stellen deutlich höher. Insbesondere steigt damit auch bei jeder solchen Operation der relative Fehler sprunghaft an, wenn man die relativen Fehler der Eingangszahlen mit den relativen Fehlern der Ausgangszahlen vergleicht.
Besonders heimtückisch ist dieser Effekt dann, wenn man die zu verrechnenden Zahlen vorher nicht sieht, da mit Variablen gerechnet wird – und man dementsprechend auch auf den Rundungsfehler nicht aufmerksam wird.
var b = 0.3+0.3; var zero = a - b; alert(zero);
//Ergebnis: 1.1102230246251565e-16Wir wissen aus dem vorhergehenden Abschnitt, dass die Werte in a und b rundungsbedingt nicht exakt identisch sind – sie scheinen es aber zu sein, da der Anwender nicht bemerkt, dass die Werte mit Rundungsfehlern behaftet sind. Der daraus resultierende Verlust an Genauigkeit bei der Subtraktion bedeutet hier, dass die Variable zero, die eigentlich den Wert 0 beinhalten sollte, ungleich 0 ist. Der Fehleranteil an diesem Ergebnis beträgt 100%.
Werden die vermeintlich exakten Ergebnisse, die mit einem sehr großen Prozentteil aus Rundungsfehlern bestehen, zur Weiterberechnung verwendet, potenziert sich dieser Fehler; vor allem dann, wenn die problematische Stelle in einem iterativen Algorithmus auftritt.
Information
Allgemein kann man sagen:
Subtrahiert man zwei fast gleich große Zahlen, so verringert sich die Genauigkeit des Ergebnisses um so viele Stellen, wie die Ausgangszahlen von links her gemeinsam haben.Umgehen lässt sich diese Problematik oft dadurch, dass man in den zur Berechnung verwendeten Formeln sehr vorsichtig mit Subtraktionen umgeht. Oft lässt sich eine Formel in einem Algorithmus auch so umstellen, dass die zu subtrahierenden Zahlen nicht gleich groß sind – etwa durch Anwendung binomischer Formeln. An anderen Stellen muss man, wenn Probleme auftreten und deren Ursprung bekannt sind, Zwischenergebnisse sinnvoll runden, um eine möglichst nicht-fehlerbehaftete Berechnung zu erhalten. In jedem Fall sollte man sich der Existenz des Effekts bewusst sein und dementsprechend auf die Größenordnung der zu subtrahierenden Zahlen achten, wenn man eine Subtraktion einsetzen muss.
a - b = (a2-b2) / (a + b)
