X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=blobdiff_plain;f=chapters%2FBackground%2FFixedPoint.tex;h=6d7a15ff800ca3d7ff352f3b64010cd03965d5a0;hp=4ef2f6ca7e75b7f613cc31859b59102723a5c3eb;hb=refs%2Fheads%2Fmaster;hpb=ae8d5f837db032eb4d9e9666f5026fab7e3e8e4a

diff --git a/chapters/Background/FixedPoint.tex b/chapters/Background/FixedPoint.tex
index 4ef2f6c..6d7a15f 100644
--- a/chapters/Background/FixedPoint.tex
+++ b/chapters/Background/FixedPoint.tex
@@ -1,18 +1,38 @@
 A positive real number $z$ may be written as the sum of smaller integers ``digits'' $d_i$ multiplied by powers of a base $\beta$. 
 \begin{align}
-	z &= d_0 \beta^0 + d_1 \beta^1 + d_2 \beta^2 + \text{ ...} = \displaystyle\sum_{i=-\infty}^{\infty} d_i \beta^{i}\label{fixedpointZ}
+	z &= \text{... } + d_{-1} \beta^{-1} + d_0 \beta^0 + d_1 \beta^1 + \text{ ...} = \displaystyle\sum_{i=-\infty}^{\infty} d_i \beta^{i}\label{fixedpointZ}
 \end{align}
 Where each digit $d_i < \beta$. A set of $\beta$ unique symbols are used to represent values of $d_i$.
 A seperate sign '-' can be used to represent negative reals using equation \eqref{fixedpointZ}.
 
 To express a real number using equation \eqref{fixedpointZ} in practice we are limited to a finite number of terms between $i = -m$ and $i = n$. Fixed point representations are capable of representing a discrete set of numbers $0 \leq |z| \leq \beta^{n+1}-\beta^{-m}$ seperated by $\Delta z = \beta^{-m} \leq 1$. In the case $m = 0$, only integers can be represented.
 
+
 Example integer representation in base 10 (decimal) and base 2 (binary):
 \begin{align*}
 	5682_{10} &= 5\times10^3 + 6\times10^2 + 8\times10^1 + 2\times10^0 \\
 	1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
 \end{align*}
 
+\subsection{Big Integers} \label{Big Integers}
+Computer hardware implements operations for fixed size integers. The base is $\beta = 2$ and the digits
+are {0, 1}. The most significant bit can be reserved for the sign instead of a digit.
+We can construct larger size integers by considering some sequence of fixed size integers to be
+individual digits. In practice we will still be limited by the memory and processing time required
+1for ``big'' integers.
+
+For example, we can represent $5682_{10}$ as a single 16 bit digit or as the sum of two 8 bit digits. Each
+digit is being written in base 2 or 10 because there is not a universal base with $\ge 2^8$ unique symbols.
+\begin{align*}
+	5682_{10} &= 1011000110010_2 = 10110_2 \times 2^{8} + 110010_{2} \times 2^{0} % = 22_{10} \times 256^{1} + 50_{10} \times 256^{0}
+\end{align*}
+
+When performing an operation involving two $m$ digit integers, the result will in general require at most $2m$ digits. A straight forward big integer implementation merely needs to allocate memory for leading zeroes 
+
+Big Integers are implemented on the CPU as part of the standard for several languages including Python\cite{python_pep0237} and Java\cite{java_bigint}. Most implementations are based on the GNU Multiple Precision library (GMP) \cite{granlund2004GMP}. There have also been implementations of Big Integer arithmetic for GPUs\cite{zhao2010GPUMP}.
+
+ During this project a custom Big Integer type was implemented, but was found to be vastly inferior to the GMP implementation\cite{documentsArbitraryIntegers}
+
 %{\bf FIXME} Add Maths reference (Cantor's Diagonal argument) without going into all the Pure maths details