Zahldarstellung im Computer

Zahldarstellung im Computer#

Speichereinheiten#

  • 1 Bit= 1 b = kleinste Einheit, speichert \(0\) oder \(1\)

  • 1 Byte= 1 B = Zusammenfassung von 8 Bit

  • 1 Kilobyte= 1 KB = 1024 Byte

    • \(1024 = 2^{10}\) nächste 2er Potenz an \(1000\)

  • 1 Megabyte= 1 MB = 1024 KB

  • 1 Gigabyte= 1 GB = 1024 MB

  • 1 Terabyte= 1 TB = 1024 GB

Speicherung von Zahlen#

  • Zur Speicherung von Zahlen wird je nach Datentyp fixe Anzahl an Bytes verwendet

  • Konsequenz:

    • pro Datentyp gibt es nur endlich viele Zahlen

    • es gibt jeweils größte und kleinste Zahl!

Ganzzahlen#

  • Mit \(n\) Bits kann man \( 2^n\) Ganzzahlen darstellen

  • Standardmäßig betrachtet man

    • entweder alle ganzen Zahlen in \([0,2^n-1]\)

    • oder alle ganzen Zahlen in \([-2^{n-1},2^{n-1}-1]\)

Integer-Arithmetik in Python#

Integer Arithmetik in Python unterscheidet sich von vielen andern Programmiersprachen, da es __keine zu großen Integer-Zahlen__gibt.

  • Python kann mit beliebig großen Zahlen exakt rechnen

    • Ausnahme: Speicherplatz im Computer reicht nicht um die Zahl zu speichern

    • Extrem unwahrscheinlich: 1 MB Speicher reicht für Zahlen mit ca. \(8\cdot 10^6\) binären Ziffern, also ca. \(2.4\cdot 10^6\) Dezimalziffern.

      • Begründung: 1 MB sind ca. 10^6 Bytes = \(8\cdot 10^6\) Bits

      • Ein Bit speichert eine binäre Ziffer

      • Um eine Dezimalziffer zu speichern, benötigt man ca. 3.32 Bits (\(\log_2(10) \approx 3.32\))

  • Viele andere Programmiersprachen (C, C++, Java, …) haben feste Grenzen für Integer-Zahlen

    • z.B. 32-Bit Integer: Zahlenbereich \([-2^{31},2^{31}-1] = [-2147483648, 2147483647]\)

    • z.B. 64-Bit Integer: Zahlenbereich \([-2^{63},2^{63}-1] = [-9223372036854775808, 9223372036854775807]\)

    • Werden diese Grenzen überschritten, kommt es zu einem Überlauf(engl. overflow)

      • z.B. in C/C++/Java: \(2147483647 + 1 = -2147483648\)

      • In Python gibt es keinen Überlauf, aber

        • Rechenoperationen mit sehr großen Zahlen sind deutlich langsamer als mit kleinen Zahlen

Achtung: Integer-Arithmetik in NumPy#

Aus Performance-Gründen verwendet die NumPy Bibliothek für numerische Rechnungen in Python standardmäßig 64-Bit Integer.

  • Exakte Arithmetik ist nur innerhalb des Bereichs \([-2^{63},2^{63}-1]\) gewährleistet.

  • Bei Überschreitung dieses Bereichs kommt es zu einem Überlauf, ähnlich wie in anderen Programmiersprachen.

  • Modulo-Arithmetik: größte Zahl + 1 = kleinste Zahl

  • Python gibt meistens eine Warnung aus, wenn ein Überlauf auftritt.

Es gibt auch die Möglichkeit, in NumPy mit größeren Integer-Typen zu rechnen, z.B. np.int128, wenn die Plattform dies unterstützt. Allerdings sind diese Typen nicht so weit verbreitet und können in manchen Umgebungen nicht verfügbar sein.

Kleinere Integer-Typen wie np.int8, np.int16, und np.int32 sind ebenfalls verfügbar, aber sie haben noch kleinere Wertebereiche und sind daher anfälliger für Überläufe. - Rechnungen in kleineren Integer-Typen sind schneller als in größeren Integer-Typen.

