From: madler@cco.caltech.edu (Mark Adler)
Newsgroups: alt.folklore.computers,sci.math,comp.compression
Subject: Re: Compressing decimal expansion of pi (was Re: PI)
Date: 27 Dec 1992 22:42:15 GMT
Organization: California Institute of Technology, Pasadena
NNTP-Posting-Host: sandman.caltech.edu


Magnus (three-jet) Olsson continues to wonder:

>> given the first million digits of pi, how well can we expect a
>> *general-purpose* compression algorithm to compress it? 

Do you mean a general purpose text compression program, or a general
purpose decimal compression program?

For text compression, most such programs use Huffman coding of some
sort, and I expect Huffman coding of bytes to give 3.5 bits per digit.
The reality is that programs like zip give about 3.76 bits per byte.
The 3.5 comes from coding five digits as three bits, and the other five
as four bits, leaving one code extension for end-of-block or other
uses.

For decimal compression, I expect close to the log-base-2 of 10 bits
per digit, which is 3.321928 bits per byte.  I posted a simple
compressor and decompressor that approaches that with 3.325667 bits per
byte.

You can achieve nearly exactly log-base-2 of 10 bits per digit by
converting pi to binary (or not converting it to decimal) for
distribution.  However, you then have a rather long decompression time,
and would require rather a lot of memory.

There is a large trade-off space between my program, which converts
three digit groups to binary, and converting all one-million digits to
binary.  As you increase the number of digits converted, you get closer
to the ideal, though it converges slowly.

For a program like the one I wrote, I can generalize the compression
ratio as a function of n, the number of decimal digits converted to
binary in each step.  Let m be the number of bits needed to represent
an n-digit decimal number, that is the ceiling of n times the
log-base-2 of 10.  Then, the compression ratio is (assuming one code
leftover):

     (m + 1 - (2^m - 1)/10^n) / n

in bits per digit.  The values of n where the ratio goes down are not
common, and are listed below up to n = 100,000:

     1: 3.500000000000000
     2: 3.365000000000000
     3: 3.325666666666667
     6: 3.325237500000000
     9: 3.325139797444444
    12: 3.325040697685417
    15: 3.324940006210492
    16: 3.324910009315738
    18: 3.324837694188508
    19: 3.323964504875213
    22: 3.323229700311461
    25: 3.322628747544664
    28: 3.322117712040836
    56: 3.322114387637351
    59: 3.321960402073528
   118: 3.321960242723494
   146: 3.321932061149300
   292: 3.321932053734470
   351: 3.321930919049451
   497: 3.321929165771849
   643: 3.321928207007562
  1286: 3.321928206986929
  1929: 3.321928206966293
  2572: 3.321928206945655
  2718: 3.321928174691855
  3361: 3.321928132446014
  4004: 3.321928103755393
  8008: 3.321928103754379
  8651: 3.321928096700861
 12655: 3.321928096132708
 21306: 3.321928095036133
 42612: 3.321928095036133
 55267: 3.321928095028128
 76573: 3.321928094936851
 97879: 3.321928094888992

This sequence in the limit goes to log-base-2 of 10, which is:

        3.321928094887362

The price for larger n is having to do a 2^m bit arithmetic operation
for each digit.

Particularily good values to use are n=3 for 16-bit machines, n=9 for
32-bit machines, and n=19 for 64-bit machines.  For a random one
million digit number, n=3 would compress to 415709 bytes, n=9 would
give 415643 bytes (66 bytes less than n=3), and n=19 would give 415496
bytes (213 bytes less than n=3).  Total binary conversion would
compress to 415242 bytes (467 bytes less than n=3).

So have we beaten this issue to death yet?

mark
Newsgroups: alt.folklore.computers