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 2024 ExpyDoc
