File system that stores location of file in Pi

by morisy • 12 years ago

310 98 12 years ago

somid3• 12 years ago

Fascinating implementation I must admit. How does i/o performance change as the byte-length or chunks vary in size from 3 to 200 bytes?

ch4ch4• 12 years ago

I think it would probably take forever for the initial lookup, because the probability of matching any 3 byte sequence is higher than matching a 200 bytes sequence?

zaroth2• 12 years ago

Literally forever, right?

It's basically scanning a random byte-stream for a 200-byte long exact match. 200 bytes, 1600 bits, or 2^1600 different possible sequences, making the odds 1/2^1600 that any particular 200 bytes pulled out will match the bytes you are looking for.

Jack5500• 12 years ago

This project was posted before and hasn't been updated since. I doubt that it is still in development

XorNot• 12 years ago

Its also pretty obviously an elaborate mathematics joke.

E_Carefree• 12 years ago

Yes, but it conceivable. It's like a code. You could securely save files with two numbers. Just a position and length.

opinali• 12 years ago

Because nobody likes Pi anymore, we need the Tau filesystem.

calvins2• 12 years ago

Nah, e is obviously the best transcendental number.

I hope the author's pending patent is limited to pi though, so I can work on ef^H^H. Hmm, I see why maybe the author preferred pi over e.

zaroth2• 12 years ago

  Now, we all know that it can take a while to find a long sequence of digits in π,
  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 π.

Definitely worth a chuckle. Very cute idea and implementation.

microcolonel• 12 years ago

You laugh now, but when we develop a trivial method to calculate pi and other irrational constants to quadrillions of digits, this will be wonderful.

baddox5• 12 years ago

I bet I could take a few moments and come up with a proof that such a method would require P=NP.

Tuna-Fish3• 12 years ago

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.

sqrt172• 12 years ago

If you used small chunks (say, up to four bytes) you could just have a lookup table storing all the indices.

Or - what a genius idea! - we could use Pi itself as a lookup table and use the sequence of n bytes at that position of pi as an implicit lookup table.

lubos• 12 years ago

There are 4,294,967,296 possibilities in 4 bytes.

To store a number in range of 0 to 4,294,967,296 - you will need exactly 4 bytes.

fla• 12 years ago

And what will you do when you know that 0xdeadbeef is located at index 54'896'523'871 ? store the index as a 64bit number ? ;) Edit: typo

irodov• 12 years ago

Could have made it even better by considering individual bits separately, and using their positions.

bunderbunder• 12 years ago

I'm skeptical that this could really save any space. Just speculating here, really, but it seems like on average the amount of space needed to store the starting index of an arbitrary string of digits in pi should be greater than (or at least comparable to) the size of the string itself.

e.g., the first instance of "256" in pi starts at the 1750th digit. So in that case you're getting a 'compression' rate of -33% if we go by the count of decimal digits used.

TheZenPsycho• 12 years ago

... and that's the joke.

peteretep• 12 years ago

You should really consider commenting on the project pointing this out to the author; I think he'll be disappointed to know that he hasn't discovered a way to magically compress random data.

That said, I wonder if "but remember all that storage space we saved by moving our data into π? Why don't we store our file locations there!?!" wasn't meant as some kind of hint...

Kapura• 12 years ago

Don't worry, it scales well!

hashmymustache• 12 years ago

To be fair, it compressed my 93 Gb file into 6 bytes. Incidentally, the file stored the first 100 billion decimals of pi.

chacham15• 12 years ago

Nope, sry: "In this implementation, to maximise performance, we consider each individual byte of the file separately, and look it up in π."

EarthLaunch2• 12 years ago

It's obvious that, like many compression algorithms, this one is best suited for certain specific applications such as yours.

vanderZwan• 12 years ago

Ah, the LenPEG approach.

http://www.dangermouse.net/esoteric/lenpeg.html

bmh100• 12 years ago

This is extremely clever and something I have wanted to do for a while. If you are interested in contributing to a fun, small Clojure project, stop by: https://github.com/bmhimes/clojure-pifs

andrewfong• 12 years ago

Reminds me of this SMBC: https://medium.com/the-nib/jesus-is-destroying-civilization-...

TOMDM• 12 years ago

