Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

File system that stores location of file in Pi

github.com

Post reply on HN
Print view View original

91–100 of 102 posts

Re: File system that stores location of file in Pi

#91

Post by Chinjut »

nadam wrote: post #56

When I was young I had this idea that any hard drive can be compressed into 100 bytes. The compressed data is a 4 dimensional vector, a component of the vector is a 25 byte floating point number, and represent the space-time coordinates of the hard drive. (For example my hard drive in 1994 marc 3 23:00:45.456 at a specific place in Budapest) The extractor algorithm just have to simulate the universe from the big bang…

That's quite clever. Of course, only 2^800 hard drives can actually be represented in this way, but it would, by definition, be in principle capable of covering everything we would ever desire to place on a hard drive anywhere (during the relevant time period, in the relevant space, to the relevant resolution...).

One drawback (on top of astronomically slow extraction time...), is that this still requires us to go ahead and actually write the data in uncompressed form onto a hard drive somewhere. So storage space is still taken up at some point in the world, but at least we can erase and reuse that space as soon as we like, and transmit the data elsewhere with minuscule bandwidth.

Of course, all this really amounts to "Any data you are actually interested in presumably has a short description (e.g., something like 'A complete audio and video recording of every occurrence in Eurasia over the 10,000 years beginning with 6000 BC') and thus, in perfectly compressed form, you will never have any need for large numbers of bits". Or, put another way, "There can't be more than [some reasonably finite number] pieces of data you will ever actually be interested in in your very finite life, so as far as you're concerned, log_2([said number]) bits suffices for everything".

Re: File system that stores location of file in Pi

#92

Post by baddox »

nadam wrote: post #67
baddox wrote: post #62

Earlier quoted context omitted.

