# Re: Fwd: Compression, encoding, entropy

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Mon May 03 2004 - 12:16:08 CDT

> On May 3, 2004, at 4:57 AM, Arthur Keller wrote:
>> I'm not a python programmer, so I can't. But the formula is:
>
> Arthur: Does this look right to you? If so, I'll post the source code.
> But if not, I must have made a programming error in implementing your
> formulas:
> Vote Space Optimal Self-Delim
> ---------- ------- ----------
> 3 2 3
> 3 2 3
> 176 8 15
> 109601 17 37

As I stared at it, it started to look wrong that it should take so many
bits to self-delimit contests. So I figured I did something wrong.
Naturally, I did. However, looking at the formulae again, I think they
must be wrong too:

> Let n be the highest number being encoded [DQM: "Vote Space"]
> Let d be the number of bits in a digit
> Let b be the base (2**n)
> Let m be one-half of the base
> The number of digits, g = floor (log_m(n) +1)
> The number of bits is d*g
> The efficiency in encoding compared with straight binary is:
> (d*g)/floor(lg(n)+1)

The term 'g' very quickly converges to 1, i.e. for n >= 3.

Assuming you mean 'b' by "the base", m is larger than n for almost all
n's. And therefore log_m(n) is always less than one (for n>2). And
therefore g is exactly equal to one.

Since d is constant, d*g is also constant. Which would mean that every
contest gets encoded in the same number of bits. And at that point I
start to think something's wrong. :-)

Yours, David...
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Mon May 31 23:17:04 2004

This archive was generated by hypermail 2.1.8 : Mon May 31 2004 - 23:18:15 CDT