ArbitraryIntegers.tex

   1 \documentclass[11pt]{article}
   2 \input{template}
   3
   4 \begin{document}
   5 \title{Arbitrary Sized Integers}
   6 \author{Sam Moore, David Gow}
   7 \maketitle
   8
   9 \section*{Abstract}
  10 We have implemented arbitrary sized integers which sometimes don't segfault, using a combination of the C++ standard library and stand alone x86-64 assembly. Performance tests reveal that we would have been better off just using the GNU Multiprecision Library (GMP).
  11
  12 \section{Integer Representation}
  13
  14 A positive integer (natural number) can be written as the sum of smaller integers ``digits'' multiplied by powers of a base.
  15 \begin{align}
  16         z &= \displaystyle\sum_{i=0}^{\infty} d_i \beta^{i}
  17 \end{align}
  18 Where each digit $d_i < \beta$ the base. A set of $\beta$ unique symbols are used to represent values of $d_i$.
  19 A fixed size representation truncates the sum at some $i=N$, which can represent all values $0 \leq z \leq \beta^{n+1}-1$.
  20
  21 A seperate sign symbol (eg: '-') can be used to represent negative integers using the same digit sum.
  22
  23 Example in base 10 (decimal):
  24 \begin{align}
  25         5682_{10} &= 5\times10^3 + 6\times10^2 + 8\times10^1 + 2\times10^0
  26 \end{align}
  27 In base 2 (binary) the same integer is:
  28 \begin{align}
  29         1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
  30 \end{align}
  31
  32 \subsection{Representation on computer hardware}
  33
  34 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.
  35
  36 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 for ``big'' integers.
  37
  38 For example, we can represent $5682_{10}$ as a single 16 bit digit or as the sum of two 8 bit digits.
  39 Each digit is being written in base 2 or 10 because there is not a universal base with $\geq2^8$ unique symbols.
  40
  41 \begin{align}
  42         5682_{10} &= 0001011000110010_2 = 10110_2\times2^8+ 110010_2\times 2^0 \\
  43          &= 22_{10}\times2^{8} + 50_{10}\times2^{0}
  44 \end{align}
  45
  46 \section{Addition Algorithms}
  47
  48
  49
  50 \section{Subtraction Algorithms}
  51
  52 \section{Multiplication Algorithms}
  53
  54 \section{Division Algorithms}
  55
  56 \subsection{Naive Algorithm}
  57
  58 \subsection{Shifting Algorithm}
  59
  60 \section{Base conversion}
  61
  62 Since humans are not very good at understanding binary, it is convenient to convert integer representations from one base to another.
  63
  64
  65 \section{IPDF Integer Representations}
  66
  67
  68
  69
  70 \end{document}