Even if all your assumptions hold, of course, you can still only represent 2^800 universes, and thus only 2^800 different file systems. That's probably sufficient for cases with infrequent read-write cycles, assuming that your floats tend to cover useful time-space coordinates (i.e. where and when a hard drive could plausibly reside). I'm not sure how "space-time coordinates" would work (where is the origin and what…

" That's probably sufficient for cases with infrequent read-write cycles, assuming that your floats tend to cover useful time-space coordinates (i.e. where and when a hard drive could plausibly reside). I'm not sure how "space-time coordinates" would work (where is the origin and what is the granularity?), so I don't know if it's likely." Now I have calculated a little: The age of the universe is 8 * 10^60 in planck…

It sounds like you probably don't need or want floats then. Just a uniform number format for the coordinates should suffice.

Re: File system that stores location of file in Pi

#93

Post by peterwwillis »

Tuna-Fish wrote: post #89
peterwwillis wrote: post #83

Earlier quoted context omitted.

I 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?

Let'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. Compressi…

I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all.

The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointing to a single point in a 107 billion byte long file.

You just do the same thing with Pi, except in this case Pi is the 107-billion byte file, and position 53687091200 points to the file's beginning point. The only thing you store is 11 bytes + the size of the file. (Of course wouldn't store the location in ASCII as binary would be a much smaller representation, but for these purposes i'm just using ASCII) Obviously the size of Pi is infinite and the size of the position would be much larger than 50-billion in, but the idea is the same.

Please tell me in simpler terms how this idea does not work?

Re: File system that stores location of file in Pi

#94

Post by [deleted] »

peterwwillis wrote: post #93
Tuna-Fish wrote: post #89

Earlier quoted context omitted.

Let'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. Compressi…

I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all. The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointi…

[deleted]

Re: File system that stores location of file in Pi

#95

Post by jdmichal »

peterwwillis wrote: post #93
Tuna-Fish wrote: post #89

Earlier quoted context omitted.

Let'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. Compressi…

I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all. The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointi…

Let's say you wanted to encode a single decimal digit using this PI method. So, to start, you list out PI until you get all the possible decimal digits:

    03 14159 26535 897
    01 23456 78901 234
There, that's all of them. I cheated a bit and put a zero in the front, as the first zero in the expansion is another 10 digits or so away. So now, we can represent any decimal digit by indexing into PI!

    0 - 0
    1 - 2
    2 - 7
    3 - 1
    4 - 3
    5 - 5
    6 - 8
    7 - 14
    8 - 12
    9 - 6
So, what did we accomplish? Well, zero stays the same. We successfully renamed 1-6 and 9 to be new numbers. And now 7 and 8 take two decimal digits.

Now, extrapolate this out to every possible 100GB file, and the binary representation of PI.

Re: File system that stores location of file in Pi

#96

Post by haberman »

peterwwillis wrote: post #83
Tuna-Fish wrote: post #42

Earlier quoted context omitted.

By 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.

I 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?

> Why wouldn't this work?

It would work, exactly like you say. However, you seem to intuitively be vastly underestimating how far into pi you have to go to find a particular bit pattern.

To sharpen your intuition of this, I recommend this website: http://pi.nersc.gov/

I tried searching pi for the string "zzzz" (this is 20 bits of information according to their somewhat weird encoding scheme). The decimal position in pi for this 20-bit string was 3725869808, which takes 32 bits to represent.

The same will be true in most cases -- the offset into pi will take more space to represent than the data itself! However, in some cases data absolutely can be compressed with this pi scheme. Just not often enough to be actually useful.

However, the fact that the data will usually be larger is not what the pigeonhole principle is about.

All the pigeonhole principle says is: it's not possible for every 100 GB file to have a offset in pi that takes less than 100GB to represent. The pigeonhole principle still allows some files to be compressable with pi, just not all.

To prove this is simple: take every possible 100GB file (there are 2100G of them). Now let's suppose that for every single one you can actually find a location in pi whose binary representation is less than 100GB to represent. If you can do this, then it means that at least 2 of the input files mapped to the same location in pi (because there were 2100G distinct input files but less than 2100G pi offsets that we are allowed to use). Therefore, once "compressed", you can't tell the difference between the two input files that both mapped to the same location in pi!

Re: File system that stores location of file in Pi

#97

Post by Chinjut »

nadam wrote: post #67
baddox wrote: post #62

Earlier quoted context omitted.

Even if all your assumptions hold, of course, you can still only represent 2^800 universes, and thus only 2^800 different file systems. That's probably sufficient for cases with infrequent read-write cycles, assuming that your floats tend to cover useful time-space coordinates (i.e. where and when a hard drive could plausibly reside). I'm not sure how "space-time coordinates" would work (where is the origin and what…

" That's probably sufficient for cases with infrequent read-write cycles, assuming that your floats tend to cover useful time-space coordinates (i.e. where and when a hard drive could plausibly reside). I'm not sure how "space-time coordinates" would work (where is the origin and what is the granularity?), so I don't know if it's likely." Now I have calculated a little: The age of the universe is 8 * 10^60 in planck…

For what it's worth, despite the common perception that the Planck length is the the grid-scale on which the world is quantized, or the smallest measurable distance, or various such things, the Planck length is not actually known to have any particular physical significance; it's just the length that falls out of combining various other constants of significance. It's not unreasonable to guess that it will eventually turn out to have some significance in itself, but if there is any, it is as of yet unknown.

Re: File system that stores location of file in Pi

#98

Post by Tuna-Fish »

peterwwillis wrote: post #93
Tuna-Fish wrote: post #89

Earlier quoted context omitted.

Let'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. Compressi…

I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal. And I have no idea what your second paragraph means at all. The idea that a single reference point in a set is larger than the entire set itself is also ridiculous. If I have a 100-gigabyte file, and I want to point to the position in the middle, that is position 53687091200. That is an 11 byte string pointi…

> and the size of the position would be much larger than 50-billion in, but the idea is the same.

The crucial part is that the size of the position will be larger than the file you are seeking. This is unintuitive, but necessarily true for most possible files because of the pigeonhole principle. If you don't believe me, just try it out. Decide on random 4-digit sequences in pi and find their indexes. The mean of their indexes will be >4 digits. Same is true of any sequences of any length.

> I don't get this at all. You're talking about multiple files, which has nothing at all to do with my proposal.

No, I'm talking about multiple possible files, of which you must be able to compress and decompress any single one for your proposal to work in general.

General compression is mathematically proven to be impossible. If you have a compression algorithm f() which can take any input, in order for it to be able to compress some input of length x into a form that is shorter than x, it must also compress some other input of length x into a form that is longer than x.

Or, to put in another way, the sum of len(f(y)) for all possible y where len(y) = x is always greater than or equal to sum of len(y).

Re: File system that stores location of file in Pi

#99

Post by haberman »

haberman wrote: post #96
peterwwillis wrote: post #83

Earlier quoted context omitted.

I 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?

> Why wouldn't this work? It would work, exactly like you say. However, you seem to intuitively be vastly underestimating how far into pi you have to go to find a particular bit pattern. To sharpen your intuition of this, I recommend this website: http://pi.nersc.gov/ I tried searching pi for the string "zzzz" (this is 20 bits of information according to their somewhat weird encoding scheme). The decimal position in…

Aw shoot, where my comment above says "2100G" that was supposed to be "2^100G". HN ate my double-asterisk.

Re: File system that stores location of file in Pi

#100

Post by rmc »

delinka wrote: post #87
patio11 wrote: post #35

Earlier quoted context omitted.

Yep. Consider the minimum case: assume we've described a process for finding any bitstream we want in pi while necessarily saving at least one bit. Attempt to do so for the bitstreams 00, 01, 10, and 11. If we compress 2 bits to 1 bit, by the pigeonhole principle, at least one of 0 and 1 has to represent at least 2 distinct bitstreams, which means we have lost data. A similar argument works for all compression algori…

"It is flatly impossible to compress all data all of the time." Might I add "...such that the uncompressed data is recoverable." Pedantically speaking, any data passing through a cryptographic hash algorithm is being compressed.

Pedantically, that's not compression.
Post reply on HN