Hacker News Reader

Comment by krastanov | Hacker News Reader

I imagine the BigInt index that points to the starting digit for your data would take more space than the data itself. Here is an example in julia:

    julia> setprecision(BigFloat, 10_000) do 
               findfirst("123","$(BigFloat(pi)))")
           end
    1926:1928

I.e. the string "123" starts at index 1926.

On the other hand, this type of "encoding" always fun to think about. I would suggest reading "Permutation City" by Greg Egan if you are amused by this.

View on HN

> I imagine the BigInt index that points to the starting digit for your data would take more space than the data itself

Assuming optimal conditions (i.e. optimal randomness), you can expect that as many pieces of data will have pointers smaller than them, as pointers bigger than them; you can't win that way necessarily, only in some cases.

But maybe if you can find two 'opposite' algorithms, such that for any data where the pointer is larger with the first, it's smaller in the second...

(From what I know of information theory, the extra bit you have to use to specify which algorithm to use will outweigh all savings, but it's still fun to think about.)

I doubt that... You are comparing a random variable (the size of the data) to a sum of random variables (the index of the data). Thus I would expect the index to be greater than the size... But I am fairly uncertain.

Assuming optimal randomness, the shortest program to output the data will be in the random source. So record the random source, try all programs shorter than the data, and note the timestamp when you've found the optimal compression.

I have not heard of this book, but these things do interest me...I'll check it out; I've been looking for a new book to read.

Reply on news.ycombinator.com