Computer rechnen anders?

In Newsgruppen findet man immer wieder Fragen, die sich um das Thema "ungenaue Rechenergebnisse" drehen.

Zum Beweis, wie ungenau der Computer rechnet, werden Beispiele angeführt:

0.2 + 0.7 ergibt 0.89999999
1.234 * 1000 ergibt 1233.999967

Woher kommen diese Ungenauigkeiten???

Dieser Artikel soll dem Programmiereinsteiger in das Thema einführen und Hintergrundinformationen bieten, um diese Probleme zu verstehen und dadurch zu vermeiden.

Dezimalzahlen und Dezimalbrüche

Dezimalzahlen und ihre Schreibweise haben wir alle in der Schule gepaukt. Durch die tägliche Verwendung nehmen wir gar nicht mehr wahr, das eine recht ausgetüftelte Schreibweise zur Darstellung der Dezimalzahlen verwendet wird, das sogenannte Positionssystem.

In einem Positionssystem erhalten die Ziffern außer ihrem Zahlenwert noch einen Stellenwert. Den Stellenwert drücken wir in unsere Sprache aus, indem wir von Hunderter, Zehner, Einer usw. sprechen.

Für jede Ziffer ist es also sehr wichtig, an welcher Stelle sie steht, denn dadurch wird Ihr Stellenwert bestimmt. Der Stellenwert wächst von rechts nach links, die Bezugsziffer ist die Einerstelle, jede Ziffer links davon hat eine um den Faktor 10 höhere Wertigkeit pro Stelle.

Normalerweise schreiben wir den Stellenwert nicht explizit hin, das wäre Platz und Zeitverschwendung, aber zu Verdeutlichung wollen wir hier ein Beispiel mit Angabe des Stellenwertes ansehen:

Beispiel: 1204 entspricht ausgeschrieben: 1*1000 + 2*100 + 0*10 + 4*1

Im Positionssystem bewährt sich auch die Null hervorragend. Sie belegt eine Position mit dem Zahlenwert 0, sorgt aber dafür, das die weiter links oder rechts stehenden Ziffern an der richtigen Position stehen. Ohne Null (oder etwas gleichwertiges) könnten wir unser Positionssystem gar nicht verwenden.

Das Positionssystem war ein großer Fortschritt gegenüber anderen Systemen wie z.B. dem römischen Additionssystem. Das schriftliche Rechnen ist im Positionssystem viel einfacher und Dezimalzahlen lassen sich kompakter schreiben als römische Zahlen (Beispiel: 7 =  VII,  88 = LXXXVIII).

Doch zurück zu den Dezimalzahlen. Bisher können wir im gerade vorgestelltem Positionssystem nur ganze Zahlen notieren. Ein weitere wichtiger Schritt war es daher, diese Schreibweise so zu erweitern, das auch Brüche und irrationale Zahlen darstellbar sind.

Jeder beliebige Bruch lässt sich in einen Dezimalbruch (Brüche mit Nenner gleich 10, 100, 1000 usw.) umrechnen.

Wenn wir Dezimalbrüche verwenden, können wir das Schema des Dezimal-Positionssystems - jeder Stelle unterscheidet sich vom Nachbar um den Faktor 10 - auch nach rechts zu kleineren Stellen fortsetzen und wir erhalten rechts von der Einerstelle die Zehntel, Hundertstel, Tausendstel usw.

Wenn wir unser Beispiel von oben erweitern, sagen wir um den Bruch 1/4, müssen wir 1/4 zuerst in einen Dezimalbruch umwandeln:

 1     1*25     25      2      5
——— = —————— = ———— = ———— + —————
 4     4*25    100     10     100

Das können wir dann als Dezimalzahl schreiben als:

Das Komma müssen wir setzen, damit wir die Einerstelle erkennen können.
Allerdings werde ich hier kein Komma mehr verwenden, sondern als Trennzeichen den Punkt, so wie das in Programmiersprachen (und einigen natürlichen Sprachen) üblich ist. Unser Zahlenbeispiel, mit Angabe aller Stellenwerte, sieht dann so aus:

                                           1         1
