Re: Is this a legitimate compression scheme?


dougwedel@xxxxxxxxxxxxx wrote:
A previous discussion in here has left me with this boiled-down question:

Suppose my computer contains in its memory the first 10 billion digits of
pi. Now suppose you generate a 10-digit random number and give it to me.
My computer program will compare your random number to its 10 billion digits
to see if at any point your 10-digit string exactly matches a 10-digit
stretch of pi. If the program finds a match, it returns the index into pi
(i.e. the Nth digit of pi) where your 10-digit string starts. If this index
has nine or fewer digits, would you agree that this is a legitimate
"compression" of your 10-digit number as the term "compression" is used in
algorithmic complexity or algorithmic information theory?

No, that would not be a legitimate "compression", since you would
typically need a little more space to describe your index into pi than
you needed to encode your number in the first place.

.

Relevant Pages

  • Re: ADIZ Violation Explained in AOPA Magazine
    ... Jose wrote: ... demand this number even though they have no legitimate ... Most of the rest of the digits can be reconstructed by anybody who knows how the system is set up. ... Make the number tie to something that only you can provide. ...
    (rec.aviation.piloting)
  • Re: Cantor
    ... That's not a shorthand for a converging limiting expression. ... > and have IT accepted as a legitimate number. ... it makes sure that digits don't get any more value just because ...
    (sci.math)
  • Is this a legitimate compression scheme?
    ... My computer program will compare your random number to its 10 billion digits ... to see if at any point your 10-digit string exactly matches a 10-digit ... algorithmic complexity or algorithmic information theory? ...
    (sci.math)
  • Re: Developing a focused set of questions for IDists - Comments encouraged
    ... and mathematical processes, and whether its digits actually _are_ random ... or just _appear_ random is actually a legitimate and open question? ...
    (talk.origins)
  • Re: ADIZ Violation Explained in AOPA Magazine
    ... demand this number even though they have no legitimate ... reasons to know it. ... the rest of the digits can be reconstructed by anybody who knows how the system is set up. ...
    (rec.aviation.piloting)