Relevanz von Festkomma- und willkürlichen Präzisionsberechnungen

10

Ich sehe nur sehr wenige Nicht-Gleitkomma-Computer-Bibliotheken / -Pakete. Angesichts der verschiedenen Ungenauigkeiten der Gleitkommadarstellung stellt sich die Frage, warum es nicht zumindest einige Bereiche gibt, in denen diese erhöhte Genauigkeit die Komplexität der Arbeit mit Festkommawerten wert sein könnte.

Gibt es größere Schwierigkeiten bei der Verwendung beispielsweise eines Festpunkt-Eigenwertlösers? Wie langsam / schnell, ungenau / genau wären sie?

Verwandte: dies und das

Milind R.
quelle
Milind R, danke für deine Frage. Ich denke, Ihre Frage ist interessant, aber wahrscheinlich unangemessen für die Website. Ich fordere Sie dringend auf, die FAQ der Website zu lesen, um eine Anleitung zu erhalten. Wenn ich mir Ihre Frage ansehe, habe ich den Eindruck, dass dies der Beginn eines Geschwätzes ist, obwohl ich denke, dass die Elemente einer standortgerechten Frage vorhanden sind. Es lohnt sich zu fragen, ob es in der Computerwissenschaft viele Anwendungen der Ganzzahlarithmetik und der Festkomma-Arithmetik gibt, und nach einem Vergleich dieser Arithmetik mit dem Gleitkomma zu fragen. Ich empfehle Ihnen, Ihren Beitrag zu bearbeiten.
Geoff Oxberry
Ja, es wurde aus einem Schimpfen geboren, aber ich formulierte es als eine Rechtfertigung für den Status quo. Wie Sie vermuten können, geht es bei meiner Frage darum, warum wir in der intensiven Numerik keine größere Verschiebung hin zu Ganzzahl- und Festkomma-Mathematik haben können. Können Sie es bitte in meinem Namen bearbeiten? Ich habe es wirklich versucht, aber ich weiß nicht, wie meine Frage nicht angemessen ist.
Milind R
5
Ich denke, es gibt eine objektive technische Antwort darauf: Wenn Sie fast jede wissenschaftliche Berechnung ausführen (z. B. eine lineare Lösung), wächst die Anzahl der für die exakte Speicherung erforderlichen Bits mit der Zeit exponentiell. Daher ist für nützliche Arbeit eine starke Unterstützung für Ungenauigkeiten erforderlich.
Geoffrey Irving
@MilindR: Die Community für Computergeometrie war an reellen Zahlenberechnungen interessiert, die gleichzeitig sehr leistungsfähig und genau sind. Ich denke, dass alle für Sie relevanten praktischen Fragen in diesem Forschungsbereich beobachtet werden können. Ein Beispiel, nach dem Sie suchen könnten, ist die Bibliothek LEDA.
Shuhalo
@GeoffreyIrving Was ist mit Nullen in dreieckigen Matrizen? Können sie nicht als etwas anderes als ungenauer fehleranfälliger Gleitkomma gespeichert werden?
Milind R

Antworten:

5

Die Verwendung von Festkomma-Arithmetik kann unter bestimmten Umständen angebracht sein. Im Allgemeinen ist es für wissenschaftliches Rechnen (zumindest in dem Sinne, wie die meisten Leute es denken) nicht geeignet, da die großen Dynamikbereiche ausgedrückt werden müssen. Sie erwähnen als Beispiel Eigenwertprobleme, aber in der Wissenschaft interessiert man sich sehr oft für die kleinsten Eigenwerte einer Matrix (z. B. für die Berechnung des Grundzustands eines Quantensystems). Die Genauigkeit kleiner Eigenwerte wird im Allgemeinen im Vergleich zu großen Eigenwerten ziemlich verschlechtert, wenn Sie einen festen Punkt verwenden. Wenn Ihre Matrix Einträge enthält, die durch große Verhältnisse variieren, können die kleinen Eigenwerte in der Arbeitsgenauigkeit möglicherweise nicht ausgedrückt werden. Dies ist ein Problem bei der Darstellung von Zahlen; Diese Argumente gelten unabhängig davon, wie Sie die Zwischenberechnungen durchführen. Sie könnten möglicherweise eine Skalierung ausarbeiten, um sie auf die berechneten Ergebnisse anzuwenden, aber jetzt haben Sie gerade den Gleitkomma erfunden. Es ist leicht, Matrizen zu konstruieren, deren Elemente sich gut verhalten, deren Eigenwerte sich jedoch außerordentlich schlecht verhalten (wie zWilkinson-Matrizen oder sogar Matrizen mit vollständig ganzzahligen Einträgen ). Diese Beispiele sind nicht so pathologisch, wie es scheinen mag, und viele Probleme auf dem neuesten Stand der Wissenschaft betreffen Matrizen mit sehr schlechtem Verhalten. Daher ist die Verwendung von Fixpunkten in diesem Zusammenhang eine schlechte Idee (TM).

