Algorithmic Information Theory Project - Reduce complexity with prime numbers
This project aims at exploring the use of prime numbers in order to reduce the complexity of integers bit encoding.
3 approaches are tested:
- PrimeDecomposeCoding uses prime decomposition of an integer to encode it
- PrimeSkipCoding is an alternative to PrimeDecomposeCoding and also uses prime decomposition
- PrimeProxyCoding uses prime numbers as proxy to describe integers
The 3 techniques are combined to get an optimal one, which is then compared to other techniques such as basic compact coding or the use of round numbers for complexity reduction.
This project concludes that prime numbers allow complexity reduction in several cases. But, due to their highly not uniform distribution, it is not possible to generalize over the limits tested here.