Gleitkommazahlen Binäre Gleitkommazahlen

Gleitkommazahlen
• in vielen technischen und wissenschaftlichen Anwendungen
erforderlich:
– hohe Präzision
– große Dynamik
möglich durch Verwendung von Gleitkommazahlen
• allgemeine Gleitkommazahl zur Basis r („radix“) definiert
durch x = a × re mit
− Argument oder Mantisse a
− Exponent oder Charakteristik e
• eine Gleitkommazahl x ≠ 0 zur Basis r heißt normalisiert, wenn
für die Mantisse a gilt: 1/r ≤ a < 1
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
2
Binäre Gleitkommazahlen
• Verwendung der Basis 2, d.h. eine binäre Gleitkommazahl x
ist definiert durch x = a × 2e
mit m-stelliger Mantisse a
und p-stelligem Exponent e
• eine binäre Gleitkommazahl x ≠ 0 heißt normalisiert, wenn das
höchstwertige Nachkommabit den Wert 1 hat
⇒ zwei Interpretationen: 0.XXXXXXX oder 1.XXXXXXX
• häufig Darstellung des Exponenten mit Bias b: x = a × 2e−b
Wahl von b = 2p–1 – 1 bewirkt Transformation des Bereiches für
den Exponenten e von 0 ... 2p – 1 in –(2p–1 –1) ... 2p–1
⇒ einfache Kodierung positiver und negativer Exponenten
• früher unterschiedliches Gleitkommaformat in jedem Prozessor,
heute überwiegend Verwendung des IEEE 754 Standard
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
3
1
IEEE 754 Standard
• allgemeine Definition: x = (–1)s × 1.f × 2e–b
• Mantisse aus Vorzeichen s und normalisiertem Betrag a = 1.f
im Bereich 1.00..00 bis 1.11..11
(1 vor dem Komma wird nicht kodiert ⇒ erhöhte Präzision)
• Aufbau einer n-Bit
IEEE Gleitkommazahl:
• p-stelliger Exponent mit Bias b = 2p–1–1, gültiger Exponent e
nur im Bereich emin= 0 < e < emax = 2p–1 = 2b+1
⇒ darstellbarer Zahlenbereich: ± 21–b ... (2–2–m) × 2b
• zwischen 2e–b und 2e−b+1 können stets 2m Gleitkommazahlen
kodiert werden ⇒ Abstand 2–m × 2e–b ist abhängig von e !
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
4
IEEE 754 Standard (Forts.)
• 3 verschiedene Formate spezifiziert:
single precision
double precision
quad precision
n
32
64
128
m
23
52
112
s
1
1
1
p
8
11
15
emin
0
0
0
emax
255
2047
32767
b
| xmin |
127
2–126
≈
10–38
1023
2–1022
≈
10–308
16383
2–16382
≈ 10–4932
| xmax | (2–2–23)×2127 ≈ 1038 (2–2–52)×21023 ≈ 10308 (2–2–112)×216383 ≈ 104932
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
5
2
IEEE 754 Standard (Forts.)
• e = emin = (00..00)2 = 0 und e = emax = (11..11)2 werden zur
Kodierung besonderer Zahlen verwendet:
x = +0 („positive Zero“): e = 0, f = 0, s = 0
x = −0 („negative Zero“): e = 0, f = 0, s = 1
x = +∞ („positive Infinity“): e = emax , f = 0, s = 0
x = −∞ („negative Infinity“): e = emax , f = 0, s = 1
x = NaN („Not a Number“): e = emax , f ≠ 0, s kann der
Klassifikation eines NaN dienen, z.B. „quiet“ oder „trapping“
x = (–1)s × 0.f × 21−b („Denormalized Number“): e = 0, f ≠ 0
• Denormalisierte Gleitkommazahlen ermöglichen die Darstellung
sehr kleiner Werte im Bereich 21−b−m ... 21−b
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
6
IEEE 754 Standard (Forts.)
Behandlung von Ausnahmesituationen:
• Überlauf tritt ein, wenn nach Normalisierung für x gilt: e ≥ emax
⇒ Generierung von +∞ (falls x > 0) bzw. −∞ (falls x < 0)
• einige Rechenregeln:
∞ + x = ∞ (falls x ≠ −∞), ∞ − x = ∞ (falls x ≠ ∞),
± x / 0 = ±∞ (falls x ≠ 0), ∞ ⋅ x = ±∞ (falls x ≠ 0)
• einige Operationen liefern ein unbestimmtes Ergebnis, z.B.:
∞ ⋅ 0 = NaN, 0 / 0 = NaN, ∞ − ∞ = NaN, f(NaN) = NaN
• Unterlauf tritt ein, wenn nach Normalisierung für x gilt: e = 0
⇒ entweder Generierung von x = 0 („flushing to zero“)
oder Generierung einer denormalisierten Darstellung von x
• Anmerkung: In vielen Laufzeitsystemen wird bei Darstellung einer Zahl
nicht zwischen NaN, +∞ und −∞ unterschieden und stets NaN generiert!
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
7
3
Fehleranalyse von Gleitkommazahlen
• Eine reelle Zahl x soll durch eine Gleitkommazahl x´ angenähert
werden
• i.a. existieren zwei Gleitkommazahlen x1´ und x2´ mit
x1´≤ x ≤ x2´, d.h. a × 2e ≤ x ≤ (a + 2−m) × 2e
• sei nun x´ die nähere von beiden Gleitkommazahlen x1´ und x2´,
so ergibt sich der maximale absolute Fehler:
εx = x´− x = ½ × (x2´ − x1´) × 2e = ½ × 2−m × 2e = 2−m × 2e−1
(εx hängt somit von Breite m der Mantisse und vom Exponenten ab !)
• für den maximalen relativen Fehler gilt jedoch:
δx = (x´− x) / x = εx / x = (½ × 2−m × 2e) / x
< (½ × 2−m × 2e) / (a × 2e) = ½ × 2−m / a < ½ × 2−m
(δx hängt somit nur von Breite m der Mantisse ab !)
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
8
Rundung von Gleitkommazahlen
IEEE Standard unterstützt vier Rundungsmodi, die vom Anwender
gewählt werden können
(Annahme: x = a × 2e−bias; aus m+r Stellen der Mantisse a werden m Stellen)
• „round to nearest even“ (Default): Runde zur nächsten darstellbaren
Gleitkommazahl x´. Sind Distanzen zur nächstgrößeren Zahl x+ und zur
nächstkleineren Zahl x− identisch, wähle die Zahl x´ mit Mantissenbit a0 = 0
⇒ mittlerer relativer Fehler: E[δx] = 0 !!
• „round towards plus infinity“: Runde stets zur nächstgrößeren
darstellbaren Gleitkommazahl x+ (gilt auch bei Überlauf !)
⇒ mittlerer relativer Fehler: E[δx] = ½ (2−m −2−m−r)
• „round towards minus infinity“: Runde stets zur nächstkleineren
darstellbaren Gleitkommazahl x− (gilt auch bei Überlauf !)
⇒ mittlerer relativer Fehler: E[δx] = – ½ (2−m −2−m−r)
• „round towards zero“: Abschneiden ohne Runden (also „Truncating“)
⇒ mittlerer relativer Fehler: E[δx] = 0 !?
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
9
4
Gleitkomma-Multiplikation
Algorithmus zur Multiplikation zweier IEEE-Gleitkommazahlen
x = (–1)s × a × 2α−bias und y = (–1)t × b × 2β–bias :
1) Multipliziere Mantissen als Festkommazahlen: c = a × b
a = 1.fa und b = 1.fb haben m + 1 Stellen ⇒ c hat 2m + 2 Stellen !
2) Addiere Exponenten: γ = α + β – bias
3) Berechne Vorzeichen des Produktes: u = s ⊕ t
γ-bias
4) Normalisiere Ergebnis z = (–1) × c × 2
a) Falls c ≥ 2, schiebe c um 1 nach rechts und inkrementiere γ
b) Setze c = 1.fc = 1.(c2m–1 c2m–2 ... cm)2 mit Rundung
5) Behandlung von Ausnahmesituationen:
a) Überlauf, falls γ ≥ emax = 2p – 1 ⇒ z := ±∞ (abhängig von u)
b) Unterlauf, falls γ ≤ emin = 0 ⇒ Denormalisierung durchführen !
c) Zero, falls c = 0 ⇒ z := ±0 (abhängig von u)
u
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
10
Gleitkomma-Multipliaktion (Forts.)
• Architektur eines Gleitkomma-Multiplizierers:
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
11
5
Gleitkomma-Addition/Subtraktion
Algorithmus zur Addition/Subtraktion zweier Gleitkommazahlen
x = (–1)s × a × 2α−bias und y = (–1)t × b × 2β−bias im IEEE Format:
1) Sortiere x und y derart, daß x die Zahl mit kleinerem Exponenten ist
2) Anpassung der Exponenten: Transformiere x in die Gleitkommazahl
x´ = (– 1)s × a´× 2β−bias durch Rechtsschieben von a um d = β − α Bits
3) Addiere/Subtrahiere Mantissen:
a) Falls nötig, bilde Zweierkomplement von a´ oder b
b) Führe Festkomma-Addition c = a´ ± b aus
c) Falls c < 0, setze u = 1 und bilde Zweierkomplement von c
4) Normalisiere Ergebnis z = (– 1) × c × 2β–bias
a) Falls c ≥ 2, schiebe c nach rechts (mit Rundung !) und inkrementiere β
b) Falls c < 1, schiebe c nach links und dekrementiere β
ggf. wiederhole b), bis 1 ≤ c < 2
5) Behandlung von Ausnahmesituationen: a = 0, b = 0 oder c = 0,
Überlauf, Unterlauf, d > m + 2
u
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
12
Gleitkomma-Addition (Forts.)
• Architektur eines Gleitkomma-Addierers:
Computer-Arithmetik, WS 2002/2003
A. Strey, Universität Ulm
Kapitel 3 : Gleitkomma-Arithmetik
13
6