Sie könnten argumentieren, dass Sie die Größe der Ergebnisse kennen und keine Bits für den Exponenten verschwenden möchten. Lassen Sie uns also über die Zwischenprodukte sprechen. Die Verwendung von Festkomma verschärft im Allgemeinen die Auswirkungen von katastrophalen Stornierungen und Abrundungen, es sei denn, Sie haben wirklich große Mühe, präziser zu arbeiten. Der Leistungsverlust wäre enorm, und ich würde vermuten, dass die Verwendung einer Gleitkommadarstellung mit derselben Mantissenbitbreite schneller und genauer wäre.

Ein Bereich, in dem Fixpunkte leuchten können, sind bestimmte Bereiche des geometrischen Rechnens. Insbesondere wenn Sie eine genaue Arithmetik benötigen oder den Dynamikbereich aller Zahlen im Voraus kennen, können Sie mit dem Festkomma alle Bits in Ihrer Darstellung nutzen. Angenommen, Sie möchten den Schnittpunkt zweier Linien berechnen, und die Endpunkte der beiden Linien werden so normalisiert, dass sie im Einheitsquadrat liegen. In diesem Fall kann der Schnittpunkt mit größerer Genauigkeit dargestellt werden als unter Verwendung einer äquivalenten Gleitkommazahl (wodurch Bits auf dem Exponenten verschwendet werden). Nun ist es mit ziemlicher Sicherheit so, dass die für diese Berechnung erforderlichen Zwischenzahlen mit höherer Genauigkeit berechnet oder zumindest sehr sorgfältig durchgeführt werden müssen (Wenn Sie das Produkt aus zwei Zahlen durch eine andere Zahl teilen, müssen Sie sehr vorsichtig sein . In dieser Hinsicht ist der Festpunkt eher vom Standpunkt der Darstellung als vom Standpunkt der Berechnung aus vorteilhaft, und ich würde sogar sagen, dass dies im Allgemeinen der Fall ist, wenn Sie bestimmte Ober- und Untergrenzen für den Dynamikbereich Ihrer Algorithmusausgaben festlegen können . Das kommt selten vor.

Früher dachte ich, dass Gleitkomma-Darstellungen grob oder ungenau sind (warum Bits auf einem Exponenten verschwenden?!). Aber im Laufe der Zeit wurde mir klar, dass es wirklich eine der bestmöglichen Darstellungen für reelle Zahlen ist. Dinge in der Natur werden auf Protokollskalen angezeigt, sodass reale Daten einen großen Bereich von Exponenten umfassen. Um die höchstmögliche relative Genauigkeit zu erreichen, müssen Sie auch an Protokollskalen arbeiten, um die Verfolgung eines Exponenten natürlicher zu gestalten. Der einzige andere Anwärter auf eine "natürliche" Darstellung ist der symmetrische Pegelindex . Addition und Subtraktion sind in dieser Darstellung jedoch viel langsamer, und es fehlt die Hardware-Unterstützung von IEEE 754. Den Gleitkomma-Standards wurde eine enorme Menge an Gedanken gewidmetdurch eine Säule der numerischen linearen Algebra. Ich würde denken, er weiß, was die "richtige" Darstellung von Zahlen ist.

Victor Liu
quelle
4

Betrachten Sie Folgendes als Beispiel dafür, warum exakte Arithmetik / Festkomma-Arithmetik so selten verwendet wird:

  • Bei der Finite-Elemente-Methode kommen wir wie bei fast jeder anderen im wissenschaftlichen Rechnen verwendeten Methode zu linearen oder nichtlinearen Systemen, die nur Annäherungen an die reale Welt sind. Beispielsweise ist in der FEM das zu lösende lineare System nur eine Annäherung an die ursprüngliche partielle Differentialgleichung (die selbst nur eine Annäherung an die reale Welt sein kann). Warum also enorme Anstrengungen unternehmen, um etwas zu lösen, das nur eine Annäherung ist?

  • Die meisten der heute verwendeten Algorithmen sind iterativer Natur: Newtons Methode, Gradienten konjugieren usw. Wir beenden diese Iterationen immer dann, wenn wir uns davon überzeugt haben, dass die Genauigkeit der iterativen Annäherung an die Lösung des Problems ausreichend ist. Mit anderen Worten, wir beenden, bevor wir die genaue Lösung haben. Warum sollten wir nach wie vor exakte Arithmetik für ein iteratives Schema verwenden, wenn wir wissen, dass wir nur Näherungen berechnen?

Wolfgang Bangerth
quelle
Es ist frustrierend zuzugeben, aber ja, Ihre Antwort kreuzigt im Grunde genommen die Verwendung exakter Berechnungen in großem Maßstab. Ich schätze, ich werde floatbald nicht mehr die Rückseite sehen .
Milind R
@ MilindR: Ich bin mir nicht ganz sicher, was Sie anstreben. Sie scheinen einen Hammer zu haben und sind frustriert, dass niemand einen Nagel hat oder denkt, dass ein Hammer ein nützliches Werkzeug ist. Aber es liegt nicht daran, dass wir Sie nicht mögen - wir haben lange über diese Probleme nachgedacht und einfach entschieden, dass der Schraubenzieher, den wir haben, das richtige Werkzeug ist. Ich finde nichts Frustrierendes daran (es sei denn, Sie haben einen Hammer), da es nur ein pragmatischer Ansatz ist - warum exakte Arithmetik verwenden, wenn wir nur Annäherungen machen?
Wolfgang Bangerth
Es ist frustrierend, weil ein ganz normales Problem so schlecht konditioniert sein kann, dass es praktisch unlösbar ist. Ebenso, weil das Ideal der willkürlichen Präzision im Vergleich zu der Ungenauigkeit des Gleitkommas vom Speichern des Werts bis zur Ausgabe so vielversprechend aussah.
Milind R
Das Problem ist, dass Rundungsfehler äußerst schwer zu analysieren sind. Dies wurde mir an dem Tag klar, als ich anfing, numerische Analyse und numerische lineare Algebra zu lernen. Ein System, das das Problem vollständig vermeidet und das Konditionieren zum Problem macht, sollte die Welt im Sturm erobern, oder? war das Denken. Natürlich verstehe ich die Einschränkungen, aber sie schienen eher irritierend als Dealbreaker zu sein. Ein bisschen wie die erhöhte Schwierigkeit, Transistoren in Prozessoren zu verkleinern. Ja, es ist schwer zu analysieren, aber Intel macht es immer noch.
Milind R
1
Wenn ein Problem so schlecht konditioniert ist, dass es schwer zu lösen ist, ist seine Lösung nicht störungsstabil. Das ist ein Problem mit dem ursprünglichen Problem, nicht mit der Gleitkommadarstellung. Ja, vielleicht können Sie eine Lösung für das Problem mit exakter Darstellung finden. Aber die Lösung ist nicht stabil und wird wahrscheinlich nichts mit dem zu tun haben, wonach Sie wirklich suchen. Sie bellen den falschen Baum an, wenn Sie denken, dass die Darstellung von Zahlen das Problem ist.
Wolfgang Bangerth
3

Wenn Sie sich diese Bibliothek auf korrekte Rundung ansehen : CRlibm , werden Sie in der Dokumentation sehen, dass Algorithmen im Allgemeinen (mit begründeten Beweisen) als genau erwiesen werden müssen. Warum? Die Stabilität und Geschwindigkeit der Konvergenz eines Ergebnisses einer Funktion hat keine "Einheitslösung". Kurz gesagt, es gibt "kein kostenloses Mittagessen" - Sie müssen arbeiten, um zu beweisen, dass Ihre Argumentation richtig ist. Dies liegt am Verhalten der zu modellierenden Funktionen und nicht an der zugrunde liegenden Hardware (unabhängig davon, ob Sie Ganzzahl- oder Gleitkommaeinheiten verwenden, obwohl beide "Fallstricke" wie Überlauf / Unterlauf, Denormalzahlen usw. haben), selbst wenn das Ergebnis Wenn Sie nach Konvergenzen zu einer Ganzzahl suchen, ist der Algorithmus, mit dem das Ergebnis ermittelt wird, nicht unbedingt sehr stabil.

Eigen ist eine C ++ - Bibliothek mit einer Vielzahl von Algorithmen zum Lösen von Matrizen mit jeweils unterschiedlichen Eigenschaften. Diese Seite enthält eine Tabelle, in der die Kompromisse zwischen Geschwindigkeit und Genauigkeit für die verschiedenen Algorithmen zum Lösen einer Matrix erläutert werden. Ich vermute, die Eigenbibliothek kann machen, was Sie wollen. :-)