import numpy as np

x = np.array([1, 2, 3], dtype=np.int64)
x[0] = 2**63-1
x[0] += 1
print(x[0])

-9223372036854775808

/var/folders/xh/ww_6450d6kv5hwq5w_j_kwjh0000gn/T/ipykernel_93262/104898551.py:5: RuntimeWarning: overflow encountered in scalar add
  x[0] += 1

Beispiel: unsigned 4-bit Integer#

Um zu erklären, wie es zum Überlauf kommt, betrachten wir die Darstellung von Zahlen im Binärsystem mit 4 Bits (4 Speicherplätzen für 0/1).

  • 4 Speicherplätze für 0/1 \(\implies\) 16 verschiedene Zahlen (\(0,\ldots, 15\))

  • Formel: \(a_3 a_2 a_1 a_0= \sum_{i=0}^3 a_i2^i\) mit \(a_i\in\{0,1\}\)

  • 0 0 0 0\(= 0\)

  • 0 0 0 1\(= 1\)

  • 0 0 1 0\(= 2\)

  • 0 0 1 1\(= 3\)

  • \(\ldots\)

  • 1 0 0 0\(= 8\)

  • \(\ldots\)

  • 1 1 1 1\(= 15\)

  • Addition wie im 10er System (mit Übertrag falls Ergebnis \(>1\))

    • 0 0 0 1+ 0 1 0 1= 0 1 1 0 (\(1+5=6\))

Beispiel: 4-bit Integer#

  • 4 Speicherplätze für 0/1 \(\implies\) 16 verschiedene Zahlen (\(-8,\ldots,0,\ldots, 7\))

  • 0 0 0 0\(= 0\)

  • \(\ldots\)

  • 0 1 1 1\(= 7\)

  • Beobachtung: 0 1 1 1+ 1 0 0 1= 0 0 0 0(\(+1\) Übertrag bleibt übrig)

  • daher: 1 0 0 1\(= -7\)

  • 1 0 0 0\(= -8\)

  • \(\ldots\)

  • 1 1 1 1\(= -1\)

  • Daher: 0 1 1 1+0 0 0 1= 1 0 0 0 (Überlauf \(7+1=-8\))

np.int32 hat nicht viel PLatz#

Kleinere Datentypen sind zwar schneller, haben aber deutlich weniger Platz für Zahlen.

  • Größter Wert für np.int32: \(2^{31}-1 = 2147483647 \approx 2.1\) Milliarden

  • Achtung:\(13! = 13\cdot 12! > 13\cdot 479\cdot10^6 > 6\) Millarden

import numpy as np
x = np.array([1], dtype=np.int32)
for i in range(17):
    x[0] *= (i+1)
    print(f"{i+1:2d}! = {x[0]}")

 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280
15! = 2004310016
16! = 2004189184
17! = -288522240

Achtung: Überlauf-Fehler wird zwar angezeigt, aber erst bei \(17!\). Das Ergebnis ist ab \(13!\) schon falsch.

Codierung von Zeichen#

Strings sind Folgen von Zeichen.

  • Jedes Zeichen wird durch eine Zahl codiert.

  • Festgelegt im Unicode-Standard (UTF-8)

  • Den Zahlencode eines Zeichen kann man mit der Funktion ord herausfinden.

  • Umgekehrt kann man mit der Funktion chr aus einem Zahlencode das entsprechende Zeichen zurückgewinnen.

    • Oft wird der Unicode in hexadezimaler Schreibweise angegeben: 0x...

for c in "abcdefghijklmnopqrstuvwxyz":
    print(f"The Unicode of '{c}' is {ord(c)}")

print("Cats are great " + chr(0x1F63B)*10)

