3 ms·

I wonder, assuming the computation was instantaneous, how effective it would be for compression.

by kukx 10y ago

aratno 10y ago
You mean, if there was an oracle for instant pi-index lookup? All finite-length strings can be expressed as natural numbers, so the pi-index is just a mapping from that number to another, pi: N -> N, with no guarantee of any more efficiency. Over the set of all finite-length strings, I do not think this would provide an advantage. But it might be fun.
- ehsankia 10y ago
  What if we split of the data into chunks? Let's say I have enough digits of PI stored that guarantees any chunk of x characters is found in there. Now, I encrypt my file that is k * x in size with k indices into pi. May possible improve if we use variable size chunks too. Would this not provide pretty good compression ratios? Compression may be slow, though it'd be sped up if you can the precomputed digits of pi (and maybe even some prebuilt prefix datastructure of some sort?). Decrypting, you can use the BBP formula so you wouldn't need all the digits of pi (though having the database would speed it up quite a bit). Anyone have any sort of rough estimate on how this would perform in speed and compression ratio?
  - deleted 10y ago
    [deleted]
greggyb 10y ago
If computation is instantaneous, then you could recurse down to a single pointer, which points to a pair of pointers, which each point to another pair, and so on until you have an arbitrary amount of your data. Since computation is instantaneous, it is instantaneous to compute this first pointer for the contents of any hard disk. And since computation is instantaneous, rebuilding the files on the disk from that pointer is instantaneous. Your compression ratio would approach infinity.
- greggyb 10y ago
  Nevermind, I neglected to take into account the length of that pointer: https://news.ycombinator.com/item?id=13870098 https://news.ycombinator.com/item?id=13870098
rnhmjoj 10y ago
I think the offset is bigger than the actual information you want to store in most of the cases.
deleted 10y ago
[deleted]
mikeash 10y ago
The pigeonhole principle means that compression can never be effective on average. For every input that can be compressed, there must be others that are expanded, such that the average compression ratio is at best 1. Useful compression algorithms take advantage of the fact that inputs aren't evenly distributed. Real-world data tends to have repetition, self-similarity, or predictability, which real-world algorithms use to produce smaller output. It's unlikely that πfs would provide useful compression for any real data, since it would have to line up entirely by random chance.

I wonder, assuming the computation was instantaneous, how effective it would be for compression.

by kukx 10y ago

I wonder, assuming the computation was instantaneous, how effective it would be for compression.

You mean, if there was an oracle for instant pi-index lookup? All finite-length strings can be expressed as natural numbers, so the pi-index is just a mapping from that number to another, pi: N -> N, with no guarantee of any more efficiency. Over the set of all finite-length strings, I do not think this would provide an advantage. But it might be fun.

ehsankia 10y ago
What if we split of the data into chunks? Let's say I have enough digits of PI stored that guarantees any chunk of x characters is found in there. Now, I encrypt my file that is k * x in size with k indices into pi. May possible improve if we use variable size chunks too. Would this not provide pretty good compression ratios? Compression may be slow, though it'd be sped up if you can the precomputed digits of pi (and maybe even some prebuilt prefix datastructure of some sort?). Decrypting, you can use the BBP formula so you wouldn't need all the digits of pi (though having the database would speed it up quite a bit). Anyone have any sort of rough estimate on how this would perform in speed and compression ratio?
- deleted 10y ago
  [deleted]

greggyb 10y ago

If computation is instantaneous, then you could recurse down to a single pointer, which points to a pair of pointers, which each point to another pair, and so on until you have an arbitrary amount of your data. Since computation is instantaneous, it is instantaneous to compute this first pointer for the contents of any hard disk. And since computation is instantaneous, rebuilding the files on the disk from that pointer is instantaneous. Your compression ratio would approach infinity.

greggyb 10y ago
Nevermind, I neglected to take into account the length of that pointer: https://news.ycombinator.com/item?id=13870098 https://news.ycombinator.com/item?id=13870098

rnhmjoj 10y ago

I think the offset is bigger than the actual information you want to store in most of the cases.

deleted 10y ago

[deleted]

mikeash 10y ago

The pigeonhole principle means that compression can never be effective on average. For every input that can be compressed, there must be others that are expanded, such that the average compression ratio is at best 1. Useful compression algorithms take advantage of the fact that inputs aren't evenly distributed. Real-world data tends to have repetition, self-similarity, or predictability, which real-world algorithms use to produce smaller output. It's unlikely that πfs would provide useful compression for any real data, since it would have to line up entirely by random chance.