\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

5. Arithmetische Algorithmen

Ich würde sehr gerne noch über die Laufzeitkomplexität von Hashing mit Ihnen sprechen, allerdings haben Sie bestimmt gemerkt, dass sehr große Zahlen eine wichtige Zutat von universellem Hashing darstellen und die Laufzeitkomplexität wohl von den arithmetischen Operationen (Multiplikation, Division, Modulo) dominiert wird. Darum geht es in diesem Kapitel: obwohl wir beim Programmieren arithmetische Operationen oft als konstant schnell, also von Komplexität \(O(1)\) betrachten, gilt dies nicht mehr, wenn wir es mit sehr großen Zahlen zu tun haben.

int, long int und Big Integer

Wenn Sie in Java programmieren, werden Sie ganze Zahlen wahrscheinlich als int darstellen. Dies besteht aus 4 Bytes, also 32 bits. Damit können Sie gar nicht beliebig große Zahlen darstellen, sondern nur die in der Menge $$ \{ - 2^{31}, \dots, -1, 0, 1, 2, \dots, 2^{31}-1 \} $$ In C und C++ haben Sie auch den Datentyp unsigned int, der die Menge $$ \{0, 1, \dots, 2^{32}-1\} $$

repräsentiert. In der Terminologie, die wir im letzten Kapitel gelernt haben: mit int oder unsigned int rechnen Sie sowieso immer nur modulo \(2^{32}\). Der Datentyp long int verhält sich genau so, nur mit \(64\) statt \(32\) bits. Es gibt aber durchaus Anwendungen, die nach größeren Zahlen verlangen, zum Beispiel Hashing, Fingerprinting oder Kryptographie. Wie stellen Sie noch größere Zahlen dar? Nun ja, genau so, wie wir auf Papier die Zahl dreihundertneunundsiebzig als 379 darstellen, können wir im Computer beliebig große Zahlen als Array von int darstellen, also im Prinzip nicht in Basis 10 sondern in Basis \(2^{32}\). Die Java-Klasse BigInteger speichert die "Ziffern" der Zahl als int []. Arithmetische Operationen wie Addition, Multiplikation, Division etc. müssen dann aber als Code in dieser Klasse implementiert werden; im Gegensatz dazu stehen die arithmetischen Operationen für int und long int; diese werden bereits von einem elektronischen Schaltkreis im Prozessor unterstützt.

Für die Übungen in diesem Kapitel empfehle ich Ihnen, Python zu verwenden, da Python nativ bereits Big Integers unterstützt: 

python                                
2**100 + 2**88 + 1                                
1267960085238050746565427986433

Falls es Sie interessiert: Node.js scheint große Integers einfach als Float oder Double zu approximieren. Sie können bei Node also nicht darauf verlassen, dass es "richtig" rechnet: 

node                                    
2**88 + 1 - 2**88 - 1
-1

was natürlich falsch ist. Also: verwenden Sie am Besten python.