greg@garnet.berkeley.edu (Greg Kuperberg) (04/11/91)
In article <4931@pink1.UUCP> beville@motcid.UUCP (Anthony T. Beville) writes: >It seems to me that a scheme using the the digits of >and irrational number ( or a repeating rational number, for that >matter) might be able to yeild some really good compression >ratios. > >For any given sequence of bits longer than some number, >merely (!) find a matching sequence deep within the bowels >of pi or sqrt(2) or some fraction or whatever, and represent >that sequence with a greatly reduced number of bits. (I'm not sure if this is a serious proposal, but I'll err on the side of courtesy and assume that it is.) This the kind of algorithm can't possibly work, because it assumes nothing about the input stream. A data compression scheme which shortens some data streams must necessarily lengthen others (if only by a small amount). Some data compression algorithms, like Lempel-Ziv, are called "universal", as if to suggest that they assume nothing about the input stream. This is not the case. Lempel-Ziv only shortens messages with a bias in the distribution of bits or strings of bits. It is universal in the sense that it makes no prior assumption about what that bias is, only that it exists. The catch in this particular case is that most sequences of bits occur so far down in the expansion of pi or sqrt(2) that you will need at least as many bits as you started with to describe their locations. ---- Greg Kuperberg greg@math.berkeley.edu
weverka@spot.Colorado.EDU (Robert T. Weverka) (04/11/91)
In article <1991Apr10.193417.28193@agate.berkeley.edu> greg@math.berkeley.edu writes: >In article <4931@pink1.UUCP> beville@motcid.UUCP (Anthony T. Beville) writes: >>It seems to me that a scheme using the the digits of >>and irrational number ( or a repeating rational number, for that >>matter) might be able to yeild some really good compression >>ratios. >> >>For any given sequence of bits longer than some number, >>merely (!) find a matching sequence deep within the bowels >>of pi or sqrt(2) or some fraction or whatever, and represent >>that sequence with a greatly reduced number of bits. >The catch in this particular case is that most sequences of bits >occur so far down in the expansion of pi or sqrt(2) that you will need >at least as many bits as you started with to describe their locations. >---- >Greg Kuperberg >greg@math.berkeley.edu A sloppy proof to that effect (but simple) suppose we want to compress a ten digit number (decimal) the chance of matching the first digit to a digit in the pi sequence is 0.1 the chance of matching the first two digits to two digits in the pi seq. is 0.01 the chance of matching all ten is 10^-10. so the description of where the ten digit sequence occurs in the sequence of pi digits is a number of size 10^10 and to store this we need 10 digits. ---> no compression QED BFD .
slandrum@ntg.uucp (Stephen Landrum) (04/13/91)
In article <1991Apr11.044640.20930@colorado.edu> weverka@spot.Colorado.EDU (Robert T. Weverka) writes: >In article <1991Apr10.193417.28193@agate.berkeley.edu> greg@math.berkeley.edu writes: >A sloppy proof to that effect (but simple) >suppose we want to compress a ten digit number (decimal) >the chance of matching the first digit to a digit in the pi sequence is 0.1 >the chance of matching the first two digits to two digits in the pi seq. is 0.01 >the chance of matching all ten is 10^-10. > so the description of where the ten digit sequence occurs in the sequence >of pi digits is a number of size 10^10 and to store this we need 10 digits. > ---> no compression QED BFD . Actually the problem is worse. There is ~1/e probability that the 10 digit sequence you are looking for does NOT occur in the first 10^10 digits. You may need more than 10 digits to store the location of your number in PI. -- Stephen H. Landrum VOICE: (415) 813-8909 UUCP: ...apple!ntg!slandrum USNAIL: New Technologies Group Inc. 2468 Embarcardero Way, Palo Alto CA 94303