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 grants permission to the University Librarian at Acadia University to reproduce, loan or distribute copies of my thesis in microform, paper or electronic formats on a non-profit basis. The author retains the copyright of the thesis.