I love pieces of code like this, it appeals to me in the same way sleepsort does. A superficial understanding of it might make you think it would be worth it, but really, while it may work, it's better left as a joke.

zachrose• 12 years ago

Obligatory Dinosaur Comics: http://www.qwantz.com/index.php?comic=353

"You can't copyright a fact (like a number), but you can copyright a creative work, like a song or a piece of software. But since one can be transformed into another, copyright law is logically INCOHERENT."

yzzxy• 12 years ago

Godel's lesser-known Nonliability Theorem has as of yet failed to gain much traction in the MPAA.

pasiaj• 12 years ago

What Colour are your bits?

http://ansuz.sooke.bc.ca/entry/23

infogulch• 12 years ago

Oh! I love this article! Very enlightening. Thanks for reminding me about it!

ithkuil• 12 years ago

Wow, great article!

Does a number that represents a range within Pi, get also coloured as copyrighted if your intent while computing it was the search for a copyright coloured sequence of bits within Pi ?

I think that for a lawyer it doesn't really matter; it doesn't matter which technique you're using to encode your data, as long as somebody can access that content and you did that on purpose. They're good at dealing with loosely defined things like intent, better than with formally defined things.

I wonder what amount (and progress) of AI research has been done in this area; not all illogical things are bullshit, however you might want to feel about them. Anti-digital-rights sentiment (disclaimer: I personally deplore much of the consequences about enforcement of digital rights, so I share that sentiment at many levels) sometimes can cloud judgement, and I've seen many people invoke rational thinking so well they successfully miss the point.

malka• 12 years ago

You cant copyright a number, but you can make it illegal[0].

[0] https://en.wikipedia.org/wiki/Illegal_number

ttflee• 12 years ago

Like other lossless compression algorithms, there always exist some blobs of data, where the length of the location plus metadata exceeds that of the the original blob, due to the pigeon hole principle. The trouble in the case of pi-fad is that probably we will not know whether the location is longer or not before it is ever actually computed.

EarthLaunch2• 12 years ago

Quantum computing will abstract that away so we don't need to know whether the location is longer or not before using it.

skhavari• 12 years ago

Hooli is gonna be pissed when they learn that Pi-ed Piper nailed a compression algorithm.

peterkelly• 12 years ago

Great, now we're going to see a DMCA takedown for π as it contains copyrighted content.

cetu86• 12 years ago

Yeah, and bomb building instructions and child pornography.

tiku• 12 years ago

if you have this large base file with pi-numbers, you could use it to compress data right? and with the current internet speeds, pi-storing in the cloud could be an option. or hell, even distributed pi files :)

soheil• 12 years ago

The location of where the data is is no less complex than the actual data.

serge2k• 12 years ago

They said 100% compression was impossible? You're looking at it!

If the offset within pi is so large that any representation of it is larger than my data?

patio11• 12 years ago

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 algorithms and all sizes. It is flatly impossible to compress all data all of the time.

delinka3• 12 years ago

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

marvy• 12 years ago

Shush. You'll ruin it :)

alixaxel2• 12 years ago

Case and point: http://pi.nersc.gov/cgi-bin/pi.cgi?word=alix&format=char

strlen(alix) < strlen(1188606148)

baddox5• 12 years ago

If you're going to use a normal number for this purpose, why not choose a much nicer one? Let's use a number such that its binary representation is the concatenation of consecutive ascending binary numbers.

    0 1 10 11 100 101 110 111 1000...

becomes

    0.0110111001011101111000...

It's much easier to demonstrate that this number is normal than to do so for pi. It's also much easier to calculate the nth digit, and to find an occurrence of a given string of bits.

mavdi• 12 years ago

Smartest thing I've seen in months, not so much the speed, but the compression value of it is great

fluff3141592653• 12 years ago

I've been looking for the lyrics to the song that, when sung, will bring about peace on this planet. Now to hear that the file containing these lyrics is already contained in pi is revelatory. Could someone please give me the index and length of the file? I've got some singing to do.

fsiefken• 12 years ago

As Dr. Ellie whispers in in Contact; "No words to describe it" and in the Dark Crystal Jen's song is without words.

