πfs – A data-free filesystem
github.com
github.com
It's still in stealth mode but I'm hoping to unveil it sometime in late June.
I'm sure that you can do that before noon of the first of next month.
So I've designed a once-a-year data processing system. It's going to queue up all your requests throughout the year and save them for this "quiet window" and then distribute all the jobs across all network connected computers running this new code. I think I'll make a pull request to Linux for maximum coverage. The best thing is, there is absolutely no performance hit or impact on everyone's servers because they're ALREADY not being used.
Should work great for love letters too as long as I write them in UTF-8.
"At present it contains all possible pages of 3200 characters, about 104677 books." (https://libraryofbabel.info/About.html)
What? How? If this is something other than being able to write to libraryofbabel.info I am extremely confused.
Your comment was contained in this text before you even wrote it
The trick to seeing why it's on page 314 is to note that the spacing on the sentence is really odd. Since spaces are significant to the algorithm, the same words with different whitespace will end up on different pages of different books.
From the information on https://libraryofbabel.info/referencehex.html, we can see that each book has exactly 410 pages. Assuming that for any phrase X, the page that that phrase is on is independent and equally likely, then there is a 1/410 chance that the phrased being searched will be on page 314. So just write a script that hits libraryofbabel.info automatically with randomized spacing. You'll likely end up on a page that is 314 in about 410 or so tries.
Copy-paste error caused a dropped exponent. It's 10^4677 books.
The library, by the way, is quite big. You couldn't fit it all in our universe --- in fact, you'd need 10^4594.
My brain was apparently getting him confused with Victor Borge, who is also great, but differently. Stupid brain.
So... if your Internet connection goes down, you lose all your data?
So it is like every cloud service...
Granted, the index might be larger to represent than the actual sequence you're indexing, but...
Not only that, but Pi is normal (all digits distributed evenly), and your sequence clearly is not.
I understand what you are saying - indeed there are infinite finite sequences - but it just does not apply here.
As another commenter pointed out, pi is not proven to be normal, but is suspected to be.
Sure, but this doesn't answer the question: Do we know that every possible finite sequence is present? You can have the former without the latter being true. For example, a sequence of the form "1011011101111011111..."[0], while infinite, never contains the finite sequence "1234".
Pi is not proven to be normal, but is suspected.
It might turn out that Pi is not normal say in base 2, but all possible finite sequences of 0s and 1s occur in it, just with some of them being slightly more frequent than others of the same length.
The movie industry should just shut down now. Any two people implementing piFS will have already shared all possible movie files, including future, unreleased films.
Your medical records are now available to anyone with time and patience.
The horror!
(Seriously, we should see if we can wind up Spicer about that first one and see if he explodes).
So basically like a regular filesystem except now lookup each byte every time you intend to use it?
In those situations, you can bet money that some compression scheme will be proposed that fits into at least one of the two categories "did not check to see if it actually compresses data" or "works by hiding bits where you forgot to count, but they still count".
"I'll just give an offset into pi" is in the first category; it does, technically, work, in the sense that it can validly represent the original data, but it turns out that in order to represent the offsets into pi it takes more bits than the content had in the first place. (You can get lucky every once in a while, and store 14159265 as "0/8", but the vast, vast majority of sequences get expanded.) Everyone proposes this one. It's almost funny how often it gets proposed, given that it is actually a very slow method for making your data bigger. Don't hold your breath for your Fields Medal for that one.[1]
An example of the second case is "I'll just store the first few bytes in the filename of the file and then 'forget' that I have to count the filenames in the size of the compressed content". Vigorous, month-long debates about whether or not something "counts" as part of the content will follow, which can be resolved by pointing out that the challenge is basically to give a stream of bytes over the network to a computer that only has the algorithm on it that fully reconstructs all the content, but this rarely satisfies Our Hero who has discovered perfect compression.
I add the word "moral" not just as a jab, but as the only way I have to explain how these people react to things like pointing out "if that worked, I could compress all files to one bit/one byte" or "I can't actually reconstruct the original content with that information". They get offended.
[1]: Just for fun, let's implement the ideal "index into a sequence" compression algorithm. This is not written to proof standards, but "give the reader the flavor of what is going on" standards. (Technically it assumes the proof, in an attempt to illuminate it from another direction.) The problem with pi is that it tends to repeat a lot. Let's chunk up 8 bits into a byte, since that's pretty common, and let's build the idea sequence of bytes that we can index into easily. For completeness, let's just index the 8-bit bytes in a one sequence:
00000000000000010000001000000011
You'll find this approach, extended into as many consecutive bits in a row as you please, will wildly outperform pi as a sequence to index into to get values. Because this is, of course, just the identity transform, and pi in practice does way worse than that. This transform is also wildly more efficient than the pi indexing operation, having computational complexity O(zero), if you'll pardon me the abuse of notation.
Could you write that proof here, for the benefit of tired HNers who are just finishing their day of work?
The "literally sketchable on a post-it note" is that you can show this for 1 bit, 2 bits, and 3 bits pretty easily, and 4 bits if you sketch small enough. At that point it's not hard to see this goes to infinity, maybe not rigorously enough to pass for a proof, but pretty strong. (It's a fairly small step to an inductive proof from there, though this verges on a trivial proof by the time you've laid all the bits out.)
EDIT: The sibling comment from rmidthun is much more rigorous and concise, so if you're looking for a more proper explanation, ignore this and read that
To anyone confused: Look today's date!
I celebrate christmas too.
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?
Your compression ratio would approach infinity.
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.
Thus - storing and maintaining the offset in PI becomes more expensive than storing data elsewhere.
As long as you know the index into p of your file and its length,
its a simple task to extract the file using the Bailey–Borwein–Plouffe
formula Similarly, you can use the formula to initially find the index of your file
Now, we all know that it can take a while to find a long sequence of digits in p,
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 p.
You would not need to store the entire number.
https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%9...
You
A really great literary read btw.
As other posts already said, if, as many think, π is normal (https://en.m.wikipedia.org/wiki/Normal_number), every sequence appears in it. If it isn't, that still is open.