5 ms·
Now, we all know that it can take a while to find a long sequence of digits in π, so for practical reasons, we should break the files up into smaller chunks t
by zaroth 12y ago
Now, we all know that it can take a while to find a long sequence of digits in π,
so for practical reasons, we should break the files up into smaller chunks that
can be more readily found.
In this implementation, to maximise performance, we consider each individual byte
of the file separately, and look it up in π.
Definitely worth a chuckle. Very cute idea and implementation.
- microcolonel 12y agoYou laugh now, but when we develop a trivial method to calculate pi and other irrational constants to quadrillions of digits, this will be wonderful.
- baddox 12y agoI bet I could take a few moments and come up with a proof that such a method would require P=NP.
- dtech 12y agoI can't find an authoritative source on this, but the algorithm used by SuperPi: https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorit... seem polynomial in the number of digits you want to calculate at first glance.
- baddox 12y agoEven if that's the case, wouldn't the number of digits of pi that must be computed to find a n occurrence of a random bit string of length n not be polynomial in n?
- Tuna-Fish 12y agoBy the pigeonhole principle, no matter how fast you can calculate pi, you cannot actually use this to compress data. The index to relevant sequence is on average >= the size of the data to be stored.
- mrpopo 12y agoI was thinking so hard trying to give myself a clear explanation of why this type of compression was impossible! Thank you. Here is the pigeonhole principle on wikipedia: http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle
- TheAuditor 12y agoI know :D I tried it for past 6 months and then gave up on it 2 months back, for the same reason. how ever that search gave rise to a better idea to compress files. Not yet usable but don't have all these issues with it. If you are interested you can read it at https://www.academia.edu/7620004/Advanced_Compression_Technique_For_Random_Data https://www.academia.edu/7620004/Advanced_Compression_Techni... It is based on data being represented as a position and not as the values in a computable number series .
- peterwwillis 12y agoI don't get how this applies. If you have a 100-gigabyte file you want to "compress" with Pi, all you have to do is find the beginning of that exact sequence in Pi and write down its location and the size (100gigabytes). As long as the binary representation of the location within Pi was less than 100 gigabytes, it is now "compressed". Why wouldn't this work?
- mikeash 12y agoFor most candidates, the binary representation of the location will be 100GB or more.
- Tuna-Fish 12y agoLet's say you want to store a 100kB file. There are 2^(8 x 102400) possible different 100kB files. The lowest amount of data you need to be able to distinguish the one you want from all the possible candidates is 100kB. If you could compress any file with the same algorithm, it would mean that you would necessarily have to be able to decompress the exactly same compressed file into multiple different files. Compression can only work when for every byte you take out of a file you want you need to concede to add another byte to the representation of a file you don't care about. > write down its location and the size The location of any arbitrary sequence in pi is on average a much larger number than the sequence itself.
- sqrt17 12y agoIf you used small chunks (say, up to four bytes) you could just have a lookup table storing all the indices. Or - what a genius idea! - we could use Pi itself as a lookup table and use the sequence of n bytes at that position of pi as an implicit lookup table.
- lubos 12y agoThere are 4,294,967,296 possibilities in 4 bytes. To store a number in range of 0 to 4,294,967,296 - you will need exactly 4 bytes.
- sqrt17 12y agoNot all 32bit sequences can be found in the first 4,294,967,296 binary digits of pi. Hence you will either need more then 4 bytes to encode 4 bytes in a pi position or a lookup table to fit the 4,294,967,296 numbers, some of which will be substantially larger than 4,294,967,296, into 4,294,967,296 slots.
- delinka 12y agoTo save us from searching in the number space after 4.3-ish billionth slot, we could just store the sequences that we didn't find in that part of pi. I propose a bit used to indicate whether the current sequence is a pi-sequence or just raw data.
- fla 12y agoAnd what will you do when you know that 0xdeadbeef is located at index 54'896'523'871 ? store the index as a 64bit number ? ;) Edit: typo
- irodov 12y agoCould have made it even better by considering individual bits separately, and using their positions.