Unum-Arithmetik Laslo Hunhold Oberseminar AG Kunoth im SS 2016, Universität zu Köln 2016-07-27 Ziel dieses Vortrags: Einführung in die Unum-Arithmetik • Probleme mit IEEE 754 Fließkommazahlen • Theoretische Herleitung der Unums • Unum-C-Toolbox • Ausblick zu Anwendungsmöglichkeiten Verwendete Literatur: [Gus16] John L. Gustafson, A Radical Approach to Computation with Real Numbers http://www.johngustafson.net/presentations/Unums2.0.pdf, Februar 2016. Abgerufen: 2016-07-26. [Kah06] William Kahan. How futile are mindless assessments of roundoff in floating-point computation? https://people.eecs.berkeley.edu/˜wkahan/Mindless.pdf, Januar 2006. Abgerufen: 2016-07-26. [MBdD+10] Jean-Michel Muller, Nicolas Brisebarre, Florent de Dinechin, Claude-Pierre Jeannerod, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol, Damien Stehlé, und Serge Torres. Handbook of Floating-Point Arithmetic. Birkhäuser Boston, Boston, MA, USA, 1. Ausgabe, Dezember 2010. ISBN 9780817647049. Laslo Hunhold — Unum-Arithmetik 1 Probleme mit IEEE 754 Fließkommazahlen s e f Figure: IEEE 754 Fließkommazahl (s = 1, (e, f ) ∈ {(5, 10), (8, 23), (11, 52)}) • Verschwendung von Bitmustern mit NaN, Infinity, ±0 (2f + 1) ≈ 0.02%, ≈ 0.04%, ≈ 1.6% für double, single, half precision • Vorzeichenbehaftete Null x = y 6⇒ x1 = y1 , da 0 = −0, aber 1 0 6= 1 −0 • Schwierige Implementierung wegen vieler Spezialfälle • Rundungsfehler Laslo Hunhold — Unum-Arithmetik 2 Probleme mit IEEE 754 Fließkommazahlen 1. Beispiel: Teufelsfolge [MBdB+10] Betrachte {un }n∈N definiert als 0 2 un := −4 111 − 1130 un−1 + 3000 un−1 ·un−2 n=0 n=1 n≥2 Charakteristisches Polynom: Nullstellen bei 5, 6 and 100. Mit den Startwerten (2, −4) lim un = 6 n→∞ Wie verhält sich der IEEE 754 Löser? Laslo Hunhold — Unum-Arithmetik 3 Probleme mit IEEE 754 Fließkommazahlen 2 25 100 100 80 un 60 40 20 6 0 0 5 10 15 20 25 n Figure: IEEE 754 (double) Verhalten der Teufelsfolge. Laslo Hunhold — Unum-Arithmetik 4 Probleme mit IEEE 754 Fließkommazahlen 2. Beispiel: Stumme Polstelle [Kah06] Betrachte f : R → R definiert als f (x) := ln(|3 · (1 − x) + 1|) 2 + x + 1. 80 Es gilt lim {f (x)} = lim {f (x)} = −∞. x↓ 4 3 x↑ 4 3 Wie verhält sich der IEEE 754 Löser? Laslo Hunhold — Unum-Arithmetik 5 Probleme mit IEEE 754 Fließkommazahlen −2.22 · 10−15 2.22 · 10−15 2.37 f (x) 2.36 2.35 2.34 2.33 2.327 −2 −1 0 x− Figure: IEEE 754 (double) Verhalten von f um 4 − 2.22 · 10−15 , 43 + 2.22 · 10−15 . 3 Laslo Hunhold — Unum-Arithmetik 1 2 ·10−15 4 3 4 3 für alle doubles in 6 Probleme mit IEEE 754 Fließkommazahlen Zwischenfazit Völlig falsche Ergebnisse durch Rundungsfehler, selbst mit dem double-precision-Quasistandard. • Verschwendung von Arbeitsspeicher und Pipeline-Bandbreite. • Falsches Gefühl der Sicherheit. • Fehlentscheidungen (Mensch und Maschine, Finanzen, Militär, . . . ). Intervallarithmetik? • Abhängigkeitsproblem erfordert große Vorsicht. • Liefert oft zu pessimistische Lösungsschranken. • Baut meistens auf IEEE 754 Fließkommazahlen auf. Ziele von Unums 2.0 [Gus16] • Brauchbare Lösungen bei geringer Präzision. • Garantierte Lösungsschranken. • Schnelle und einfache Maschinenarithmetik. Laslo Hunhold — Unum-Arithmetik 7 Theoretische Herleitung der Unums Projektiv erweiterte reelle Zahlen Definiere ∗ R := R ∪ {∞} ˘ mit den Axiomen für a, b ∈ R und b 6= 0 1. −(∞) ˘ := ∞ ˘ 2. a + ∞ ˘ =∞ ˘ + a := ∞ ˘ 3. b · ∞ ˘ =∞ ˘ · b := ∞ ˘ 4. a/∞ ˘ := 0 5. b/0 := ∞ ˘ ∞ ˘ −x x −1 1 −x −1 x −1 0 Nicht definiert sind ∞ ˘ + ∞, ˘ ∞ ˘ ·∞ ˘ und 0 · ∞. ˘ Laslo Hunhold — Unum-Arithmetik 8 Theoretische Herleitung der Unums R∗ -Intervallarithmetik Offenes R∗ -Intervall Seien a, a ∈ R∗ mit a ≤ a. R x ∈ R x < a ∗ R ⊃ (a, a) := x ∈ Ra < x x ∈ Ra < x < a ˘ a=a=∞ a=∞ ˘ ∧a∈R a∈R ∧a=∞ ˘ a, a ∈ R Menge der offenen R∗ -Intervalle I ∗ I := {(a, a) a, a ∈ R } mit ⊕, ⊗ R∗ -Einermengen R∗ S ∗ RS := ∗ {x} : x ∈ R . R∗ -Flocken F ∗ F := I t RS mit , , Inversion / und Negation − P(F) enthält u.a. alle offenen, geschlossenen und halboffenen Intervalle. Laslo Hunhold — Unum-Arithmetik 9 Theoretische Herleitung der Unums Menge der Unums U Definition Wähle Gitter P = {p1 , . . . , pn | ∀i < j : pi < pj } ⊂ (1, ∞), ˘ und definiere F ⊃ U(P) := n G {pi } t /{pi } t −{pi } t −/{pi } t i=1 n G {(pi , pi+1 )} t {/(pi , pi+1 )} t {−(pi , pi+1 )} t {−/(pi , pi+1 )} t i=0 {1} t {−1} t {0} t {∞} ˘ ˘ pn −pn ∞ −p1 p1 −1 1 −p1−1 p1−1 −pn−1 0 pn−1 Laslo Hunhold — Unum-Arithmetik 10 Theoretische Herleitung der Unums SORNS (Sets of real numbers) Betrachte nun Teilmengen von P(U(P)) als Mittelpunkt der Unum 2.0-Arithmetik. Blur-Operator blur : F → P(U(P)) f : 7→ {u ∈ U : f ⊆ u}. Duale Operationen Sei ? : F × F → F eine Operation auf F und ∼ eine Relation. h?i : P(U(P)) × P(U(P)) → P(U(P)) U ∼ V ∧ u 6= v [ [ ∅ (U, V ) :7→ R∗ u?v =∅ u∈U v ∈V blur(u ? v ) sonst Paarweise Auswertung abhängiger SORNs, totale Auswertung unabhängiger SORNs. Addition, Multiplikation, Subtraktion und Division sind nun wohldefiniert auf SORNs. Laslo Hunhold — Unum-Arithmetik 11 Unum C-Toolbox unum u; struct sorn a, b; Arithmetik uadd(&a, usub(&a, umul(&a, udiv(&a, upot(&a, &b); &b); &b); &b); &b); uneg(&a); uinv(&a); Mengenoperationen uemp(&a); uset(&a, &b); ucut(&a, &b); uuni(&a, &b); uint(&a, 1.0, INFINITY); Ausgabe uout(&a); Umgebung (Datentypen, Tabellen, ...) wird automatisch generiert aus beliebigem Eingabegitter Laslo Hunhold — Unum-Arithmetik 12 Unum C-Toolbox Modellierung von SORNs in 8 Bits #include "unum.h" int main(void) { struct sorn a; uemp(&a); uint(&a, -300, -20); uint(&a, -2, 4); uint(&a, 5, 5); uint(&a, 92.5, 160); uout(&a); putchar(’\n’); $ ./model (∞,-20] ˘ [-2,4] [5,5] (90,∞) ˘ return 0; } Laslo Hunhold — Unum-Arithmetik 13 Unum C-Toolbox Abhängigkeitsproblem in 8 Bits #include "unum.h" int main(void) { struct sorn a; int i; uemp(&a); uint(&a, -4, 4); uout(&a); putchar(’\n’); for (i = 0; i < 6; i++) { usub(&a, &a); uout(&a); putchar(’\n’); } $ ./dep [-4,4] (-0.7,0.7) (-/10,/10) (-/90,/90) (-0.009,0.009) (-0.009,0.009) (-0.009,0.009) return 0; } Laslo Hunhold — Unum-Arithmetik 14 Ergebnisse und weiterer Ausblick • Einsparungen bei Arbeitsspeicher und Energie (brauchbare Ergebnisse mit weniger als 64 Bits) • Neuer Ansatz für parallele Löser (Iterative Verfahren von groben auf feine Gitter) • Solidität bei Problemen für Fließkommazahlen und traditionelle Intervallarithmetik • Anwendungsspezifische Zahlensysteme Vielen Dank für Ihre Aufmerksamkeit! Laslo Hunhold — Unum-Arithmetik 15
© Copyright 2025 ExpyDoc