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.

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

> As [Martin] Gardner tells the tale, on visiting Earth, an inquisitive alien wishes to collect all of human knowledge. Having no room for the Encyclopedia Britannica aboard an already-cramped spaceship (and lacking a CD-ROM player), the alien proposes a clever method for compressing the Encyclopedia's volumes. Assuming there are fewer than 1000 unique letters, digits, and other symbols in the text, our resourceful visitor assigns each symbol a three-digit code from 000 to 999, including leading 0s. The word "Snow," for example, might be encoded as 083110111119. Translating the entire Encyclopedia this way produces a giant integer that, with an imaginary decimal point to the left, is equivalent to the decimal fraction, A/B. To complete the data compression, the visitor places a mark on a small rod of otherworldly material that divides the bar into two lengths, A and B.

> After returning to Zenon (or wherever), the alien precisely measures the marked rod, obtains lengths A and B, and divides A/B to yield the original integer, which a computer decodes to print out the Encyclopedia.

- Dr Dobb's