I think the lyrics are contained in the celestial music itself, and such music is contained in the silence. Silence or 0 is the holy grail of 100% compression, creatio ex nihilo. Perhaps you could find such a song in Pi in a lifelong quest, but it's a much deeper mystery that Pi and 0 are mysteriously related. Euler is rumoured to have remarked it to be proof of God's existence. But even if such proof exists it's of no value compared to it's beauty.

"After proving Euler's identity during a lecture, Benjamin Peirce, a noted American 19th-century philosopher, mathematician, and professor at Harvard University, stated that "it is absolutely paradoxical; we cannot understand it, and we don't know what it means, but we have proved it, and therefore we know it must be the truth." Stanford University mathematics professor Keith Devlin has said, "Like a Shakespearean sonnet that captures the very essence of love, or a painting that brings out the beauty of the human form that is far more than just skin deep, Euler's equation reaches down into the very depths of existence."

http://en.wikipedia.org/wiki/Euler's_identity

andybak• 12 years ago

If anyone here hasn't read The Library of Babel yet, then now is a good time.

Here's a link in case you have trouble locating it within Pi: http://hyperdiscordia.crywalt.com/library_of_babel.html

tluyben2• 12 years ago

Reminds me of Jan Sloot; http://en.wikipedia.org/wiki/Jan_Sloot. It was like an april fools but a lot of big people fell for it at the time.

aaron695• 12 years ago

I'm not sure pi is proven to contain all sequence of digits. Anyone care to link a proof. The joke be on them and they might not really understand pi at all.

pbhjpbhj2• 12 years ago

It isn't proven to be "normal" (http://en.wikipedia.org/wiki/Normal_number). There is no guarantee that any particular sequence is in pi until you've searched and found it. It's a very common fallacy that because the expansion is infinite and non-repeating it should contain every possible sequence, very simple counter examples exist.

Pi can be infinite and non-repeating (as it's irrational) and only sparsely contain 5s after the 100 trillionth digit (or whatever we've calculated it to so far), unlikely.

There are some normal numbers that are known but they seem hard to construct (to me, not a number theorist), like Champernowne's number which is the concatenation of all natural numbers (clearly any number will be in it's expansion by definition but it won't be very good for compression purposes due to the indexing issues highlighted elsewhere).

Some further reading: http://math.stackexchange.com/questions/216343/does-pi-conta..., http://mathoverflow.net/questions/51853/what-is-the-state-of..., http://en.wikipedia.org/wiki/Complexity_function.

colanderman• 12 years ago

If the idea that an infinite, non-repeating pattern might not contain every possible digit seems strange, consider Penrose Tilings [1]. Penrose Tilings are infinite geometric patterns which never repeat, yet clearly don't contain every image known to man.

[1] http://en.wikipedia.org/wiki/Penrose_tiling

bonchibuji• 12 years ago

Isn't this one of the April 1st jokes from 2012? Most of the commits were made on March 31, 2012[1]. And there's even a reference to the pi joke[2].

[1] https://github.com/philipl/pifs/commits/master

[2] http://www.netfunny.com/rhf/jokes/01/Jun/pi.html

nadam3• 12 years ago

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 up until the given time, read the state of the atoms at the specified location, recognize the hard drive, and read the data from it. (Provided that the universe is deterministic, and what seems to be random in quantum mechanics can be simulated with a pseudorandom number generator.)

erikb• 12 years ago

Well, let's assume that the past is constantly changing. The path leading from the start to the universe to the writing of your 4D vector would also change and therefore your vector itself might change automatically with every change to space-time. Or would that still be called deterministic?

damon_c• 12 years ago

Good point. It might be best to use a 5D vector to account for this.

nsajko• 12 years ago

Could yóu explain how/why do you think the past is constantly changing?

kalops• 12 years ago

"the universe is deterministic" - have you developed your thoughts on this since?

nadam3• 12 years ago

Not too much, just one thing: If we could simulate the universe then of course there would be a simulation in the simulation, etc... And maybe there is a fundamental yet undiscovered 'law of computation' that a sufficiently complex simulation can embed itself only on a slower timescale, so even if everything is deterministic, we even theoretically cannot calculate fast enough to calculate the future.

baddox5• 12 years ago

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 is the granularity?), so I don't know if it's likely.

