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

πFS

github.com

Post reply on HN
Print view View original

211–220 of 224 posts

Re: πFS

#211

Post by jerf »

liamYC wrote: post #99
adzm wrote: post #12

It is worth noting that as the length of data increases it becomes extremely unlikely that the index and length of the sequence within pi would actually be smaller than the data.

Point taken about the index potentially being really long. Why would the length be longer than the data? Don’t you need to find the right sequence?

I wonder if it might make more sense to come at it from the opposite angle. Take pi as a sequence you want to compress with. But pi, being random, has redundancies in it that make it less than optimal. So instead, for a given size of block you want to look up, design the optimal number to use for compression. For instance, if you want to compress "594" in the digits of pi, the sequence 253 appears before it twice, which means any attempt to "compress" any three-digit sequence that only first appears after the second 253 is costing you more to get past the second 253, and "pi, but with all the 253s removed after the first one" is clearly a more efficient encoder for 3-digit numbers than pi itself.

So, instead of using pi, design an optimal number to encode with.

What you'll find is that the optimal sequence ends up being equally efficient as listing the blocks in order and indexing by block number itself. There are a number of other solutions; you could use superpermutations to get "all possible subsequences" with fewer digits in your target number, but you'll end up needing to provide the encoder and decoder a table of where the digit sequences appear since they are no longer regular and indexing into that table will cost exactly the same as just writing your number as the concatenation of all the blocks and its efficient method for indexing into them by indexing on the block rather than the digit number.

This actually has some natural overlap with the "normal numbers" in that one of the earlier normal numbers was: https://en.wikipedia.org/wiki/Champernowne_constant I'm not sure whether this is necessarily optimal for an arbitrary block size. (My quick intuitive check suggests it may be, but "my quick intuitive check" in the time of an HN post is not something I'd count on.) In this scheme, you can include the fact that the person using this constant to encode knows the nature of the constant, so they know that if you give index 0-9, it's single digit, and if you index into the two-length blocks, it must have a length of two. Since the encoder and decoder know that, they can also skip the middle of the block and just index into "the n'th number"... which degenerates into "the index of number N is N", which means this is not a compression scheme.

To put all that in a nutshell, if you want to deeply understand why this compression scheme doesn't work, I think you can attain a deep understanding of why by optimizing it.

Re: πFS

#212

Post by sam_goody »

Theoretically, if we had a GPU so fast it could instantly calculate billions of digits of Pi, and a small hard drive, could this actually be made to work?

Cache all the last lookups but otherwise just store the index within pi? And for larger files - split them into chunks of whatever size could be handled?