The Unicode of 'a' is 97
The Unicode of 'b' is 98
The Unicode of 'c' is 99
The Unicode of 'd' is 100
The Unicode of 'e' is 101
The Unicode of 'f' is 102
The Unicode of 'g' is 103
The Unicode of 'h' is 104
The Unicode of 'i' is 105
The Unicode of 'j' is 106
The Unicode of 'k' is 107
The Unicode of 'l' is 108
The Unicode of 'm' is 109
The Unicode of 'n' is 110
The Unicode of 'o' is 111
The Unicode of 'p' is 112
The Unicode of 'q' is 113
The Unicode of 'r' is 114
The Unicode of 's' is 115
The Unicode of 't' is 116
The Unicode of 'u' is 117
The Unicode of 'v' is 118
The Unicode of 'w' is 119
The Unicode of 'x' is 120
The Unicode of 'y' is 121
The Unicode of 'z' is 122
Cats are great 😻😻😻😻😻😻😻😻😻😻

Gleitkommazahlen#

Reelle Zahlen werden im Computer in der Regel als Gleitkommazahlen (engl. floating point numbers) gespeichert. Der Name kommt daher, dass die Position des Dezimalpunkts (bzw. Binärpunkts) “gleiten” kann, abhängig von der Größe der Zahl.

Gleitkommadarstellung#

Folgender mathematischer Satz formalisiert die Idee der Gleitkommadarstellung:

  • SATZ: Zu \( x\in\mathbb{R}\) existieren

    • Vorzeichen \(\sigma\in\{\pm1\}\)

    • Ziffern \( a_k\in\{0,1\}\)

    • Exponent \( e\in\mathbb{Z}\) sodass gilt \(\displaystyle x = \sigma\Bigg(\sum_{k=1}^\infty a_k2^{-k}\Bigg)2^e\)

  • Darstellung ist nicht eindeutig, da z.B. \(1 = \displaystyle\sum_{k=1}^\infty2^{-k}\)

    • geometrische Reihe: \(\displaystyle \sum_{k=0}^\infty 2^{-k} = \frac{1}{1-1/2} = 2\)

    • z.B. \(\displaystyle \Bigg( \sum_{k=1}^\infty 2^{-k} \Bigg) 2^0 = \sum_{k=1}^\infty 2^{-k} = 1 = \Bigg( \sum_{k=2}^\infty 2^{-k} \Bigg) 2^1\)

Bemerkungen zum Dezimalsystem#

  • Satz gilt für jede Basis \( b\in\mathbb{N}_{\ge2}\)

    • Ziffern dann \( a_j\in\{0,1,\dots,b-1\}\)

  • Dezimalsystem \(b=10\) ist übliches System

    • \(47.11 = (4\cdot10^{-1}+7\cdot10^{-2}+1\cdot10^{-3}+1\cdot10^{-4})\cdot10^2\) * \(a_1=4\), \(a_2=7\), \(a_3=1\), \(a_4=1\), \(e=2\)

  • Nichteindeutigkeit im Dezimalsystem: \(0.\overline{9} = 1\)

Bemerkungen zum Binärsystem#

  • Mit \(b=2\) sind gekürzte Brüche genau dann als endliche Summe darstellbar (nicht als unendliche Reihe), wenn der Nenner Zweierpotenz ist:

    • \(\displaystyle\sum_{k=1}^{ M}a_k 2^{-k}\) hat Nenner mit Zweierpotenz

    • Folgt aus Eindeutigkeit der Primfaktorzerlegung

    • formaler Beweis = freiwillige Übung

  • z.B. keine exakte Darstellung für \(1/10\) für \(b=2\)

Definition von Gleitkommazahlensystemen#

  • Gleitkommazahlsystem \(\mathbb{F}(2,M,e_{\rm min},e_{\rm max})\subset\mathbb{Q}\)

    • endliche Teilmenge!

    • Mantissenlänge \( M\in\mathbb{N}\)

    • Exponentialschranken \( e_{\rm min}<0<e_{\rm max}\)

  • \( x\in\mathbb{F}\) hat Darstellung \(\displaystyle x = \sigma\Bigg(\sum_{k=1}^M a_k2^{-k}\Bigg)2^e\) mit

    • Vorzeichen \(\sigma\in\{\pm1\}\)

    • Ziffern \( a_j\in\{0,1\}\) mit \( a_1=1\) oder \( e = e_{\rm min}\) * normalisierte Gleitkommazahl (\( a_1=1\)) * denormalisierte Gleitkommazahl (\( e = e_{\rm min}\))

    • Exponent \( e\in\mathbb{Z}\) mit \( e_{\rm min}\le e\le e_{\rm max}\)

  • Darstellung von \( x\in\mathbb{F}\) ist eindeutig (Übung!)

  • Ziffer \(a_1\) muss nicht gespeichert werden

    • implizites erstes Bit

