From: David Mertz <voting-project_at_gnosis_dot_cx>

Date: Mon May 03 2004 - 12:16:08 CDT

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
*