search

DK96-OS / MathTools

Mathematical Software Components. This library is actively maintained, and aims to stay updated. New feature proposals are welcome, but may not be included.
Apache License 2.0
2 stars 1 forks source link

Compact PrimeCache #41

Open DK96-OS opened 2 years ago

DK96-OS commented 2 years ago

Upgrade the BytePrimeCache using properties of small prime numbers to reduce the space requirement, and extend the coverage (ie. increase maxIndex).

A succinct or compact data structure uses space on the order of the minimum number of bits required to represent each element.

A basic fact to get started with:

This could increase the maxIndex (up to double the highest prime) by adding a bit shift operation when the index is between the current maxIndex, and the new maxIndex.

DK96-OS commented 2 years ago

The recent changes in Primes included the addition of a private array insertion method, complementing the existing private readFromArray method. These two methods encapsulate the internal array data storage, and any transformations that are to be applied when reading and writing the array.

DK96-OS commented 1 year ago

The array data encapsulation is highly effective, supporting quick and easy upgrade in #124

DK96-OS commented 1 year ago

There are many creative solutions, each introducing some amount of complexity. It is important to determine what the ideal balance of memory and cpu usage is during operations, and throughout the life of the cache.

For example, does dividing the size of the data array in half outweigh a doubling of branches, or a significant increase in the number of arithmetic operations?

A reliable series of measurements of cpu time performance comparing the solutions will be used in the decision. These will be contrasted with the theoretical memory saved, including the ability of the solution to scale to larger prime numbers.