Notes on integers
authorSam Moore <matches@ucc.asn.au>
Mon, 7 Jul 2014 12:25:48 +0000 (20:25 +0800)
committerSam Moore <matches@ucc.asn.au>
Mon, 7 Jul 2014 12:25:48 +0000 (20:25 +0800)
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.

ArbitraryIntegers.pdf [new file with mode: 0644]
ArbitraryIntegers.tex [new file with mode: 0644]
LiteratureNotes.pdf
LiteratureNotes.tex
template.tex

diff --git a/ArbitraryIntegers.pdf b/ArbitraryIntegers.pdf
new file mode 100644 (file)
index 0000000..8b97582
Binary files /dev/null and b/ArbitraryIntegers.pdf differ
diff --git a/ArbitraryIntegers.tex b/ArbitraryIntegers.tex
new file mode 100644 (file)
index 0000000..414abe4
--- /dev/null
@@ -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}
index 53d3953..380f44b 100644 (file)
Binary files a/LiteratureNotes.pdf and b/LiteratureNotes.pdf differ
index 3f21e37..94670a0 100644 (file)
@@ -1,3 +1,4 @@
+\documentclass[8pt]{extreport}
 \input{template}
 \begin{document}
 
index 1c06233..dd28ba0 100644 (file)
@@ -1,4 +1,4 @@
-\documentclass[8pt]{extreport}
+
 \usepackage{makeidx}
 \usepackage{graphicx}
 \usepackage{caption}

UCC git Repository :: git.ucc.asn.au