Die Probleme mit den Rundungen

17 September 2013 by Benjamin Hiller, posted in Computer Science, Deutscher Blog, General

Ja, ich habe die Ehre, beim ersten Heidelberg Laureate Forum dabei sein und darüber bloggen zu dürfen. Auf der Suche nach spannenden Blogthemen sticht mir im Vortragsprogramm der Vortragstitel "Desperately needed remedies for the undebuggability of large-scale floating-point computations in science and engineering" von William Morton Kahan ins Auge. Was verbirgt sich hinter diesem sperrigen Titel? Ein Problem, mit dem ich mich in meiner Arbeit häufiger herumschlage.

William Morton Kahan
Foto © Klaus Tschira Stiftung / Peter Badge

In wissenschaftlichen Rechnungen treten Zahlen sehr unterschiedlicher Größenordnungen auf. Um damit effizient rechnen zu können, werden sie als Gleitkommazahlen (engl.: "floating point numbers") gespeichert. Die Grundidee für Gleitkommazahlen ist einfach: Eine Zahl wird als Produkt einer Zahl zwischen 1 und 10 und einer Zehnerpotenz geschrieben, z.B. die Lichtgeschwindigkeit als 2,99792458×108 statt 299792458 Meter pro Sekunde. Gleitkommazahlen bestehen also aus zwei Zahlen: die Mantisse entspricht der Zahl zwischen 1 und 10 und speichert sozusagen die Ziffern, während der Exponent der Zehnerpotenz die Größenordnung angibt. Damit der Speicherbedarf und auch die Zeit für Rechenoperationen nicht von der Größe der Zahl abhängen, enthält die Darstellung einer Gleitkommazahl im Computer nur eine feste Anzahl von Ziffern. Werden z.B. nur 4 Ziffern gespeichert, so wird statt des korrekten Werts der Lichtgeschwindigkeit mit 2,998×108 gerechnet. Gleitkommazahlen wurden übrigens von Konrad Zuse, einem deutschen Ingenieur, zuerst in Rechenmaschinen eingesetzt.

Die Z3, der erste programmierbare Computer der Welt, unterstützte bereits Gleitkommazahlen.
Foto © Wikimedia, GFDL

Praktisch bedeutet die Beschränkung auf wenige Ziffern, dass fast alle Zahlen gerundet werden müssen, was natürlich zu Rundungsfehlern führt. Außerdem entstehen weitere Fehler durch das Runden nach jeder Rechenoperation, da jedes Zwischenergebnis wieder als Gleitkommazahl mit beschränkter Genauigkeit gespeichert wird.

Ein einfaches Beispiel ist die Addition von Zahlen verschiedener Größenordnung. Nehmen wir an, dass für die Mantisse nur vier gültige Stellen zur Verfügung stehen. Dann führt die Berechnung von 10000 + 1, in Gleitkommadarstellung also 1,000×105 + 1,000×100, zu dem Ergebnis 1,000×105 = 10000, weil der Unterschied der Summanden zu klein ist, um mit vier Stellen erfasst zu werden. Dieser kleine Fehler kann sich schnell aufschaukeln: Wird zu 1,000×105 zehnmal 1,000×100 = 1 addiert, so ist das Ergebnis immer noch 1,000×105, obwohl 1,001×105 = 10010 korrekt und darstellbar wäre. Diesen Fehler kann man vermeiden, indem die Zahlen vor der Addition aufsteigend nach Betrag sortiert werden. Es ergibt sich dann zunächst die Summe 1,000×101 = 10 aus den zehn kleinen Zahlen, was fehlerfrei zu der großen Zahl addiert werden kann.

Eine besonders elegante Alternative wurde von Kahan entwickelt. Für diese und andere Arbeiten zum Rechnen mit Gleitkommazahlen hat er den Turing-Preis bekommen. In vielen anderen Fällen ist es ebenfalls möglich, durch sorgfältige Analyse und Programmierung die Effekte der Rundungsfehler gering zu halten.

Was hat das nun mit meiner Arbeit zu tun? Ich arbeite an mathematischen Optimierungsverfahren, in denen sehr komplexe Rechenoperationen mit Gleitkommazahlen ausgeführt werden -- also genau die "large-scale floating-point computations", auf die Kahan mit seinem Vortrag abzielt. Ein wesentlicher Teil der Arbeit dabei ist die Fehlersuche oder neudeutsch das Debugging. Die meisten Fehler sind relativ leicht zu finden und zu beheben. Es ist aber öfter auch unklar, ob ein falsches Progammverhalten wirklich ein echter Programmierfehler (ein "Bug") oder ein Problem mit der Gleitkomma-Arithmetik ist. Und selbst wenn es klar ein Gleitkomma-Problem ist, ist es meist nicht einfach zu beheben, weil die Rechenoperationen über viele Programmteile verteilt sind. Eine Analyse und die Entwicklung robusterer Verfahren ist dann nur schwer möglich. Ich benötige daher wirklich dringend Abhilfe in diesen Fällen -- und Ideen dazu verspricht der Vortrag von William Morton Kahan. Ich bin gespannt.

Leave a Reply


5 − = four