1204.25 = 1*1000 + 2*100 + 0*10 + 4*1 + 2*———— + 5*—————
                                           10       100

Die uns so vertraute Schreibweise mit den Dezimalbrüchen wurde in Europa erst etwa um 1600 von dem niederländischer Mathematiker und Ingenieur Simon Stevin (Wikipedia über Simon Stevin) verbreitet.

Kann man mit Dezimalzahlen alle Brüche und alle irrationalen Zahlen darstellen?

Wenn wir versuchen, so harmlose Brüche wie 1/3 oder 1/7 in einen Dezimalbruch umzuwandeln, stellen wir fest, das sich Ziffern oder Ziffernfolgen zu kleineren Stellen hin ständig wiederholen:

1/3 -> 0.333333333333333333333333
1/7 -> 0.142857142857142857142857

Solche Brüche nennt man periodisch, da sich die Ziffern(folgen) unendlich oft wiederholen.

Irrationale Zahlen lassen sich nicht als Bruch darstellen und sie haben eine unbegrenzte Stellenanzahl; bekannte Beispiele für irrationale Zahlen sind die Kreiszahl π und √2. (weitere Infos zur Zahl π).

Zur exakten Darstellung irrationaler Zahlen und der periodischen Dezimalbrüche müssten wir unendlich viele Stellen notieren. Das ist weder auf Papier noch im Computerspeicher möglich. Deshalb müssen wir uns auf eine bestimmte Anzahl von Stellen beschränken!

Nehmen wir für ein Zahlenbeispiel an, das wir uns auf 5 Nachkommastellen beschränken müssen:

Berechnung von

 1     1     2
——— + ——— = ———
 7     7     7

Die Addition der Zahlen als Brüche ist einfach und ergibt das exakte Ergebnis 2/7. Rechnen wir dagegen mit Dezimalzahl mit nur 5 Nachkommastellen, so erhalten wir:

   1         1        2
  ———   +   ———   =  ———
   7         7        7

0.14285 + 0.14285 = 0.28570

Hier weicht die 5. Nachkommastelle schon vom genauen 5 stelligem Ergebnis für 2/7 ab:

 2
——— = 0.28571
 7

Die mathematisch exakte Bruchgleichung ist als Dezimalzahl mit begrenzter Stellenzahl plötzlich nur noch ungefähr gleich, da sich die Summe der beiden Brüche in der letzten Dezimalstelle vom korrekten Wert für 2/7 unterscheidet!

Löst runden das Problem?

Kurz gesagt - Nein!

Mit der begrenzten Stellenanzahl können wir bestimmte Zahlen nicht exakt darstellen. Entweder ist die Zahl etwas zu klein oder etwas zu groß. Im obigen Beispiel haben wir nicht gerundet. Wenn wir 1/7 aufrunden, erhalten wir für das gleiche Beispiel folgende Rechnung:

0.14286 + 0.14286 = 0.28572

Wieder haben wir eine Abweichung in der letzten Stelle gegenüber der direkten Berechnung von 2/7!

Computer können nur bis Eins zählen

Alle (mir bekannten) Computer verwenden das sogenannte Binärsystem. Binär bedeutet hier "zwei unterscheidbare Werte" und der Grund für die weite Verbreitung dieses Systems ist seine einfache technische Realisierbarkeit und seine Zuverlässigkeit. Es ist relativ einfach, nur zwei verschiedene Zustände zu speichern (z.B. Flipflop-Schaltung) und solche Zustände fehlerfrei zwischen CPU und Speicher oder über externe Schnittstellen zu übertragen. Außerdem lassen sich Rechenwerke für Binärzahlen einfach in Hardware realisieren, da die binären Rechenregeln simpel sind.

Wenn wir im binären System nur 2 Zustände pro Stelle speichern können, dann müssen wir zur Darstellung größerer Zahlen als Ausgleich einfach mehr Stellen verwenden. Und da bietet sich wieder das schon bewährte Positionssystem an. Niemand verlangt, das es unbedingt Zehn als Basis für ein Positionssystem sein muss, so wie bei unserem Dezimalsystem.

