From: Sam Moore <matches@ucc.asn.au>
Date: Mon, 7 Jul 2014 12:25:48 +0000 (+0800)
Subject: Notes on integers
X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=commitdiff_plain;h=c2b9e06d2e1501bac79a7908883a290f1660d4cd

Notes on integers

Not having done much pure maths feel like I'm saying everything wrong :S
Will fill in the "algorithm" bits at some point, since that's the bit we actually care about.
---

diff --git a/ArbitraryIntegers.pdf b/ArbitraryIntegers.pdf
new file mode 100644
index 0000000..8b97582
Binary files /dev/null and b/ArbitraryIntegers.pdf differ
diff --git a/ArbitraryIntegers.tex b/ArbitraryIntegers.tex
new file mode 100644
index 0000000..414abe4
--- /dev/null
+++ b/ArbitraryIntegers.tex
@@ -0,0 +1,70 @@
+\documentclass[11pt]{article}
+\input{template}
+
+\begin{document}
+\title{Arbitrary Sized Integers}
+\author{Sam Moore, David Gow}
+\maketitle
+
+\section*{Abstract}
+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).
+
+\section{Integer Representation}
+
+A positive integer (natural number) can be written as the sum of smaller integers ``digits'' multiplied by powers of a base.
+\begin{align}
+	z &= \displaystyle\sum_{i=0}^{\infty} d_i \beta^{i}
+\end{align}
+Where each digit $d_i < \beta$ the base. A set of $\beta$ unique symbols are used to represent values of $d_i$.
+A fixed size representation truncates the sum at some $i=N$, which can represent all values $0 \leq z \leq \beta^{n+1}-1$. 
+
+A seperate sign symbol (eg: '-') can be used to represent negative integers using the same digit sum.
+
+Example in base 10 (decimal):
+\begin{align}
+	5682_{10} &= 5\times10^3 + 6\times10^2 + 8\times10^1 + 2\times10^0
+\end{align}
+In base 2 (binary) the same integer is:
+\begin{align}
+	1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
+\end{align}
+
+\subsection{Representation on computer hardware}
+
+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 for ``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 $\geq2^8$ unique symbols.
+
+\begin{align}
+	5682_{10} &= 0001011000110010_2 = 10110_2\times2^8+ 110010_2\times 2^0 \\
+	 &= 22_{10}\times2^{8} + 50_{10}\times2^{0}
+\end{align}
+
+\section{Addition Algorithms}
+
+
+
+\section{Subtraction Algorithms}
+
+\section{Multiplication Algorithms}
+
+\section{Division Algorithms}
+
+\subsection{Naive Algorithm}
+
+\subsection{Shifting Algorithm}
+
+\section{Base conversion}
+
+Since humans are not very good at understanding binary, it is convenient to convert integer representations from one base to another. 
+
+
+\section{IPDF Integer Representations}
+
+
+
+
+\end{document}
diff --git a/LiteratureNotes.pdf b/LiteratureNotes.pdf
index 53d3953..380f44b 100644
Binary files a/LiteratureNotes.pdf and b/LiteratureNotes.pdf differ
diff --git a/LiteratureNotes.tex b/LiteratureNotes.tex
index 3f21e37..94670a0 100644
--- a/LiteratureNotes.tex
+++ b/LiteratureNotes.tex
@@ -1,3 +1,4 @@
+\documentclass[8pt]{extreport}
 \input{template}
 \begin{document}
 
diff --git a/template.tex b/template.tex
index 1c06233..dd28ba0 100644
--- a/template.tex
+++ b/template.tex
@@ -1,4 +1,4 @@
-\documentclass[8pt]{extreport}
+
 \usepackage{makeidx}
 \usepackage{graphicx}
 \usepackage{caption}