mda
quelle
Danke. Sehr informativer und netter Link. Aber führt die Verwendung von Fixpunkten zusammen mit einem begrenzten Rundungsgrad nicht zu genaueren Ausgaben? Da die Darstellung selbst im Gegensatz zum Gleitkomma zunächst exakt ist?
Milind R
1
Ich schlage vor, dass Sie Ihr Problem aus einem anderen Blickwinkel angreifen. In der Einführung in die Logik lernen Sie, dass die Lösung eines Problems drei Teile umfasst: Definitionen, Argumentation und Schlussfolgerung / Ergebnis. Sie sind wahrscheinlich (wie die meisten von uns) sehr daran gewöhnt, hauptsächlich am "Definitions" -Schritt der Problemlösung zu arbeiten - normalerweise können Sie Ihr Problem "wegdefinieren"; Wenn Sie jedoch frustriert sind, sind Sie gelegentlich auf eine schwierigere Art von Problem gestoßen, die mehr Arbeit im Teil "Argumentation" erfordert.
MDA
Ich verstehe dich nur vage ... Ich kann nicht sehen, wo ich dieses Problem "wegdefinieren" kann, die Argumentation ist wesentlich.
Milind R
Einige Jahre später verstehe ich dich tatsächlich :-)
Milind R
2

Einige schöne Beispiele dafür, wo hochpräzise Arithmetik in der Mathematik nützlich war, finden Sie in dem Buch Mathematics by Experiment von Jonathan Borwein und David Bailey. Es gibt auch diese Fortsetzung , die ich nicht gelesen habe.

David Ketcheson
quelle