3 ms·

I love the idea of this, it has certainly boggled my mind a handful of times when thinking of content-addressed storage. Obviously it can't work, there is no lo

I love the idea of this, it has certainly boggled my mind a handful of times when thinking of content-addressed storage. Obviously it can't work, there is no loophole to infinite space or compression. Entropy is a very real thing. But it did lead me down an interesting train of thought. > maximise performance, we consider each individual byte of the file separately, and look it up in π. Ok, so we store a byte and look it up in π. Now we get an offset. The exact offset will depend on the byte of course. But to simplify let's assume that π is "optimal". We will assume that the fist 256 offsets contain the first 256 bytes. So our offset will be in the range 0-255. Storing our offset will then take 1 byte of storage. Oh, I have found the problem. So yes, you can find any data in π. But storing the location of that data will on average take the same amount of space as the data itself.

ignoramous 3y ago
> I love the idea of this, it has certainly boggled my mind a handful of times when thinking of content-addressed storage You only need 2 bits 1 and 0 to store every file there can ever be, and then store sequences in file metadata. Call it bifs.
SirMaster 3y ago
Why are you storing an offset for each byte? I thought you are supposed to find the offset where your entire file is sequentially there in pi. Because if it's infinite and not repeating, then that string should be in there somewhere.
- kevincox 3y ago
  Because that is what the project does. But I suspect that the analysis would look very similar for the entire file. Just calculate the average offset of the file of a given size. It won't be smaller than the file itself.
  - kevincox 3y ago
    I guess that is mostly true. In theory you could think of a more efficient way to store the indexes such as run-length encoding. So you could store 1M of whatever the first byte of Pi is and then run-length encode the 1M zero addresses. You can also imagine a scheme such as 2 bit varint encoding the indexes or a tally system that only uses 1 bit per offset to store a zero. ...of course you are still better off to just compress the file consisting of a single repeated byte.
BugsJustFindMe 3y ago
> So yes, you can find any data in π. But storing the location of that data will on average take the same amount of space as the data itself. Not on average. Not even at minimum. Since the leading values of pi are definitely _not_ so compact (and we have yet to identify any contiguous segment that is), the absolute minimum is N + plus the overhead to support the optimization of sometimes only using single-byte offsets by declaring the offset size as a header.
- kevincox 3y ago
  I don't think this is true. If I coincidentally want to store the first million of digits of Pi then my offset is 0 which is certainly smaller than the data. So you can get lucky.
  - BugsJustFindMe 3y ago
    Not here, because this mechanism stores offsets to individual bytes not large blobs. Storing the first N bytes of Pi (it makes more sense to talk about bytes than digits) requires N offsets plus either a header indicating how big each offset needed to be or variable-length delimited offsets, which necessarily likewise increases the offset size. In the absolute smallest case that's N+1 bytes.

ignoramous 3y ago

> I love the idea of this, it has certainly boggled my mind a handful of times when thinking of content-addressed storage You only need 2 bits 1 and 0 to store every file there can ever be, and then store sequences in file metadata. Call it bifs.

SirMaster 3y ago

Why are you storing an offset for each byte? I thought you are supposed to find the offset where your entire file is sequentially there in pi. Because if it's infinite and not repeating, then that string should be in there somewhere.

kevincox 3y ago
Because that is what the project does. But I suspect that the analysis would look very similar for the entire file. Just calculate the average offset of the file of a given size. It won't be smaller than the file itself.
- kevincox 3y ago
  I guess that is mostly true. In theory you could think of a more efficient way to store the indexes such as run-length encoding. So you could store 1M of whatever the first byte of Pi is and then run-length encode the 1M zero addresses. You can also imagine a scheme such as 2 bit varint encoding the indexes or a tally system that only uses 1 bit per offset to store a zero. ...of course you are still better off to just compress the file consisting of a single repeated byte.

BugsJustFindMe 3y ago

> So yes, you can find any data in π. But storing the location of that data will on average take the same amount of space as the data itself. Not on average. Not even at minimum. Since the leading values of pi are definitely _not_ so compact (and we have yet to identify any contiguous segment that is), the absolute minimum is N + plus the overhead to support the optimization of sometimes only using single-byte offsets by declaring the offset size as a header.

kevincox 3y ago
I don't think this is true. If I coincidentally want to store the first million of digits of Pi then my offset is 0 which is certainly smaller than the data. So you can get lucky.
- BugsJustFindMe 3y ago
  Not here, because this mechanism stores offsets to individual bytes not large blobs. Storing the first N bytes of Pi (it makes more sense to talk about bytes than digits) requires N offsets plus either a header indicating how big each offset needed to be or variable-length delimited offsets, which necessarily likewise increases the offset size. In the absolute smallest case that's N+1 bytes.