That being said, I would be more concerned by the philosophical and practical consequences of such capability, namely the ability to read hard drives in normally inaccessible locations and hard drives in the future.

nadam3• 12 years ago

" 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 time units:

http://www.wolframalpha.com/input/?i=universe+age+%2F+planck...

So if the simulation is for example something like a cellural automaton with a planck-time (5.4 * 10^(-44) sec) step-size, than assuming we use fix-point numbers, 26 bytes suffice. (25 bytes are just not enough, 256^25 = 1.6 * 10^60)

Suprisingly the size of the universe is 5.4 * 10^61 in planck-length units:

http://www.wolframalpha.com/input/?i=planck+length+universe+...

So again, we need 26 bytes, for a super fine representation. I was one byte off for all components, so we need altogether 104 bytes.

Chinjut2• 12 years ago

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

tragomaskhalos• 12 years ago

If you use base 11 you get the added bonus of proving the existence of god !(http://en.wikipedia.org/wiki/Contact_(novel))

andrey-p• 12 years ago

I prefer the infinite monkey database [1] myself.

[1] https://github.com/brycebaril/infinite-monkey-db

dvanduzer• 12 years ago

has anybody run bonnie++ benchmarks with this fs?

TheAuditor2• 12 years ago

I had played with this idea some time back and gave up after some very specific flaws came became clear.

The good probability that a 5 digit combination is found in Pi will be in the range of locations above 10000, for example I once located by 6 digit phone number in position 685214 which was not actually helpful at all.

Further we are not sure if Pi is normal hence the better idea would be use a simple computable normal series.

It was just yesterday I uploaded a paper that presents a idea for Compressing Random Data to -> https://www.academia.edu/7620004/Advanced_Compression_Techni... which proposes an Idea to push multiple bytes represented by a positions in a computable number series into small representation and generate them on the go when required. (need lot of improvement to actually apply)

cettox• 12 years ago

As many pointed that out using Pidgeon Hole principle, it is not practical to create a compression index(A lookup index where you map actual data with some kind of adresses preferably smaller than sequences), using every possible n byte sequence of your data!

Because your index size would be at least equal or higher than your original data.

The only way you get a smaller compression index, you have to look for recurrences, and try to only include most recurring sequences up to a number(there would be a tradeof and an optimal number for compression ratio) and left other sequences uncompressed. Only this way you can achieve compression ratio's smaller than 100%.

pbhjpbhj2• 12 years ago

I scanned the responses and saw only one that mentioned that pi is not proved (or possibly also provably) normal. That comment was downvoted.

alixaxel2• 12 years ago

This is genius!

Am I right in assuming that the decompression step is several orders of magnitude faster than the compression phase?

EdwardCoffin• 12 years ago

This reminds me of Frederik Pohl's [1] book The Gold at Starbow's End, in which Gödelization [2] is used to compress a huge message into a very short one. There's a brief description of that part of the book at MathFiction [3]

[1] http://en.wikipedia.org/wiki/Frederik_Pohl

[2] http://www.encyclopediaofmath.org/index.php/Gödelization

[3] http://kasmana.people.cofc.edu/MATHFICT/mfview.php?callnumbe...

haddr• 12 years ago

really cool idea, but not sure if actually true: http://math.stackexchange.com/questions/216343/does-pi-conta...

Igglyboo• 12 years ago

His weissman score must be off the charts.

braydenjw• 12 years ago

I'm not sure I understand how this would compress files. I mean, the only way it could is if the decimal place in Pi at which the byte occurs is significantly less than the value of the byte itself. Statistically, this would happen less than 50% of the time, the other 50+% of the time occurring at a higher decimal place. I don't see this providing any real compression benefit.

For example, the byte 0xFF, which is the number 255, first occurs at the 1168th value of Pi.This means instead of storing 255, you're now storing 1168, or 0x490, requiring an extra half-byte. However, 0x328, or number 808, first occurs at the 105th value of pi, or 0x69, requiring one less half-byte.

How does this system provide better compression? The way I see it, the best case scenario would be if no sequence from 000 to 255 was ever repeated in Pi (or rather, not until every pattern in that sequence has been covered), in this case the compression ratio should be exactly 0%, no net gain or loss.

File system that stores location of file in Pi

Related Stories