Anschrift
Frauengasse 3-5
2500 Baden
02252 / 44403

Very Large Integer 10-11-2009

Rechnen mit sehr großen Zahlen - Very Large Integer

Programmiersprachen sind in der Darstellung von Zahlen auf gewisse Zahlenbereiche eingeschränkt. So ist der größte ganzzahlige Zahlenbereich in C# ulong im Bereich [0 bis 18.446.744.073.709.551.615] (Vorzeichenlose 64-Bit-Ganzzahl) und in Delphi Longword im Bereich [0..4294967295] (32 Bit, ohne Vorzeichen).

Doch was tun wenn man größere Zahlen benötigt?
So verwendet z.B. der RSA Algorithmus (Verschlüsselung von Daten) Primzahlen mit einer Länge von 100 oder mehr Stellen. Nun man programmiert sich einfach einen neuen Zahlentyp. Eine beliebige große Zahl wird einfach in einem Array abgelegt, das im Prinzip so groß werden kann, bis das RAM erschöpft ist. Ich verwende hier in C# den Zahlentyp int im Bereich [-2.147.483.648 bis 2.147.483.647] (32-Bit-Ganzzahl mit Vorzeichen), und in Delphi den Typ integer.
In nachfolgender Grafik sehen Sie wie eine größere Zahl gespeichert wird.

info.png


In jedem Arrayeintrag werden aber nur 9 Stellen gespeichert. Der Grund ist ein einfacher: Bei einer Addition könnte man auf die Zahl 3.000.000.000 oder größer stoßen, die aber nicht mehr im Zahlentyp int abspeicherbar wäre. Eine Exception des Programms wäre die Folge. Daher werden nur die besagten 9 Stellen abgelegt und alles darüber im nächsten Eintrag abgelegt.
Hat man das Abspeichern der Zahlen erledigt, muss man die 4 Grundrechnungsarten programmieren (Addition, Subtraktion, Multiplikation und Division). Und ab dann kann man schon rechnen. Für aufwendigere Rechnungen wird man wohl zwangsläufig noch diverse Rechenoperation definieren müssen, aber das hängt von der Anwendung ab.

Hier einige erste Ergebnisse:

mime TestVLI.zip 75 KB mit den entsprechenden Klassenbibliotheken