Datentypen jenseits von Gut und Böse
Wofür braucht man die denn?
Wenn wir uns unser Vorhaben mal genauer ansehen, wollen wir ja die Kreiszahl PI mit möglichst vielen Nachkommastellen berechnen.
Wieviele Nachkommastellen?
Das sollte eigentlich egal sein, oder anders gesagt, wir wollen uns nicht durch irgendwelche Begrenzungen eines Datentypen von unserem Vorhaben abbringen lassen.
Und was gibts da so?
Naja, in erster Linie geht es um nahezu unendlicher Datenmenge für den Datentyp und Effizienz.
Bei der Betrachtung von Effizienz in der Mathematik ist eigentlich klar, dass wir 3 Sachen unbedingt vermeiden sollten:
- Subtraktion
- Division
- Dezimalzahlberechnung
Während Addition und Multiplikation oft als grundlegende und effizient implementierte Operationen gelten, sind Subtraktion und insbesondere Division von Dezimalzahlen komplexer und ressourcenintensiver. Dies liegt an verschiedenen Faktoren, darunter die Notwendigkeit der Normalisierung, die Komplexität der zugrunde liegenden Algorithmen und hardwarebedingte Einschränkungen.
Aber zurück zum eigentlichen „Problem“. Schauen wir sie uns die Formel zur Berechnung von Pi nach Chudnovsky nochmal an:
Die Teile die wir für die verteilte Berechnung benögitgen befinden sich hinter dem SIGMA-Therm. Und an dieser Stelle berechnen wir auch nur die einzelnen Iterationen. Wie wir gelernt haben ist PI mit jeder Iteration 14 Nachkommastellen genauer.
Also berechnen wir, verteilt, die ganzen Iterationen und speichern das Ergebnis. Später, wenn alle Iterationen berechnet sind, berechnen wir das Gesamtergebnis (der Teil links neben dem SIGMA-Therm).
Und damit haben wir das Ergebnis und zwar der Nachkommastellen.
Das schöne ist nämlich, wenn ich von einer Dezimalzahl Vorkommastelle und Komma wegnehme, bleiben immer nur die Nachkommastellen als Ganzzahl übrig und das machen wir uns hier zu Nutze. Und da wir ja möglichst viele Nachkommastellen berechnen wollen tun wir das als Ganzzahl.
Und genau dafür, also einem ganzzahligen Datentyp mit unendlicher Datenmenge gibts was Eingebautes.
Warum?
Kleines Beispiel aus der Formel: Nehmen wir an wir sind bei der 100. Iteration (also theoretisch bei der Berechnung der 1.400 Nachkommastelle).
Und hier nur den Teil
(6k)!(13591409 + 545140134k)
also
(6 * 100)!(13591409 + 545140134 * 100)
TL;DR, hier das Ergebnis:
69008627116351066085122392871871004054204533374234896618228229108154803221007872787084612638423936787088468332798182197805281978385787397004499502940319012166005164540430259962361973033653474945967905723616860019663852106965324254096641703680896943138461517533075587987158675142466779862362313615502582354125644301665933393604257284983545438185803054782894327580261692782706752427844784820954078508443151284856602396456936799803310237134305118790173615656953730075817601150586802212167218480761343017341720637000123382580258636596567872358271066320044124809318327585169963056310201784312675371189466170929953480571188620305733190449639706569176915042781213021767383457058146692764510305062295748488271106699597333556468657521227577487565966326140781924672776552877551607794674328701127738696911472777445679222004870591881103617442424414237712964956648075238295405105438722759660567607621261209823880675931255996738679613215959375484073972809729974986753325168526605608432717128860394158801656132455902942915435645369393317458741278621259489007844457408652622727926133470081847660313065063994589564729366382122473807392127131461871463886096387914130851402029149735474671396590277452778402620227319793221364500603532875561363049360764953984812102214841982296897721166987264
Eine Ganzzahl mit 1272 Stellen. Und jetzt kommt der Auftritt von BigInteger!
Der BigInteger-Datentyp in C# gehört zum Namespace System.Numerics und ermöglicht die Darstellung ganzer Zahlen mit beliebig großer Präzision. Im Gegensatz zu den eingebauten ganzzahligen Datentypen wie int, long oder ulong, die eine feste Bitbreite haben und somit einen begrenzten Wertebereich bieten, ist BigInteger nicht durch die Hardwarearchitektur beschränkt. Dies ermöglicht die Verarbeitung sehr großer Zahlen, die über die Grenzen der standardmäßigen Datentypen hinausgehen. Die einzige Einschränkung die der Datentyp BigInteger kennt ist die Menge an zur Verfügung stehendem Hauptspeicher im verwendeten Computer.
Funktionsweise von BigInteger
Die Implementierung von BigInteger basiert auf der Speicherung der Zahl in einem internen Array von UInt32 oder UInt64 Werten, abhängig von der Plattform (32-Bit oder 64-Bit). Jede Position im Array repräsentiert ein Segment der gesamten Zahl, ähnlich wie Stellenwerte im Dezimalsystem. Die Zahl wird in einer internen Basis dargestellt, die üblicherweise 2³² oder 2⁶⁴ beträgt.
•Vorzeichenbehandlung: BigInteger speichert das Vorzeichen separat vom Betrag. Dadurch können sowohl positive als auch negative ganze Zahlen dargestellt werden.
•Arithmetische Operationen: Bei Berechnungen werden effiziente Algorithmen verwendet, um die Leistung zu optimieren:
•Addition und Subtraktion: Ähnlich wie bei manuellen Berechnungen werden die jeweiligen Segmente addiert oder subtrahiert, wobei Überträge oder Unterläufe zwischen den Segmenten behandelt werden.
•Multiplikation: Für kleinere Zahlen wird die klassische Multiplikation verwendet. Bei größeren Zahlen kommen Algorithmen wie Karatsuba oder das Toom-Cook-Verfahren zum Einsatz, die die Anzahl der benötigten Multiplikationsschritte reduzieren.
•Division: Implementiert mittels Langdivision oder algorithmischer Optimierungen wie dem Newton-Raphson-Verfahren zur schnellen Annäherung an das Ergebnis.
•Unveränderlichkeit: BigInteger ist ein unveränderlicher (immutable) Typ. Jede Operation, die den Wert ändert, erzeugt ein neues BigInteger-Objekt. Dies erleichtert die Arbeit in multithreaded Umgebungen und verhindert Seiteneffekte.
•Speicherverwaltung: Da BigInteger variablen Speicherbedarf hat, verwaltet er intern Speicherpuffer und nutzt Techniken wie Lazy Allocation, um Speicher effizient zu nutzen.
Nachfolgend mal zum Vergleich, die einzelnen eingebauten (Ganzzahl-) Datentypen mit BigInteger.
| Datentyp | Größe | Wertebereich | Beschreibung |
|---|---|---|---|
| sbyte | 8 bit | -128 bis 127 | Ganzzahl mit Vorzeichen |
| byte | 8 bit | 0 bis 255 | Ganzzahl ohne Vorzeichen |
| short | 16 bit | -32.768 bis 32.767 | Kleiner Ganzzahltyp mit Vorzeichen |
| ushort | 16 bit | 0 bis 65.535 | Kleiner Ganzzahltyp ohne Vorzeichen |
| int | 32 bit | -2.147.483.648 bis 2.147.483.647 | Standard-Ganzzahltyp mit Vorzeichen |
| uint | 32 bit | 0 bis 4.294.967.295 | Ganzzahl ohne Vorzeichen |
| long | 64 bit | -9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807 | Großer Ganzzahltyp mit Vorzeichen |
| ulong | 64 bit | 0 bis 18.446.744.073.709.551.615 | Großer Ganzzahltyp ohne Vorzeichen |
| BigInteger | Variabel | Beschränkt nur durch verfügbaren Speicher | Ganzzahlen mit beliebiger Größe und Präzision |