chapters/Background/FixedPoint.tex

   1 A positive real number $z$ may be written as the sum of smaller integers ``digits'' $d_i$ multiplied by powers of a base $\beta$.
   2 \begin{align}
   3         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}
   4 \end{align}
   5 Where each digit $d_i < \beta$. A set of $\beta$ unique symbols are used to represent values of $d_i$.
   6 A seperate sign '-' can be used to represent negative reals using equation \eqref{fixedpointZ}.
   7
   8 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.
   9
  10
  11 Example integer representation in base 10 (decimal) and base 2 (binary):
  12 \begin{align*}
  13         5682_{10} &= 5\times10^3 + 6\times10^2 + 8\times10^1 + 2\times10^0 \\
  14         1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
  15 \end{align*}
  16
  17 \subsection{Big Integers} \label{Big Integers}
  18 Computer hardware implements operations for fixed size integers. The base is $\beta = 2$ and the digits
  19 are {0, 1}. The most significant bit can be reserved for the sign instead of a digit.
  20 We can construct larger size integers by considering some sequence of fixed size integers to be
  21 individual digits. In practice we will still be limited by the memory and processing time required
  22 1for ``big'' integers.
  23
  24 For example, we can represent $5682_{10}$ as a single 16 bit digit or as the sum of two 8 bit digits. Each
  25 digit is being written in base 2 or 10 because there is not a universal base with $\ge 2^8$ unique symbols.
  26 \begin{align*}
  27         5682_{10} &= 1011000110010_2 = 10110_2 \times 2^{8} + 110010_{2} \times 2^{0} % = 22_{10} \times 256^{1} + 50_{10} \times 256^{0}
  28 \end{align*}
  29
  30 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
  31
  32 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}.
  33
  34  During this project a custom Big Integer type was implemented, but was found to be vastly inferior to the GMP implementation\cite{documentsArbitraryIntegers}
  35
  36 %{\bf FIXME} Add Maths reference (Cantor's Diagonal argument) without going into all the Pure maths details
  37
  38
  39
  40 %, but could be represented by the combination of a numerator $7 = 111_2$ and denominator $3 = 11_2$. Lastly, some values such as $e \approx 2.718\text{...}$ can only be expressed exactly using a symbolical system --- in this case as the result of an infinite summation $e = \displaystyle\sum_n^{\infty} 1/n!$
  41