Arithmetik für Gleitkommazahlen#

  • Ergebnis Inf, __-Inf__bei Überlauf (oder 1./0.)

    • \(+\infty\) (Inf), \(-\infty\) (-Inf)

  • Ergebnis NaN, falls nicht definiert (z.B. 0./0.)

    • not a number (NaN)

  • Arithmetik ist approximativ, nicht exakt

Schlechte Kondition#

  • Eine Aufgabe ist __numerisch schlecht gestellt__bzw. schlecht konditioniert, falls kleine Änderungen der Daten auf große Änderungen im Ergebnis führen

    • z.B. hat Dreieck mit gegebenen Seitenlängen einen rechten Winkel?

    • z.B. liegt gegebener Punkt auf Kreisrand?

  • Implementierung sinnlos, weil Ergebnis zufällig!

  • bessere Fragestellungen:

    • Hat ein Dreieck mit gegebenen Seitenlängen einen Winkel \(\approx 90^\circ\)?

    • Liegt ein Punkt in einem \(\varepsilon\)-Schlauch um den Kreisrand?

Rechenfehler#

  • Aufgrund von Rechenfehlern darf man Gleitkommazahlen nie auf Gleichheit überprüfen - Statt \(x=y\) prüfen, ob Fehler \(|x-y|\) klein ist - z.B. \(|x-y|\le\varepsilon\cdot\max\{|x|,|y|\}\) mit \(\varepsilon=10^{-13}\)

  • In NumPy gibt es die Funktion np.isclose(x, y, atol=..., rtol=...), die prüft, ob zwei Gleitkommazahlen x und y “nahe beieinander” liegen. Dabei sind atol und rtol absolute bzw. relative Toleranzen.

    • Die Funktion überprüft, ob die Bedingung abs(x - y) <= atol + rtol * abs(y) erfüllt ist.

print("0.1 + 0.2 = 0.3?", 0.1 + 0.2 == 0.3)
print(f"0.1 is actually {0.1:.30f}")


print("(116/100)*100 = 116", (116./100)*100 == 116)
print(f"(116/100)*100 is actually {(116./100)*100:.30f}")

print("0.1 + 0.2 = 0.3 up to round-off error?", np.isclose(0.1 + 0.2, 0.3))
print("(116/100)*100 = 116 up to round-off error?", np.isclose((116./100)*100, 116))

0.1 + 0.2 = 0.3? False
0.1 is actually 0.100000000000000005551115123126
(116/100)*100 = 116 False
(116/100)*100 is actually 115.999999999999985789145284797996
0.1 + 0.2 = 0.3 up to round-off error? True
(116/100)*100 = 116 up to round-off error? True

Variablentypen np.float32, np.float64#

  • np.float32 ist idR. einfache Genauigkeit nach IEEE-754-Standard

    • \(\mathbb{F}(2,24,-126,127)\) \(\to\) 4 Byte = 32 Bit * 32b = 8b Exp. + 23b Mantisse + 1b Vorz.

    • sog. single precision

    • ca. 7 signifikante Dezimalstellen

  • np.float64 ist idR. doppelte Genauigkeit nach IEEE-754-Standard

    • \(\mathbb{F}(2,53,-1022,1023)\) \(\to\) 8 Byte = 64 Bit * 64b = 11b Exp. + 52b Mantisse + 1b Vorz.

    • sog. double precision

    • ca. 16 signifikante Dezimalstellen

x32 = np.array(0.1, dtype=np.float32)
x64 = np.array(0.1, dtype=np.float64)
print(f"float32: 0.1 is actually {x32:.30f}")
print(f"float64: 0.1 is actually {x64:.30f}")

float32: 0.1 is actually 0.100000001490116119384765625000
float64: 0.1 is actually 0.100000000000000005551115123126
Contents