An investigation into the structure of Chinese remainder representation

Laing, David (2009) An investigation into the structure of Chinese remainder representation. PhD thesis, James Cook University.

[img] PDF (Thesis) - Submitted Version
Download (1MB)
[img]
Preview
PDF (Thesis: Appendix B1) - Submitted Version
Download (202kB)
[img] PDF (Thesis: Appendix B2) - Submitted Version
Download (163kB)
 
749


Abstract

This dissertation began as an investigation into the pseudorank function for Chinese remainder representation (CRR) integers and its relation to the rank function. Through an innovative reformulation of the problem we discovered an alternative pseudorank function which made the study of pseudorank errors significantly easier. Prior to this work almost nothing was known about these errors. The alternative pseudorank lead us to the discovery of a set of integers which are related to many of the interesting CRR properties.

One of the drivers of CRR research is the fact that it can be used as the basis for highly performant arithmetic in hardware implementations. For a long time a number of CRR related problems have been recognized as being hard to implement efficiently. The lack of an efficient implementation for some of these problems has meant that CRR has only been able to be used to implement hardware solutions for very specific problems.

The second part of the thesis defines a model of computation that can be used to clearly divide the difficult CRR problems from the easy CRR problems. This work resulted in the establishment of a link between difficult CRR problems and NP-complete problems.

Item ID: 11590
Item Type: Thesis (PhD)
Keywords: Chinese remainder representation integers, pseudorank errors, finite automata, computational mathematics, computational algorithms
Date Deposited: 20 Jun 2010 22:31
FoR Codes: 01 MATHEMATICAL SCIENCES > 0103 Numerical and Computational Mathematics > 010302 Numerical Solution of Differential and Integral Equations @ 100%
SEO Codes: 97 EXPANDING KNOWLEDGE > 970101 Expanding Knowledge in the Mathematical Sciences @ 50%
89 INFORMATION AND COMMUNICATION SERVICES > 8902 Computer Software and Services > 890299 Computer Software and Services not elsewhere classified @ 50%
Downloads: Total: 749
Last 12 Months: 11
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page