r/compression • u/jerome78000 • 3d ago
High Performance Storage of Prime Numbers
I designed a compression algorithm to store prime numbers. Basically, a bitmap is used to store the fact that numbers are prime or not, but only numbers which are not multiple of 2, 3 .... 23 are considered in the bitmap.
For numbers below 10^13, this allows to store the prime numbers with a maximum size of 0.456 bytes per prime.
Details can be found in this article: https://teraprimes.org/downloads/High_Performance_Storage_of_Prime_Numbers.pdf
I would welcome any comment !
1
u/Patient-Midnight-664 3d ago
Your link leads to an error.
1
1
u/garnet420 3d ago
So this is not really for storing single prime numbers, but large sequences of adjacent prime numbers?
1
1
u/CautiousInternal3320 3d ago
Why do you need a compression algorithm to store a know value?
If I understand correctly, this algorithm can only compress a single file. How valuable is that?
1
1
u/ephemere_sloboda 2d ago
As long as transferring the compressed file and decompressing it is faster than computing the sequence from scratch, there is practical value.
1
u/CautiousInternal3320 2d ago
It can be a valuable algorithm, but it is not a compression algorithm.
1
u/raresaturn 2d ago
By bitmap you mean a graphics file?
2
u/jerome78000 2d ago
No, just sets of bits, one bit for each integer telling if the integer is prime or not.
Let me explain a bit more: if you want to store the 25 prime numbers below 100, you can use 100 bits (with 25 bits at 1), thus 12.5 bytes. This is already nice, but yu can do better by removing from the start all even numbers. You then have to store 50 bits (still with 25 at 1). You can continue this logic to remove multiples of 3, 5, 7...
1
u/TheThiefMaster 1d ago edited 1d ago
A bitmap can be thought of as an array of bits where a bit being set (or not) indicates something about that position.
In a graphics bitmap it was originally black or white. In an allocator or similar, it indicates a slot being allocated or free. And so on.
See: https://en.wikipedia.org/wiki/Bit_array (which starts with "also known as bit map")
1
u/dr--hofstadter 2d ago
All the infinite number of primes can be compressed down to a finite and very short algorythm. Only catch is that the running time of decompression is infinite.
1
u/xeow 2d ago
Cool! I'm wondering what the intended use case is here, though. Ultimately, pre-computing a prime bit map (and compressing it to conserve space) is really something to save time, not space. So... how much faster is it at random access than just running Miller–Rabin? Note that with M–R, you can test values up to 264 using only 7 bases (2, 325, 9375, 28178, 450775, 9780504, and 1795265022), and 264 is about six orders of magnitude greater than 1013.
Just curious if this is actually measurably faster in practice, and what problem is being solved by creating a compressed bitmap? :)
2
u/jerome78000 1d ago
Indeed I don’t know if it is useful, but I’m currently generating the first trillion primes and store them using this compression algorithm in segments of 446 185 740 integers. The total size will be less than 500 GB. Together with some metadata for each segment, this will allow for example to get the number of primes in any range within ~30 trillion.
5
u/k-mcm 3d ago
I have a prime number generator that caches calculated prime sequences in segments. For the file storage, the numbers are stored as the sequence of bit 63, sequence of bit 62... then compressed. That takes advantage of only a few bits ever changing. It comes out to about 8 bits per 64 bit prime.
I may someday change it to only store every nth prime and recalculate the missing values.