(I mean, I realize this is a joke and can't make sense - but GPUs can be really really fast, and am willing to make a fool of myself by asking.)

And if we had a quantum computer that stores all of pi on one qubit, that could make things even faster ;/

Re: πFS

#213

Post by hnbad »

So this is how I find out that in Verdana lowercase pi looks exactly like lowercase Cyrillic п (pe), i.e. like an open rectangle rather than a bit curvy.

Re: πFS

#214

Post by cestith »

nz wrote: post #199
ithkuil wrote: post #119

Earlier quoted context omitted.

You'll find this an interesting watch: Reinventing Entropy Compression is Intelligence Part 1 3blue1brown https://youtu.be/l6DKRf-fAAM?is=ne73FCJ7ErXhzZ-v

You, and the HN users, `lojban`, `klingon`, `ido`, `brithenig`, `solresol`, `babm`, and `tokipona`, may want to start a club. Amusingly, nobody seems to have registered the `esperanto`, `volapuk`, `interslavic`, `balaibalan`, and `dothraki` usernames.

I don’t see users with ‘khuzdul’, ’sindarin’, or ‘quenya’ either.

Re: πFS

#216

Post by everforward »

ainch wrote: post #111
jamwise wrote: post #31

Reminds me of when I tried to use the library of babel as a data compression tool. It led me down a fun rabbit hole and was my first introduction to information theory. The conclusion being that you basically need the same amount of data to represent the address of your data as the data itself, so it's not really effective at compression, just a fun thought experiment. The cool part of this in modern times is that LL…

In some sense, science is the most extreme form of compression - Newtonian mechanics explains an incredible number of phenomena in a few lines of text.

It does, but only vaguely unless you already know how it works and can work backwards to Newton's laws. Eg Newtonian mechanics can explain how flying works, but if you don't already know then it's hard to go from Newton's 3 laws to a functional explanation of why planes don't fall out of the sky.

Some of that is also the domain. It's less that science is an extreme form of compression, and more that natural phenomenon are highly compressible. They're a small number of kinds of interactions repeated a bajillion times. How many equations does it take to explain electricity (ignoring equations that are derivatives of ones already included)? I think it's less than 5.

On some level, you could probably reduce all of the Standard Model down to models of atoms, their motion, and the basic subatomic particles (the non-quantum ones). That would explain almost everything that happens on Earth in a very short form, though few people would be able to go from that to explaining how lightning works.

Re: πFS

#217

Post by poilcn »

helterskelter wrote: post #112
dekhn wrote: post #104

Earlier quoted context omitted.

I once interviewed for a company and the interviewer was telling me how he (a vc) funded a project to generate large streams of random numbers; you would select an index at random, share that private key with somebody, and then the subsequent text could be used as a one-time-pad. NSA would be forced to buffer/save the entire stream, which could be generated at GB/sec, if they wanted to decrypt. It didn't seem very pr…

I wonder if we could mess with NSA-style surveillance by having a good chunk of the population streaming lots of random data over the internet. Essentially, Alice piping her /dev/random to Bob's /dev/null over netcat or something. Make a slick looking app that does it 24/7 in the background using excess bandwidth and tell people it sticks it to the NSA. Spy agencies would not only have to store it all in case it was…

That's kinda happen right now. Telegram's proxy produce huge amount of garbage data to hide and avoid blocking

Re: πFS

#218

Post by ainch »

everforward wrote: post #216
ainch wrote: post #111

Earlier quoted context omitted.

In some sense, science is the most extreme form of compression - Newtonian mechanics explains an incredible number of phenomena in a few lines of text.

It does, but only vaguely unless you already know how it works and can work backwards to Newton's laws. Eg Newtonian mechanics can explain how flying works, but if you don't already know then it's hard to go from Newton's 3 laws to a functional explanation of why planes don't fall out of the sky. Some of that is also the domain. It's less that science is an extreme form of compression, and more that natural phenomeno…

I agree it's an oversimplification. The example I think of is something like Newton's law of gravitation vs Ptolemaic epicycles: one simple explanation replaced many layers of tweaks.

It's also a relevant example for AI - one paper tested the ability of Transformers to model planetary orbits: unlike Newton's Law, the implicit forces they learn are nonsense.

https://arxiv.org/pdf/2507.06952

Re: πFS

#219

Post by matneyx »

utopiah wrote: post #193

"This file doesn't look like what I remember. Are you sure? It's been a while since you last opened it. Memory is funny like that. The file is fine — maybe take another look with fresh eyes." from https://github.com/philipl/inferencefs/ Maybe I do not indeed remember properly. Anyway, back to watching "Eternal Sunshine of the Spotless Mind" for the first time, I think.

The FAQ just keeps getting creepier...

Re: πFS

#220

Post by 47282847 »

jnovek wrote: post #200
jamwise wrote: post #31

Reminds me of when I tried to use the library of babel as a data compression tool. It led me down a fun rabbit hole and was my first introduction to information theory. The conclusion being that you basically need the same amount of data to represent the address of your data as the data itself, so it's not really effective at compression, just a fun thought experiment. The cool part of this in modern times is that LL…

If you set temperature to 0.0 you almost have a key-value store, but finding the right key for your value might take some effort.

https://github.com/philipl/inferencefs/ by the same author in case you missed it
Post reply on HN