Penultimate draft

[ipdf/sam.git] / chapters / Background / Rationals.tex

diff --git a/chapters/Background/Rationals.tex b/chapters/Background/Rationals.tex
index da4f77a..5a55198 100644 (file)
--- a/chapters/Background/Rationals.tex
+++ b/chapters/Background/Rationals.tex
@@ -1,15 +1,13 @@
+A rational number $Q$ may be represented by two integers $N$ the numerator and $D$ the denominator.
+
+\begin{align}
+       Q &= \frac{N}{D} 
+\end{align}                    
+
+Compared to floating point arithmetic which is generally inexact, rational arithmetic including the division operation is always exactly representable as another rational number. However, a \emph{fixed size} rational representation is of rather limited use as $D$ will always grow after repeated operations and overflow. Use of arbitrary sized integers as described in section \ref{Big Integers} and implemented by GMP\cite{granlund2004GMP} overcomes this issue; however as we will see in Chapter \ref{Results and Discussion} there can be a significant performance cost associated with Rationals.
+  
        \begin{align}
-               Q &= \frac{N}{D} 
-       \end{align}                     
-       \begin{itemize}
-               \item $N$ and $D$ are arbitrary precision integers
-       \end{itemize}
-       \begin{align}
-               N &= \sum_{i=0}^{S} d_i \beta^{i}
+               N = \sum_{i=0}^{S} n_i \beta^{i} & \text{ and }
+               D = \sum_{i=0}^{S} d_i \beta^{i} \text{ where $S$ grows as needed}
        \end{align}     
-       \begin{itemize}
-               \item $d_i$ are fixed size integers, $\beta = 2^{64}$
-               \item Size $S$ grows as needed
-               \item Operations are always exact
-               \item Implemented by GNU Multiple Precision Library
-       \end{itemize}
+