Berechnung von Reals: Gleitkomma vs TTE vs Domänentheorie vs etc
19
Gegenwärtig erfolgt die Berechnung von Real in den meisten gängigen Sprachen immer noch über Gleitkommaoperationen. Andererseits haben Theorien wie die Typ-2-Effektivität (TTE) und die Domänentheorie lange Zeit eine genaue Berechnung der Realzahlen versprochen. Das Problem der Fließkommapräzision hat natürlich nicht an Relevanz verloren. Warum sind diese Theorien nicht mehr zum Mainstream geworden und warum gibt es keine auffälligeren Implementierungen?
Gibt es beispielsweise Anwendungsbereiche, in denen Gleitkommafehler keine große Rolle spielen? Gibt es signifikante Komplexitätsprobleme?
Ich arbeite in der Berechnung von reellen Zahlen und ich wünschte, ich wüsste die reale Antwort. Aber ich kann spekulieren. Es ist ein soziologisches Problem, denke ich.
Die Community der Leute, die an exakten reellen Arithmetikern arbeiten, besteht aus Theoretikern, die nicht daran gewöhnt sind, Software zu entwickeln. Daher geben sie die Implementierungsaufgabe in der Regel an die Schüler ab (eine bemerkenswerte Ausnahme ist Norbert Müllers iRRAM ), oder sie haben ihre eigenen Spielzeugimplementierungen .
Leute , die tun die notwendige Programmierung haben Mojo nicht über die notwendigen theoretischen Hintergrund haben. Ohne eine solide theoretische Grundlage ist es schwierig, eine exakte echte Arithmetik korrekt zu entwerfen. Zum Beispiel ist es ein Fehler, viele reelle Zahlen in eine forSchleife einzufügen, da Sie aufgrund von Genauigkeitsverlusten eine inakzeptable Leistung erzielen. Wenn Sie viele, viele Realwerte hinzufügen möchten, sollten Sie dies mit einer baumartigen Struktur tun, wobei die Größen der Teilsummen berücksichtigt werden. Eine andere Sache , die nur schwer zu vermitteln ist , dass <und =wie Gesamt Boolesche Funktion auf den reellen Zahlen einfach nicht existieren (Sie können haben , =aber es entweder zurückkehrt falseoder divergiert, und <divergiert , wenn zwei gleich reellen Zahlen angegeben).
Schließlich ist es überhaupt nicht klar, wie man Bibliotheken für exakte echte Arithmetik implementiert. Es sind nicht die üblichen Bibliotheksbestandteile, die lediglich einige Datentypen und einige Funktionen definieren. Oft erfordert eine exakte echte Arithmetik spezielle Steuerungsmodi. Zum Beispiel übernimmt iRRAM die Hauptausführung des Programms (buchstäblich Hijacks main) sowie die Standardeingabe und -ausgabe, so dass es das Programm bei einem Genauigkeitsverlust erneut ausführen kann. Meine Bibliothek für echte Arithmetik in Haskell besteht aus einer StagedMonade (die im Wesentlichen die ReaderMonade ist). Die meisten Leute erwarten, dass die reellen Zahlen "nur ein anderer Datentyp" sind, aber ich habe meine Zweifel daran.
Ich weiß fast nichts über exakte echte Arithmetik, aber konnte man keine Kahan-Summierung darin implementieren?
JJG
1
Hmm, ich denke nicht. Stellen Sie sich exakte reelle Arithmetik als Intervallarithmetik vor, die die Zwischengenauigkeit automatisch anpasst, um die gewünschte Ausgabegenauigkeit zu erzielen.
Andrej Bauer
3
Neben dem mangelnden Verständnis der Programmierer für die Tatsache, dass reelle Zahlen unendliche Objekte sind und deren Konsequenzen für die programmgesteuerte Ausführung, halte ich mangelnde Hardware-Unterstützung auch für wichtig. Es ist schwer, Menschen davon zu überzeugen, etwas mit erheblichem Zeit- und Speicheraufwand nur für die Richtigkeit zu verwenden.
Kaveh
1
Ich habe gesehen, dass es einige Aktivitäten gibt, echte Berechnungen mit coinduktiven Typen zu implementieren. Ich habe das Gefühl, dass es immer noch recht schwierig ist, koinduktive Typen zu finden (da bin ich sicherlich kein Experte), aber ist dies Ihrer Meinung nach vielversprechender für eine umfassendere Verwendung der exakten realen Berechnung?
SorcererofDM
3
Jede Implementierung, die Zahlenströme verwendet, oder alles andere, das eine feste Konvergenzrate aufweist, ist von Anfang an dahingehend benachteiligt, dass es zu langsam konvergiert. Stream-basierte Implementierungen zwingen Sie außerdem dazu, alle vorherigen Näherungen zu berechnen, um die nächste zu erhalten, was ebenfalls ein Konstruktionsfehler ist.
Andrej Bauer
10
Im Allgemeinen interessieren sich Menschen immer für Gleitkommafehler. Ich bin jedoch anderer Meinung als Andrej und glaube nicht, dass Floats aus soziologischen Gründen (größtenteils) willkürlichen Präzisionsrealwerten vorgezogen werden.
Ich glaube, das Hauptargument gegen die exakte Berechnung von Real ist das der Leistung . Die kurze Antwort lautet also: Wenn Leistung wichtiger als Präzision ist, sollten Sie Gleitkommazahlen verwenden .
Die Anwendung, die in den Sinn kommt, ist die Verwendung der rechnergestützten Fluiddynamik zum Entwerfen der Aerodynamik von Autos oder Flugzeugen, bei der kleine Rechenfehler leicht mit den astronomischen Vorteilen der Verwendung dedizierter Gleitkommaeinheiten, die in vielen weit verbreiteten Prozessoren zu finden sind, kompensiert werden können.
Insbesondere ist das Problem der Darstellung eines weiten Bereichs von reellen Zahlen unter Verwendung einer festen Anzahl von Bits nicht so trivial, wie es auf den ersten Blick erscheinen mag. In der numerischen Simulation können die Werte stark variieren (z. B. bei Turbulenzen), sodass Festkommaberechnungen nicht geeignet sind.
Selbst wenn die Genauigkeit nicht durch die Hardware festgelegt ist, kann die Verwendung von Zahlen mit beliebiger Genauigkeit um mehrere Größenordnungen langsamer sein als die Verwendung von Gleitkommazahlen. Selbst wenn alle Zahlen rational sind, können einfache Operationen wie das Invertieren einer Matrix zu großen, schwer zu kontrollierenden Nennern führen (siehe hier für ein Beispiel). Viele große lineare Optimierungspakete verwenden Gleitkommawerte mit geeigneten Rundungsmodi, um ungefähre Lösungen zu finden, und zwar aufgrund dieses genauen Problems (siehe beispielsweise die Mehrheit der hier gefundenen Programme ).
Gibt es nachgewiesene Lücken zwischen einer Form der exakten reellen Berechnung und der Gleitkommaberechnung?
SorcererofDM
1
Nicht, dass ich wüsste, ich fürchte. Sean Gao hat einige interessante Ergebnisse über die Komplexität von Näherungsentscheidungsverfahren über den Real (siehe Zusammenfassung seiner Dissertation ) und natürlich wächst der Nenner in der Umkehrung einer Matrix im schlimmsten Fall wie seine Determinante .
Cody
-6
π
Mein Punkt ist, dass, wenn Sie genau berechnen wollen, Sie Platzhalter für die speziellen Namen sowie die vertrauten Namen der Naturals haben müssen. Irgendwann werden Sie den genauen Wert approximieren wollen, um ihn auf etwas in der realen Welt anzuwenden. Wie sich herausstellt, ist es viel effizienter, das gesamte Problem von Anfang an als Annäherung zu betrachten, es sei denn, Sie haben sehr spezielle Anforderungen.
Im Allgemeinen interessieren sich Menschen immer für Gleitkommafehler. Ich bin jedoch anderer Meinung als Andrej und glaube nicht, dass Floats aus soziologischen Gründen (größtenteils) willkürlichen Präzisionsrealwerten vorgezogen werden.
Ich glaube, das Hauptargument gegen die exakte Berechnung von Real ist das der Leistung . Die kurze Antwort lautet also: Wenn Leistung wichtiger als Präzision ist, sollten Sie Gleitkommazahlen verwenden .
Die Anwendung, die in den Sinn kommt, ist die Verwendung der rechnergestützten Fluiddynamik zum Entwerfen der Aerodynamik von Autos oder Flugzeugen, bei der kleine Rechenfehler leicht mit den astronomischen Vorteilen der Verwendung dedizierter Gleitkommaeinheiten, die in vielen weit verbreiteten Prozessoren zu finden sind, kompensiert werden können.
Insbesondere ist das Problem der Darstellung eines weiten Bereichs von reellen Zahlen unter Verwendung einer festen Anzahl von Bits nicht so trivial, wie es auf den ersten Blick erscheinen mag. In der numerischen Simulation können die Werte stark variieren (z. B. bei Turbulenzen), sodass Festkommaberechnungen nicht geeignet sind.
Selbst wenn die Genauigkeit nicht durch die Hardware festgelegt ist, kann die Verwendung von Zahlen mit beliebiger Genauigkeit um mehrere Größenordnungen langsamer sein als die Verwendung von Gleitkommazahlen. Selbst wenn alle Zahlen rational sind, können einfache Operationen wie das Invertieren einer Matrix zu großen, schwer zu kontrollierenden Nennern führen (siehe hier für ein Beispiel). Viele große lineare Optimierungspakete verwenden Gleitkommawerte mit geeigneten Rundungsmodi, um ungefähre Lösungen zu finden, und zwar aufgrund dieses genauen Problems (siehe beispielsweise die Mehrheit der hier gefundenen Programme ).
quelle
Mein Punkt ist, dass, wenn Sie genau berechnen wollen, Sie Platzhalter für die speziellen Namen sowie die vertrauten Namen der Naturals haben müssen. Irgendwann werden Sie den genauen Wert approximieren wollen, um ihn auf etwas in der realen Welt anzuwenden. Wie sich herausstellt, ist es viel effizienter, das gesamte Problem von Anfang an als Annäherung zu betrachten, es sei denn, Sie haben sehr spezielle Anforderungen.
quelle