More on barcode bandwidth (fwd)

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Sat Sep 13 2003 - 23:40:08 CDT

|iii) PickNofM - requires N * log2(M+1) bits where M is number of
|choices and N is number to pick

Actually, we can often get by with less than this. Specifically, M bits
suffices to encode the votes under the assumption the software enforces
selection of the right number of votes (which it will). Incidentally, I
think most "PickNofM" votes will actually be "PickUpToNofM".

Each of the M bits will simply be a Yes/No on a particular candidate
under this approach. Which approach is better depends on M and N. For
example, if you want to pick 5 officials out of 10 candidates:

>>> 5 * log(10,2)
    16.609640474436812

Which is more than 10 bits. However, picking 2 out of 100:

>>> 2 * log(100,2)
    13.287712379549451

...looks a lot better than 100 bits.

--
mertz@  | The specter of free information is haunting the `Net!  All the
gnosis  | powers of IP- and crypto-tyranny have entered into an unholy
.cx     | alliance...ideas have nothing to lose but their chains.  Unite
        | against "intellectual property" and anti-privacy regimes!
-------------------------------------------------------------------------
==================================================================
= The content of this message, with the exception of any external 
= quotations under fair use, are released to the Public Domain    
==================================================================
Received on Tue Sep 30 23:17:05 2003

This archive was generated by hypermail 2.1.8 : Tue Sep 30 2003 - 23:17:09 CDT