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

A bootable CD image with a retro game in a single tweet

quaxio.com

Post reply on HN
Print view View original

81–90 of 150 posts

Re: A bootable CD image with a retro game in a single tweet

#81

Post by amake »

haser_au wrote: post #65
jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

The same has been said about Pi (3.14). If you can compute, store and search enough the digits of Pi, you can reference anything by just providing the 'start' and 'finish' locations. Unfortunately, with enough digits of Pi, the 'start' and 'finish' numbers can get quite long themselves.

Here's an implementation of precisely that, as a filesystem:

https://github.com/philipl/pifs

Discussed here previously (2014):

https://news.ycombinator.com/item?id=8018818

Re: A bootable CD image with a retro game in a single tweet

#82

Post by [deleted] »

troupe wrote: post #68
haser_au wrote: post #65

Earlier quoted context omitted.

The same has been said about Pi (3.14). If you can compute, store and search enough the digits of Pi, you can reference anything by just providing the 'start' and 'finish' locations. Unfortunately, with enough digits of Pi, the 'start' and 'finish' numbers can get quite long themselves.

Years ago I tried this and basically ended up proving that if Pi is random and you are "compressing" random data, on average the start and finish numbers together are at least as long as the numbers you are trying to "compress."

[deleted]

Re: A bootable CD image with a retro game in a single tweet

#83

Post by gballan »

jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

Reminds me of 'pulse position modulation' [1].

[1] https://en.wikipedia.org/wiki/Pulse-position_modulation

Re: A bootable CD image with a retro game in a single tweet

#84

Post by hamilyon2 »

magnat wrote: post #75
jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

> Or the machine language expression of the most advanced expert systems, though by then the notch might be small enough that Planck’s constant got in the way. With Planck's length being roughly 10^-35m, I'd say you'd hit the limit trying to store more than 15 bytes.

This is insightful. 15 bytes is not a lot. I wonder what are other narural limits on information density? For example, magnetic field. Is there a least measurable difference?

Re: A bootable CD image with a retro game in a single tweet

#85

Post by OscarCunningham »

ibotty wrote: post #79
troupe wrote: post #68

Earlier quoted context omitted.

Years ago I tried this and basically ended up proving that if Pi is random and you are "compressing" random data, on average the start and finish numbers together are at least as long as the numbers you are trying to "compress."

Did you proove it formally or only by experiment. If it were a real proof, did you publish it somewhere?

In fact, any lossless compression algorithm has the property that the output is (on average) at least as long as the input. The best you can hope for is an algorithm that compresses the kind of data that humans want to store, at the expense of making other data a bit longer. If you're trying to compress random data then you just can't do it.

Here's a proof: consider the strings of length n or less, suppose there are M of them in total. Their average length is just the sum of all their lengths divided by M, and the average length of their compressed versions is just the total length of the compressed versions divided by M. Since the compression is lossless the compressed strings must all be different.

Since there are M strings, if any of them mapped to a string of length more than n then there must be some string of length at most n not being mapped to, so the average length can be improved by instead mapping that string to the shorter string. So any optimal compression method must map only to the strings of length at most n.

So the M outputs are just the M inputs, possibly permuted. So their total length is the same, and hence their average length is the same.

Re: A bootable CD image with a retro game in a single tweet

#86

Post by Tepix »

magnat wrote: post #75
jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

> Or the machine language expression of the most advanced expert systems, though by then the notch might be small enough that Planck’s constant got in the way. With Planck's length being roughly 10^-35m, I'd say you'd hit the limit trying to store more than 15 bytes.

Also depends on the length of the metal rod, doesn't it?

Re: A bootable CD image with a retro game in a single tweet

#87

Post by Const-me »

OscarCunningham wrote: post #85
ibotty wrote: post #79

Earlier quoted context omitted.

Did you proove it formally or only by experiment. If it were a real proof, did you publish it somewhere?

In fact, any lossless compression algorithm has the property that the output is (on average) at least as long as the input. The best you can hope for is an algorithm that compresses the kind of data that humans want to store, at the expense of making other data a bit longer. If you're trying to compress random data then you just can't do it. Here's a proof: consider the strings of length n or less, suppose there are…

> any lossless compression algorithm has the property that the output is (on average) at least as long as the input.

The article you’ve linked says nothing about average. It says that for every algorithm there’s at least some input files that increase the size. It even explains more about that:

Any lossless compression algorithm that makes some files shorter must necessarily make some files longer, but it is not necessary that those files become very much longer. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input

Re: A bootable CD image with a retro game in a single tweet

#88

Post by praptak »

haser_au wrote: post #65
jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

The same has been said about Pi (3.14). If you can compute, store and search enough the digits of Pi, you can reference anything by just providing the 'start' and 'finish' locations. Unfortunately, with enough digits of Pi, the 'start' and 'finish' numbers can get quite long themselves.

The indexes will, on average, have more digits than the sequence you compress. This is true for any infinite sequence of digits, not only Pi.

Re: A bootable CD image with a retro game in a single tweet

#89

Post by OscarCunningham »

Const-me wrote: post #87
OscarCunningham wrote: post #85

Earlier quoted context omitted.

In fact, any lossless compression algorithm has the property that the output is (on average) at least as long as the input. The best you can hope for is an algorithm that compresses the kind of data that humans want to store, at the expense of making other data a bit longer. If you're trying to compress random data then you just can't do it. Here's a proof: consider the strings of length n or less, suppose there are…

> any lossless compression algorithm has the property that the output is (on average) at least as long as the input. The article you’ve linked says nothing about average. It says that for every algorithm there’s at least some input files that increase the size. It even explains more about that: Any lossless compression algorithm that makes some files shorter must necessarily make some files longer, but it is not nece…

Thanks. I realized this just after I posted it, so I wrote the proof into my comment instead.

Re: A bootable CD image with a retro game in a single tweet

#90

Post by sjcsjc »

haser_au wrote: post #65
jobu wrote: post #58

This reminds me a bit of the science of nanoinformatics as described in one of the Expanse novellas (The Vital Abyss): " A thought experiment from my first course in the program: Take a bar of metal and put a single notch in it. The two lengths thus defined have a relationship that can be expressed as the ratio between them. In theory, therefore, any rational number can be expressed with a single mark on a bar of met…

The same has been said about Pi (3.14). If you can compute, store and search enough the digits of Pi, you can reference anything by just providing the 'start' and 'finish' locations. Unfortunately, with enough digits of Pi, the 'start' and 'finish' numbers can get quite long themselves.

http://www.angio.net/pi/

My 11 digit phone number occurs around the 115 millionth digit, a grand saving of two digits.

Post reply on HN