Investigating the usefulness of multidimensional radix representations for computing
LE3 .A278 2016
Master of Science
Mathematics and Statistics
Mathematics & Statistics
This thesis is an extension of typical numeration systems to the multidimensional setting. We also investigate the complexity of a generalized addition algorithm for computation with multidimensional digit representations. Positional digit representations in one dimension, such as base 10 or base 2, were a major historical advance for arithmetic. The standard representation of vectors involves multiple components, rather than being purely a digit representation, so our research asks one main question: are multidimensional digit representations computationally useful? This thesis investigates the algorithmic complexity of binary additions because they are the simplest way to analyze the idea of algorithmic complexity and to demonstrate algorithms that do or do not terminate, and have linear or quadratic complexity. This thesis also investigates the algorithmic complexity of addition involving radix representations in higher dimensions; specifcally, we consider the matrix A=[2 -1 1 2] as our radix in Z2. We prove our algorithm terminates, and that the time complexity is quadratic. This investigation has successfully answered the main question for just one example and it is a first step to generalize the answer for Zn.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.