Für ein Binärsystem verwenden wir daher die Zwei als Basis. Bei einer Binärzahl ändert sich also pro Stelle nach links die Wertigkeit um den Faktor 2, wenn man nach rechts geht, halbiert sich die Wertigkeit. Die Einerstelle ist wieder unsere Bezugsziffer und wird durch Komma oder Punkt gekennzeichnet. Hier ein Beispiel mit der Dezimalzahl 26.625, umgewandelt in eine Binärzahl:

                                                      1     1     1
26.625 = 11010.101 = 1*16 + 1*8 + 0*4 + 1*2 + 0*1 + 1*— + 0*— + 1*—
                                                      2     4     8

Bei den Dezimalzahlen haben wir festgestellt, das es Ungenauigkeiten geben kann, weil wir nur mit einer begrenzten Stellenzahl rechnen können. Natürlich treten diese Ungenauigkeiten auch bei Binärzahlen mit begrenzter Stellenzahl genauso auf.

Mein Computer zeigt aber Dezimalzahlen an

Alle Zahleneingaben und Ausgaben erfolgen (typisch) als Dezimalzahl. Das machen alle Programme, damit wir weiterhin unsere heißgeliebten Dezimalzahlen verwenden können und wir uns nicht direkt mit den Binärzahlen rumschlagen müssen. Bei allen Ein- und Ausgaben werden Zahlen also zwischen den Zahlenformaten "Dezimal" und "Binär" hin- und hergewandelt.

Intern werden die Zahlen aber typisch als Binärzahlen gespeichert und alle Rechnung erfolgen dann im Binärformat.

Ungenauigkeit durch Binärdarstellung

Wie wir oben schon gesehen haben, müssen wir die Stellenanzahl begrenzen und können daher weder alle Dezimal- noch Binärzahlen exakt speichern.

Wir haben auch gesehen, das sich manche Brüche nicht exakt als Dezimalbruch schreiben lassen, da sie periodisch sind.

Das gleiche Problem haben wir auch, wenn wir einen beliebigen Bruch in einen Binärbruch umwandeln, allerdings in noch etwas verschärfter Form! Einige Brüche, die sich noch exakt in einen Dezimalbruch umwandeln lassen, lassen sich nicht exakt in einen Binärbruch umwandeln!

Periodische Dezimalbrüche entstehen immer dann, wenn der Nenner des Bruchs andere Primfaktoren als 2 oder 5 enthält. Der Nenner eines Dezimalbruchs ist 10 (= 2*5), im Nenner des Dezimalbruchs sind also die Primfaktoren 2 und 5 enthalten.

Alle Brüche, deren Nenner keine anderen Primfaktoren als 2 und 5 enthalten, lassen sich immer in exakte Dezimalbrüche umwandeln (ausreichende Stellenanzahl vorausgesetzt).

Falls andere Primfaktoren enthalten sind und sich diese nicht wegkürzen lassen, ist keine exakte Umwandlung in einen Dezimalbruch möglich. Nun erkennen wir auch, warum wir solche Brüche wie 1/3 oder 1/7 nicht exakt in Dezimalbrüche umwandeln können, da 3 und 7 andere Primfaktoren sind!

Bei den Dezimalbrüchen haben wir im Nenner immerhin zwei Primfaktoren (2 und 5) und haben somit mehr Möglichkeiten, einen Bruch exakt in einen Dezimalbruch umzuwandeln, als dies bei Binärbrüchen möglich ist, da wir bei Binärbrüchen nur die 2 im Nenner haben!

Betrachten wir ein paar Zahlenbeispiele:

 25     5*5      1     0     1
——— = ——————— = ——— = ——— + ———
100   2*2*5*5   2*2    2     4

Fassen wir die Ursachen für die Ungenauigkeiten zusammen:

Wie vermeidet man Probleme in der Praxis?

Dieser Abschnitt gibt einige Hinweise für die Praxis. Allerdings werde ich mich kurz fassen da Sie ja nach Durcharbeitung des Artikel entsprechend vorsichtig und aufmerksam vorgehen werden :-)

