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 Addition $s = a + b$ is done by adding digits from least to most significant.
  49 \begin{align*}
  50         s = \displaystyle\sum_{i=0}^{\infty} (a_i + b_i) \beta^{i}
  51 \end{align*}
  52
  53 Considering the contributions to the sum of the $i^\text{th}$ and $(i+1)^\text{th}$ digits:
  54 \begin{align}
  55         s_i\beta^i + s_{i+1}\beta^{i+1} &= (a_i+b_i)\beta^i + (a_i+b_i)\beta^{i+1} \\
  56         \implies s_i + s_{i+1}\beta &= (a_i+b_i) + (a_{i+1}+b_{i+1})\beta \\
  57 \end{align}
  58
  59 If the sum $a_i + b_i \geq \beta$, ie: It cannot be represented in base $\beta$, then we can rewrite this as:
  60 \begin{align}
  61         s_i + s_{i+1}\beta &= \beta + (a_i+b_i-\beta) + (a_{i+1}+b_{i+1})\beta \\
  62         &= (a_i+b_i-\beta) + (a_{i+1}+b_{i+1}+1)\beta
  63 \end{align}
  64
  65 So we can use the digits $s_i = (a_i+b_i-\beta) < \beta$ and $s_{i+1} = (a_{i+1}+b_{i+1}+1)$.
  66 This operation is the \emph{carry}\footnote{I'm pretty sure that is not a rigorous definition but close enough}.
  67
  68 The x64 instruction set includes an \emph{add with carry} instruction \verb/adc/ which will add fixed sized digits and set a flag to indicate a carry. This allows for easy adding of an array of digits representing an arbitrary sized integer.
  69
  70
  71
  72
  73 \section{Subtraction Algorithms}
  74
  75 Similarly, subtraction $s = a - b$ is done from least to most significant digit. If the result of $a_i - b_i < 0$ then we \emph{borrow} from a higher digit.
  76
  77 \begin{align*}
  78         s_i + s_{i+1}\beta &= \beta + (a_i-b_i+\beta) + (a_{i+1}-b_{i+1}-1)\beta
  79 \end{align*}
  80
  81 The x64 instruction set also includes a \emph{subtract with borrow} instruction \verb/sbb/ which will set a borrow flag.
  82
  83 \section{Multiplication Algorithms}
  84
  85 In general, the result of multiplying two $n$ digit numbers may require up to $2n$ digits.
  86
  87 \section{Division Algorithms}
  88
  89 \subsection{Naive Algorithm}
  90
  91 \subsection{Shifting Algorithm}
  92
  93 \section{Base conversion}
  94
  95 Since humans are not very good at understanding binary, it is convenient to convert integer representations from one base to another.
  96
  97
  98 \section{Performance Comparison of IPDF::Arbint and GMP Integers}
  99
 100 We repeated 1000 trials of the four basic operations on arbitrary integers initialised from \verb/rand(3)/
 101
 102 Here are the average IR costs per operation collected using the \emph{callgrind} tool with the memory analysis program \emph{valgrind}.
 103
 104 \begin{figure}[H]
 105         \centering\begin{tabular}{|c|c|c|c|}
 106         \hline
 107         {\bf Operation} & {\bf IR Cost Arbint} & {\bf IR Cost Gmpint} & {\bf Arbint/Gmpint}\\ \hline
 108         *= & 3957 & 255 & 15.6 \\ \hline
 109         /= & 395008 & 388 & 1018.1\\ \hline
 110         += & 252 & 98 & 2.5 \\ \hline
 111         -= & 458 & 102 & 4.5\\
 112         \hline
 113 \end{tabular}
 114         \caption{GMP wins}
 115 \end{figure}
 116
 117 Clearly we are not as good at implementing arbitrary integer arithmetic as the GMP project. We are particularly bad at division. This is probably because we used the second algorithm on wikipedia.
 118
 119 Examining the GMP source code shows that the library is mostly implemented using highly optimised assembly which is selected based on the build target. We've used C++ classes with all their overhead. We also used a shittier division algorithm although our addition and subtraction are pretty similar.
 120
 121 \section{Conclusion}
 122
 123 Just use GMP.
 124
 125 \end{document}