How to compress this ?

Just starting out? Need help? Post your questions and find answers here.
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

How to compress this ?

Post by Olli »

This code gives a numbers list, I want to compress.
I would like to reach 2 bits per number. This seems crazy, but there are lots of identical values, lots of small curves, and lots of periodic patterns. This example runs to 10000 numbers, but the compression algo has to go to 400000000, that allows us to get a 100 megabytes sized binary file containing all the 32 bits sized prime numbers.

(each number gives a gap between two consecutives prime numbers, so each number gives indirectly - and very quickly - a prime number greater or equal to 5)

Code: Select all

n = 5
ff = 1
For i = 1 To 10000
 n0 = n
 Repeat
  n + 1
  sqn = Sqr(n)
  isp = 1
  For j = 2 To sqn
   If n % j = 0
    isp = 0
    Break
   EndIf
  Next
 Until isp
 gap = n
 gap - n0
 gap / 2
 tmp = gap
 g2 = 0
 While tmp
  tmp - ff
  g2 + 1
  ff ! %11
 Wend
 Debug Space(g2) + Str(g2)
Next
User avatar
netmaestro
PureBasic Bullfrog
PureBasic Bullfrog
Posts: 8425
Joined: Wed Jul 06, 2005 5:42 am
Location: Fort Nelson, BC, Canada

Re: How to compress this ?

Post by netmaestro »

2 bits per number isn't possible.
BERESHEIT
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: How to compress this ?

Post by Olli »

netmaestro wrote: Tue Oct 04, 2022 12:32 am 2 bits per number isn't possible.
Your answer implies that you know how to store a good bunch of prime numbers with 7 bits per number!
User avatar
jacdelad
Addict
Addict
Posts: 1431
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: How to compress this ?

Post by jacdelad »

Come on, Olli, with two bits you can distinguish 4 numbers. With 7 bits you have 128. You basically want to get all prime numbers up to #MaxLong. The result is less than #MaxLong, but to store the exact value you still need a long. You could try to put all relevant values into a row and compress them with some known algorithm, some are built in. But it won't work in any other way, unless you find a way to store more than one bit in one bit.
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: How to compress this ?

Post by NicTheQuick »

I guess your code itself is the best compression for this. To decompress the list, just compile and run it. :wink:
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: How to compress this ?

Post by Olli »

NicTheQuick wrote:To decompress the list[...]
If I find the time, I will add the code to decompress it on the head of the subject, with the 1st code.

A 8-bits processor which put from 4 to 6 gaps "g2" (g like Gap, no secret), through 256 op codes, I think it is doable.

added : not infinite.
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: How to compress this ?

Post by Olli »

Here is the flip-flop function to uncompress the list of "g2" values.

Code: Select all

Procedure fff(i)
   Protected r, j
   Static ff
   If ff = 0
      ff = 1
   EndIf
   For j = 1 To i
      r + ff
      ff ! %11
   Next
   ProcedureReturn r
EndProcedure

pn = 5
repeat
 Debug pn
 ; import g2 (compressed code) here
 pn + 2 * fff(g2)
until pn > 100
Olli
Addict
Addict
Posts: 1071
Joined: Wed May 27, 2020 12:26 pm

Re: How to compress this ?

Post by Olli »

Now, for my "idea" of 2 bits per number, and specifically 4*2 bits per a set of 4 to 6 numbers, the way is clear : not possible, as netmaestro said and as you, JacDeLad and NicTheQuick explained.

But... This list is very strange. I cannot read it now, but any weeks ago, I studied it to millions of values.

On one side, no compressor is able to zip it with a good coefficient.

On the other side, as the 1st code does it, if a insert a left margin sized by the displayed value, my eyes see some curves. If I turn the picture (90° left), I get a landscape. There are lots of symetries, and lots of waves.

And if continue to the right of the landscape, to the numbers bigger and bigger, I see a second landscape on the background, behind the fist and main landscape which is more and more shaked.

It gives the feeling we could do a 2D world, replacing numbers by any tiles.
Post Reply