• Computer verwenden intern Binärzahlen. Dezimalbrüche lassen sich oft nicht exakt in Binärbrüche umrechnen. Diese beiden Punkte sollte man immer im Hinterkopf haben.
• niemals zwei Float-Zahlen auf Gleichheit (oder Ungleichheit!) prüfen, besser auf größer oder kleiner
• Rechenergebnis nicht exakt auf 0 (oder anderen Wert) prüfen, besser gegen Schwelle prüfen
• Schwellen geeignet wählen, C bietet zB in float.h entsprechende Werte (FLT_EPSILON, DBL_EPSILON ...)
• Bei der Multiplikation kleiner Zahlen mit großen Zahlen holen wir die Ungenauigkeit in die höheren Stellen der Zahl.
  Beispiel: 1.234 * 1000 = 1233.999967
  Schneiden wir die Nachkommastellen einfach ab, erhalten wir nicht das erwartet Ergebnis 1234, sondern 1233!
  Aufrunden scheint hier auf den ersten Blick zu helfen, den nach dem Runden würde 1234 herauskommen.
  Doch: 1.2345 * 1000 = 1234.50005, Aufrundung würde jetzt zu 1235 führen!
  Solche Fälle muss man vermeiden, am besten durch einen anderen Rechenwege, eventuell hilft auch die Verwendung von BCD oder Integer-Zahlen. In der Praxis verwendet man oft auch "Schutzstellen", d.h., man verwendet intern für die Rechnung mehr Stellen, als man ausgibt. Das löst aber die grundsätzlichen Probleme nicht, den auch mit Schutzstellen haben wir weiterhin nur eine begrenzte Anzahl von Stellen. Allerdings werden die Fehler unter Verwendung von mehr Stellen natürlich entsprechend kleiner.
• Float-Zahlen nicht als Schleifenzähler verwenden, 10 * 0.1 führt z.B. nicht zu 1.0
• Genauigkeit float (32 Bit) ca. 6 Dezimalstellen, Genauigkeit double (64 Bit) ca. 15 Dezimalstellen. Diese Genauigkeit reicht für viele Berechnung problemlos aus und das Programm wird auch problemlos laufen, wenn man die gerade erwähnten Regeln beachtet.
• Finanzmathematik: Es ist vermutlich genau vorgeschrieben, wie viel Nachkommastellen mit welchen Algorithmen zu berechnen sind. Oft verwendet man hier BCD-Arithmetik (Zahlen werden als Dezimalzahlen gespeichert), eventuell auch selbst geschrieben Festkommaarithmetik oder spezielle Bibliotheken. Durch Verwendung einer Dezimal-Kodierung (BCD) kann man zwar die beschriebenen Umwandlungsfehler zwischen Dezimal- und Binärbrüchen vermeiden, aber alle anderen beschriebenen Ungenauigkeiten können trotzdem vorkommen.

Themen, auf die ich nicht weiter eingegangen bin:

• ich habe nicht im Detail erklärt, wie man Brüche in Dezimalbrüche oder Binärbrüche umrechnet. Für die Erklärung der Probleme ist es nicht so wichtig und im Netz finden sich bestimmt entsprechende Texte unter dem Stichwort "Dezimalbrüche".
• auf andere mögliche Rechenfehler, zB ungünstige Algorithmen, Rundungsfehler, Fehlerfortpflanzung etc. bin ich nicht weiter eingegangen.
• die genaue interne Darstellung der Binärzahlen habe ich nicht betrachtet, sie ist für das Thema nicht weiter wichtig, wenn durchaus auch interessant. Wer mehr darüber wissen will, suche zB nach "IEEE float format" etc.
• BCD-Arithmetik: Zahlen werden intern als Dezimalzahlen gespeichert und berechnet, die Ungenauigkeiten bei der Umwandlung von Dezimal nach Binär entfallen, aber die anderen Rechenfehler werden genauso auftreten.

Ich hoffe, der Artikel war hilfreich. Kommentare, Fehlerhinweise oder Verbesserungsvorschläge bitte an meine Email-Adresse senden.