Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1697

Re: Question about compression with conditions

Show all headers | View raw

John Reiser <jreiserfl@comcast.net> wrote:
>>> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
>>> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
>>> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
>>> of the 1024 bits.
 
>> Is it really that small?
 
> #include <math.h>
> #include <stdio.h>
 
> double lf[1025];
 
> int
> main(int argc, char *argv[])
> {
>        int j;
>        for (j=1; j < 1025; ++j)
>                lf[j] = log(j) + lf[-1+ j];
>        double t;
>        for (t=0.0, j=522; j<=532; ++j)
>                t += exp(lf[1024] - lf[j] - lf[1024 - j]);
>        double const two_1024 = exp(1024*log(2));
>        printf("        t = %g\n"
>               "  2**1024 = %g\n"
>               "t/2**1024 = %g\n",
>                t, two_1024, t / two_1024);
>        printf("  savings = %g bits\n", - log2(t / two_1024));
>        return 0;
> }
 
>        t = 3.16949e+307
>  2**1024 = 1.79769e+308
> t/2**1024 = 0.176309
>  savings = 2.50382 bits

So, 1024 bits goes down to 1021. Sometimes that might be worthwhile,
but most of the time not.

That is about what I was going to guess.

-- glen

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 11:41 +0100
  Re: Question about compression with conditions John Reiser <jreiserfl@comcast.net> - 2013-01-19 07:10 -0800
    Re: Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 19:08 +0100
    Re: Question about compression with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-01-19 18:59 +0000
      Re: Question about compression with conditions John Reiser <jreiserfl@comcast.net> - 2013-01-19 13:15 -0800
        Re: Question about compression with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-01-19 22:41 +0000
      Re: Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 23:23 +0100

csiph-web