| Home | Computer | Programmiersprachen | Site Map | |
In diesem Artikel geht es um ein Thema, das zumindest die meisten Programmierer angehen sollte, aber auch sehr interessant ist: Wie genau rechnen Computer? Dieser Artikel behandelt die Ansätze die man im Laufe der Entwicklung gefunden hat, um zu gewährleisten, dass man Computerergebnissen auch trauen kann.
Computer sind zum Rechnen da, und man erwartet, dass sie dies auch korrekt tun. Eine Bilanz eines Konzerns muss zumindest von der Rechnung her stimmen. (Es kann nicht sein, dass dieselben Daten auf Computer A ein anderes Ergebnis als bei Computer B liefern). Nun erscheint dies trivial und natürlich machen Computer (Von Ausnahmen wie dem Fliesskommabug beim Pentium abgesehen) beim Rechnen keine Fehler. Aber sie können nicht unendlich lange Zahlen verarbeiten und da liegt das Problem.
Das erste was man mit den frühesten Computern machte, war das Rechnen mit ganzen Zahlen. Je nach Computerarchitektur ist dadurch der Zahlenraum begrenzt. Als Zahlenraum bezeichnet man die Menge der ganzen Zahlen die in ein Wort, dass ist in der Regel die größte ganze Zahl die ein Computer verarbeiten kann, passen. Hierzu ein Beispiel: Ein 16 Bit Wort kann einen Bereich von 216 abdecken. Wenn man von 0 beginnt ist so die größte Zahl die man darstellen kann 65535 (216-1, da die 0 auch dazu zählt). Wenn man auch negative Zahlen darstellen will so halbiert man oft diesen Bereich und erhält einen Bereich von -32768 bis +32767.
Früher gab es Maschinen auch mit "krummen" Wortbreiten wie 18,22 oder 26 Bit. Damit kann man mit Ganzzahlen einen bestimmten Zahlenraum abdecken, der zu klein ist für viele Aufgaben.
Hierzu ein Beispiel:
Wir betrachten das Problem erst mal aus kaufmännischer Sicht, also beim Rechnen mit Geldbeträgen. Hier benötigt man eigentlich nur die vier Grundrechenarten, doch dürfen auch bei vielen Buchungen auf ein Konto keine Rundungsfehler entstehen.
16 Bit Prozessoren können wie dargelegt einen Zahlenraum von 0 bis 65535 abdecken (216-1). Das ist recht wenig und reicht wenn man in Cent als kleinster Einheit rechnet gerade mal bis 655.35 Euro. Wenn es negative Zahlen gibt, so wird der Bereich halbiert. Also nimmt man 2 Worte zusammen zu einem größeren 32 Bit Doppelwort. Dazu führt man eine Rechenoperation in zwei Schritten aus, wobei man jeweils einen Übertrag bildet. Mit einem solchen 32 Bit Wort könnte man schon einen Bereich von ± 20 Millionen abdecken, wenn man in Cent rechnet. Unglücklicherweise gibt es aber bei den meisten 16 Bit Prozessoren keine Befehle um 32 Bit Zahlen zu multiplizieren, wie man es bei der Zinsberechnung oder Mehrwertsteuerermittlung tun muss.
Diese Methode ist trotzdem sehr schnell, doch sie ist hochgradig von der Bitbreite des Prozessors abhängig. Das spielt heute keine Rolle mehr, doch bis in die siebziger Jahre gab es keine Standards wie 16, 32 oder 64 Bit Systeme sondern man passte die Architektur so an, wie sie möglichst optimal war. Die Firma DEC stellte in der PDP Serie z.B. 12,16,18,20 und 36 Bit Rechner her. Für eine höhere Programmiersprache war dies nicht gangbar, es musste eine Methode gefunden werden die gewährleistete, dass eine bestimmte Zahl auf jedem Rechner verarbeitet werden kann.
Der Datentyp "Currency" den es in manchen Programmiersprachen gibt wird über Ganzzahlen implementiert, weil hier keine beliebig langen Kommawerte wie bei Fließkommazahlen vorkommen. Der Trick ist einfach in der Ausgabe das Komma zu verschieben. Bei meinem System z.B. um 4 Stellen. So kann eine 64 Bit Ganzzahl einen Wertebereich von 15 Vorkomma- und 4 Nachkommastellen abdecken, was für finanztechnische Operationen vollkommen ausreuchend ist (selbst die Staatsverschuldung der USA umfasst (noch) nur 13 Vorkommastellen - sie kann also noch um den Faktor 100 ansteigen bis man an die Grenzen kommt - zumindest zahlentechnisch)
Als man an Formulierung der Programmiersprache COBOL ging, war man sich dieses Problems bewusst, doch war eben auch Ziel. diese Sprache für sehr viele Rechner verfügbar zu machen und Programme portabel zu gestalten. Es sollte unabhängig davon sein, wie die zahlen intern gespeichert werden. Heute würde man ein einheitliches Format definieren mit einer festgelegten Anzahl von Stellen, doch damals ging man andere Wege. COBOL arbeitete zeichenorientiert. Mathematische Operationen spielten keine große Rolle und die Sprache war mehr dazu gedacht, Datenverarbeitung zu erledigen.
So kam man auf die Idee die man als BCD bezeichnet: Binary Coded Dezimals. Die Zahlen werden nicht binär gespeichert, sondern als Zeichen.
Hierzu ein Beispiel: Der Wert 327 wird nicht als die Bitfolge 101000111 gespeichert (327 im Zweiersystem) sondern als die Werte der Ziffern im jeweiligen Zeichensatz der Maschine. Im ASCII Code z.B. hat die Ziffer "0" den Wert 48 und die "9" den Wert 57. So würde man hier die Zahlen als die Bitmuster
00110011 (51="3"), 00110010 (50 = "2") und 00110111 (55="7") speichern. Man benötigt also 24 Bits anstatt 9 Bits.
Man benötigt also erheblich mehr Speicherplatz, doch wenn man nur die Grundrechenarten für eine Ziffer implementiert kann man mit dieser Methode im Prinzip unendlich lange Zahlen bearbeiten. Es gibt also keinen Genauigkeitsverlust.
Später hat man dieses Prinzip noch etwas verbessert, indem man die gepackten BCD's einführte, als sich das Byte mit 8 Bit allgemein durchsetzte (COBOL kam ursprünglich mit einem Zeichenvorrat von 64 Zeichen (6 Bits) aus). Hierzu speichert man nicht den Wert im Zeichensatz sondern in jeweils 4 Bit eines Bytes eine Ziffer ab. Man kann also mit einem Byte zwei Ziffern speichern. Mikroprozessoren verfügen oft über bestimmte Befehle mit denen man die Grundrechenarten in solchen BCD Ziffern machen kann und früher gab es eigene Versionen von Turbo Pascal die spezielle BCD Arithmetik boten.
Man muss dazu nach einer normalen Rechnung das Ergebnis anpassen, da die Werte von 10..15 in den jeweiligen 4 Bits einer gepackten BCD Darstellung nicht benutzt werden, d.h. man muss diese in die höhere Ziffer übertragen.
BCD ist eine Lösung wenn man nie weiß, wie groß die Ziffern sind und immer genaue Rechnungen haben will. Das Rechnen ist aber langsam und auf die Grundrechenarten begrenzt. Mit dieser Methode kann man keinen Sinus berechnen und sehr kleine Zahlen oder sehr große Zahlen (Die Masse der Erde in Kilogramm) erfordern einen enormen Rechenaufwand, weil man sehr viele Stellen angeben muss. (Es gibt keine Exponentialdarstellung). Trotzdem ist dieses Format ideal, wenn man es um die Verarbeitung von Daten geht, auch weil man BCD's sehr gut als ASCII Zeichen speichern kann oder einfach in einem bestimmten Format durch Einfügung von Tausender Trennzeichen ausgeben will. Es ist daher bei Datenbanken auch heute noch weit verbreitet.
Wenn man den kaufmännischen Bereich verlässt kommt man sehr bald beim wissenschaftlichen Bereich auf ein anderes Problem: Zahlen können dort sehr groß sein (1080: Anzahl der Elementarteilchen im Universum ) oder sehr klein (10-43: Zeit in Sekunden nach dem Urknall, ab der man über den Zustand des Universums eine Aussage machen kann.) Derartig lange Zahlen mit BCD abzubilden ist unmöglich und zur Abspeicherung in einem Computerwort brauchte man für einen Bereich von 10-43 bis 1080 einen 409 Bit Computer.
Man hat daher begonnen die Zahl zu splitten. In den meisten Implementierungen ging man so vor :
Man kann zwar damit keine 80 Stellen einer Zahl darstellen, aber die ersten 7, 15 oder 20 Stellen. Der Rest ist dann nicht definiert, man hat so eine begrenzte Genauigkeit. Die Zahl sind immer die signifikanten Stellen. Der Exponent gibt praktisch die nachfolgenden Nullen (bei großen Zahlen) oder die führenden Nullen (bei kleinen Zahlen) an.
Hierzu ein Beispiel: 12345000000 und 0.000000012345 belegen in diesem Format nur 5 Stellen (1.2345), aber der Wert für den Exponent ist jeweils unterschiedlich. Im Ersten Fall ist er +10 und im zweiten bei -8. Man kann also sehr große Zahlen und sehr kleine Zahlen darstellen, nur für jede Zahl ist die Genauigkeit auf eine bestimmte Stellenzahl begrenzt.
Obgleich das Rechnen mit solchen Zahlenformaten die intern in ihre Bestandteile zerlegt werden müssen, aufwendiger ist, hat es sich im wissenschaftlichen Bereich durchgesetzt. Nahezu alle Sprachen bieten Zahlen im Fliesskommaformat. Die Langsamkeit wurde durch spezielle Coprozessoren ausgeglichen, die heute in den Prozessoren integriert sind. Ohne diese wird das Rechnen mit diesen Zahlen langsam. So brauchte ein 8086 Prozessor für eine Multiplikation z.B. 3.2 ms, mit dem numerischen Coprozessor 8087 aber nur noch 0.01 ms. Er war also um den Faktor 320 schneller.
Ein Format hat nur einen Sinn, wenn es standardisiert ist. Ähnlich wie es früher Rechner mit allen möglichen Bitbreiten gab, waren auch die Formate für Fliesskommazahlen nicht standardisiert. Der erste Rechner des Autors z.B. verwendete 7 Bytes für eine Fliesskommazahl (Genauigkeit 14 Stellen), der nächste 4 oder 8 (7 bzw. 15 Stellen) und die nächste Programmiersprache verwandte 6 Bytes (Genauigkeit 11 Stellen). Damit waren aber Programme wiederum nicht portabel.
So ging die Vereinigung IEEE daran einen Standard zu kreieren, der zwei Genauigkeiten definierte. Dieser ist als IEEE bekannt geworden und definiert folgende Formate
Einfache Genauigkeit (single, float bei vielen Programmiersprachen):
4 Bytes Speicherplatz pro Zahl. Davon 1 Vorzeichenbit, 23 Bits für die Zahl und 8 Bits für den Exponenten. Genauigkeit: mind. 7 Stellen, Bereich des Exponenten von ± 38
Doppelte Genauigkeit (double)
8 Bytes Speicherplatz pro Zahl, Davon 1 Vorzeichenbit, 52 Bits für die Mantisse und 11 Bits für den Exponenten. Genauigkeit mind. 15 Stellen, Bereich des Exponenten: ± 307
Praktische Bedeutung hat eigentlich nur das zweite Format, den 7 Stellen Genauigkeit heißt, dass man schon Zahlen im Bereich von 1 Million Probleme hat, wenn man in Geldbeträgen rechnet (1 Million hat 7 Stellen, dazu kommen 2 für die Pfennigbeträge). Für die Wissenschaft ist auch der Bereich des Exponenten in manchen Fällen zu klein.
Das im Coprozessor 8087 implementierte (und bei vielen Compilern auf Intel Rechnern auch verfügbare) 10 Byte lange Format mit einer Genauigkeit von 19 Stellen ist kein IEEE Format. Konsequenterweise hat Intel es beim 64 Bit Nachfolger Itanium auch nicht implementiert.
Mit dem IEEE Format ist natürlich nicht nur garantiert, dass Ergebnisse auf verschiedenen Rechnern vergleichbar sind, nein dadurch wird auch der Datenaustausch zwischen Rechnern (sei es über Datenträger wie auch Netzwerk) erleichtert. So benutzt das Netzwerkprotokoll RPC z.B. das IEEE 754 Format für Fliesskommazahlen.
Es gab in den letzten 20 Jahren keinen Bedarf an noch mehr Genauigkeit. Auch Supercomputer nutzen meist dieses Format, auch wenn einige Rechner durch Zusammenfassen von Registern ein 128 Bit Format anboten, allerdings auf Kosten der Geschwindigkeit. Zur Verbreitung hat sich auch mit beigetragen, das Zahlen in diesem Format 64 Bits umfassen und das ist just die Datenbreite welche die meisten Großrechner und Workstations aufweisen.
2008 wurde der IEEE 754 Standard erweitert um ein 16 Bit Format (das nur 10 Bit für die Mantisse übrig lässt, das sind nur 3-4 Dezimalstellen) wahrscheinlich für die Berechnung von 3D Szenen mit GPU, bei denen aufgrund der begrenzten Auflösung des Monitors es nicht nötig ist eine höhere Genauigkeit zu erreichen, sowie ein 128 Bit Format für noch höhere Genauigkeit. Die Unterstützung dieses ist aber noch nicht sehr groß. Zwar haben inzwischen die meisten Prozessoren Flieskommaeinheiten die länger als 64 Bit sind (typisch 128 oder 256 Bit), doch diese werden genutzt um dann zwei oder vier 64 Bit Zahlen derselben Rechenoperation zu unterziehen.
Nun ist es an der Zeit festzustellen, wo es Probleme bei Rechnungen geben kann. Betrachtet man zuerst die Addition und Subtraktion. Diese können sehr gutmütig sein, wenn die Zahlen in der gleichen Größenordnung sind. Dies ist z.B. bei kaufmännischen Rechnungen der Fall. Es wird hier je nach Währung nie mehr als 2-4 Nachkommastellen geben. Doch was passiert wenn man zu einer großen Zahl eine kleine addiert? Wenn man z.B. die Störeinflüsse von Jupiter auf die Erde berechnet, so ist dieser Wert klein und wird zum großen Wert der Umlaufgeschwindigkeit der Erde addiert. In diesem Fall kann es im Extremfall dazu kommen dass ein Wert mit m Vorkommastellen zu einem mit n Nachkommastellen addiert werden und man für die korrekte Darstellung des Ergebnisses m+n stellen braucht.
Bei dieser Rechenoperation ist es die Regel, dass wenn man zwei Zahlen mit n und m Stellen multipliziert, das Ergebnis m+n Stellen hat. Es gibt einige gutmütige Ausnahmen wie (0.5*2), doch diese sind eben nur Ausnahmen. Das bedeutet aber auch das schon wenige Multiplikationen einen Genauigkeitsverlust bedeuten. Bei 4 Stellen sind es schon 4 Rechenoperationen die 16 Stellen Genauigkeit erfordern, also mehr als das doppelt genaue IEEE 754 Format hergibt.
Bei den meisten Zahlen erhält man bei Divisionen eine nicht endende Folge von Zahlen, die zwar periodisch sein kann aber nicht abbricht. Schon bei ganzen Zahlen wie 1/7 oder 1/3 ist dies der Fall. Dasselbe gilt für die trigonmetrischen Funktionen und Logarithmus / Exponentialfunktion und Wurzeln. Hier sind nicht periodische Zahlenfolgen sogar die Regel.
Neben dem für jeden offensichtlichen Fall bei den Finanzen ist es vor allem bei Simulationen wichtig. Betrachtet man die mathematischen Operationen, so sind es Division, Multiplikation und Exponentialfunktion. Finanzen sind zwar ein gutes Beispiel, aber eigentlich unkritisch, denn es gibt hier Regeln für die Rundung. D.h. man kann Sub-Cent Beträge nach unten oder oben runden, muss aber nicht mit den Bruchteilen weiterrechnen.
Im Naturwissenschaftlichen Bereich geht das oft nicht. Ein sehr bekanntes Beispiel ist der Schmetterlings-Effekt: Als ein Wissenschaftler eine Klima-Simulation durchlaufen ließ, speicherte er die Daten ab und rechnete mit ihnen später weiter. Eine zweite Simulation mit denselben Daten, aber ohne Speicherung ergab aber deutliche Abweichungen. Der Grund war, dass der Wissenschaftler die Daten nicht in der internen Repräsentation abspeicherte sondern gerundet, z.B. aus 1011,2783484746565433 mBar Druck 1011,278 abspeicherte, weil es keinen Druckmesser gibt, der Tausendstel Millibar angeben kann. Diese kleinen Abweichungen aber bewirken eine Veränderung des Wetters über lange Zeiten.
Vor allem aber können sich kleine Fehler addieren. Nehmen wir mal die Differentialrechnung. Wenn man die Formel einer Ableitung nicht kennt kann man ihren Funktionswert so bestimmen:
f'(x) = (f(x+dx)-f(x))/dx
dx ist ein sehr kleines Intervall. Was macht man also ? Man teilt einen kleinen Wertunterschied durch einen noch kleineren Wert. Das geht hier vielleicht noch gut, doch bei der nächsten Ableitung macht man das gleiche nur setzt man hier anstatt f(x) f'(x) ein, d.h. man verwendet einen fehlerbehafteten Wert als Basis für eine Berechnung. Damit potenziert sich der Fehler.
Eine Analogie findet man beim schon erwähnten Schmetterlingseffekt: hier führt ein Programm mehrere tausendmal eine Berechnung aus und an der letzten Stelle ist das Ergebnis in der Regel ungenau. So schaukeln sich Fehler auf.
Damit man dies mal sehen kann habe ich in Pascal 3000 mal den Wert "1/3" addiert. Das ist natürlich eine Folge mit unendlich vielen Dezimalstellen die irgendwo gerundet werden muss. Hier beginnt der Fehler und er addiert sich über 3000 Additionen. Es sollte nun ja 1000 heraus kommen (3000*1/3):
var
a: Single; // 7 Stellen Genauigkeit
b: Real48; // 11 Stellen Genauigkeit
c: Double; // 15 Stellen Genauigkeit
d: Extended; // 19 Stellen Genauigkeit
begin
a:=0;
b:=0;
c:=0;
d:=0;
for i:=1 to 3000 do
begin
a:=a+1/3;
b:=b+1/3;
c:=c+1/3;
d:=d+1/3;
end;
WriteLn(a);
WriteLn(b);
WriteLn(c);
WriteLn(d);
end;
Es sollte der Wert 1000 herauskommen, doch man erhält folgende Ergebnisse:
Nur mit Extended (80 Bit, 19 stellen Genauigkeit) als Format bekommt man korrekte Ergebnisse, das ändert sich aber wenn man von 3000 auf 30 Millionen Durchgänge erhöht:
Nun gibt es auch bei 19 Stellen Fehler. Bei 7-8 Stellen ist er schon riesig. Der Wert liegt um 20% daneben!
Nun ist aber das Wesen von Simulationen dass man sehr kleine Schritte von einem Zustand zum anderen macht, d.h. sich Werte also nur langsam verändern. Wenn man also simulieren will wie sich die Planetenbahnen im Laufe von Jahrmillionen verändern wird man pro Tag eine Positions- und Störungsrechnung machen und diese über mehrere Milliarden Zyklen wiederholen. Es ist dann klar dass schon kleinste Rundungsfehler von Bedeutung sind.
Wie schon erwähnt sind andere Rechenoperationen wie Division. hier noch kritischer, daher spielt die Wahl eines Algorithmus eine wichtige Rolle. Vor allem aber gibt es Probleme bei Prüfungen auf das Erreichen eines Wertes (meistens 0). Es ist deswegen nicht sinnvoll einen Fliesskommawert auf einen bestimmten Wert hin zu prüfen. Will man z.B. bei einer numerischen Differentiation Hoch und Tiefpunkte finden, so liegen diese vor wenn die Ableitung 0 ist. Durch die Ungenauigkeiten in der Rechnung wird man aber selten 0 bekommen, egal wie klein man die Schritte macht. Hier prüft man besser ab ob ein Wert innerhalb eines Intervalls ist z.B.:
anstatt zu schreiben:
if wert=5 then Beende_Programm;
schreibt man besser:
if Abs(wert-5)<1E-10 then Beende_Programm;
Hier wird also mit einer Abweichung gerechnet die max. 0.0000000001 betragen kann. Durch den Absolutwert darf sie in beiden Richtungen (4.9999... oder 5.0000...) auftreten.
Das IEEE Format hat sich seit 20 Jahren bewährt und Intel hat im Itanium Prozessor z.B. das noch weitergehende Format des 80x87 Coprozessors nicht mehr implementiert. 15 Stellen Genauigkeit reichen auch heute noch bei komplexen Simulationen aus. Es stellt sich daher die Frage ob es in Zukunft noch Bedarf an einer noch höheren Genauigkeit gibt.
Das IEEE 754 Format ist natürlich auch an die Computerarchitekturen gebunden. Die Breite eines Wertes beträgt 32 bzw. 64 Bit und ist somit maßgeschneidert für 64 Bit Prozessoren oder 32 Bit Prozessoren. Architekturen dieser Größe gibt es seit 1976 und seitdem hat auch keiner die Anstrengung unternommen eine 96 oder 128 Bit Architektur aufzubauen. Sowohl von dem verfügbaren adressierbaren Arbeitsspeicher wie auch der Größe der elementaren Daten gibt es keine Notwendigkeit eine größere Architektur aufzubauen. 64 Bit haben sich also seit fast 30 Jahren bewährt.
Mit der Zusammenfassung de Standards mit IEEE 854 und den finanzmathematischen Formaten deckt es heute alles ab was nötig ist und mit dem neuen 128 Bit Fromat gibt es auch noch "Luft" für zukünftige Prozessoren. Die 112 Bit der Mantisse umfassen nun 33 Dezimalstellen - das sind mehr als doppelt so viele wie beim 64 Bit Format.
Zum Thema Computer ist auch von mir ein Buch erschienen. "Computergeschichte(n)" beinhaltet, das was der Titel aussagt: einzelne Episoden aus der Frühzeit des PC. Es sind Episoden aus den Lebensläufen von Ed Roberts, Bill Gates, Steve Jobs, Stephen Wozniak, Gary Kildall, Adam Osborne, Jack Tramiel und Chuck Peddle und wie sie den PC schufen.
Das Buch wird abgerundet durch eine kurze Erklärung der Computertechnik vor dem PC, sowie einer Zusammenfassung was danach geschah, als die Claims abgesteckt waren. Ich habe versucht ein Buch zu schreiben, dass sie dahingehend von anderen Büchern abhebt, dass es nicht nur Geschichte erzählt sondern auch erklärt warum bestimmte Produkte erfolgreich waren, also auf die Technik eingeht.
Die 2014 erschienene zweite Auflage wurde aktualisiert und leicht erweitert. Die umfangreichste Änderung ist ein 60 Seiten starkes Kapitel über Seymour Cray und die von ihm entworfenen Supercomputer. Bedingt durch Preissenkungen bei Neuauflagen ist es mit 19,90 Euro trotz gestiegenem Umfang um 5 Euro billiger als die erste Auflage. Es ist auch als e-Book für 10,99 Euro erschienen.
Mehr über das Buch auf dieser eigenen Seite.
Hier geht's zur Gesamtübersicht meiner Bücher mit direkten Links zum BOD-Buchshop. Die Bücher sind aber auch direkt im Buchhandel bestellbar (da ich über sehr spezielle Themen schreibe, wird man sie wohl kaum in der Auslage finden) und sie sind natürlich in den gängigen Online-Plattformen wie Amazon, Libri, Buecher.de erhältlich.
| Sitemap | Kontakt | Impressum / Datenschutz | Neues | Hier werben / advertisment here | Buchshop | Bücher vom Autor |
|