Path: csiph.com!usenet.pasdenom.info!gegeweb.org!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 19 Feb 2015 13:24:40 -0500
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: python implementation of a new integer encoding algorithm.
References: <e45a71b2-7ec0-4c7d-88ae-c48aebe154b7@googlegroups.com> <mailman.18784.1424182393.18130.python-list@python.org> <515047c1-a20d-430e-a029-1c2d77db2f1a@googlegroups.com> <mailman.18823.1424278025.18130.python-list@python.org> <2a717ffb-d61d-4407-9082-1c17cd7ee573@googlegroups.com> <mailman.18839.1424298000.18130.python-list@python.org> <993f64c3-fc85-48a7-9d02-a4f12ecb33c6@googlegroups.com>
In-Reply-To: <993f64c3-fc85-48a7-9d02-a4f12ecb33c6@googlegroups.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.18894.1424370292.18130.python-list@python.org>
Lines: 107
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:85918

On 02/19/2015 10:45 AM, janhein.vanderburg@gmail.com wrote:
> On Wednesday, February 18, 2015 at 11:20:12 PM UTC+1, Dave Angel wrote:
>> I'm not necessarily doubting it, just challenging you to provide a data
>> sample that actually shows it.  And of course, I'm not claiming that
>> 7bit is in any way optimal.  You cannot define optimal without first
>> defining the distribution.
>
> Weird results.

In what way weird?

> For a character size 2 the growth processes are shown below.
> I listed the decimal representations, the difficult representation, a stop bit encoding, and the number of characters they differ in length:
> 0:  00				00				0
> 1:  01				01				0
> 2:  10, 00			10, 00				0
> 3:  10, 01			10, 01				0
> 4:  10, 10			11, 00				0
> 5:  10, 11			11, 01				0
> 6:  11, 00.00			11, 10, 00			0
> 7:  11, 00.01			11, 10, 01			0
> 8:  11, 00.10			11, 11, 00			0
> 9:  11, 00.11			11, 11, 01			0
> 10: 11, 01.00			11, 11, 10, 00			1
> 11: 11, 01.01			11, 11, 10, 01			1
> 12: 11, 01.10			11, 11, 11, 00			1
> 13: 11, 01.11			11, 11, 11, 01			1
> 14: 11, 10.00, 00		11, 11, 11, 10, 00		1
> 15: 11, 10.00, 01		11, 11, 11, 10, 01		1
> 16: 11, 10.00, 10		11, 11, 11, 11, 00		1
> 17: 11, 10.00, 11		11, 11, 11, 11, 01		1
> 18: 11, 10.01, 00.00		11, 11, 11, 11, 10, 00		1
> 19: 11, 10.01, 00.01		11, 11, 11, 11, 10, 01		1
> 20: 11, 10.01, 00.10		11, 11, 11, 11, 11, 00		1
> 21: 11, 10.01, 00.11		11, 11, 11, 11, 11, 01		1
> 22: 11, 10.01, 01.00		11, 11, 11, 11, 11, 10, 00	2
> 23: 11, 10.01, 01.01		11, 11, 11, 11, 11, 10, 01	2
> 24: 11, 10.01, 01.10		11, 11, 11, 11, 11, 11, 00	2
> 25: 11, 10.01, 01.11		11, 11, 11, 11, 11, 11, 01	2
> 26: 11, 10.01, 10.00		11, 11, 11, 11, 11, 11, 10, 00	3
>
> I didn't take the time to prove it mathematically, but these results suggest to me that the complicated encoding beats the stop bit encoding.
>

Clearly, one wouldn't use what you call "stop bit encoding" with a 2bit 
character.  And since the Python code you posted uses an 8bit character, 
I can't validate the "difficult" column either.

I wrote the following pair of functions:

def seven_code(n):
     acc = bytearray()
     if n == 0:
         acc.append(0)
     while n > 0:
         quotient, remainder = divmod(n, 128)
         acc.append(remainder)
         n = quotient
     acc[-1] |= 0x80            #add a stop bit to last byte
     return acc

def seven_decode(sequ):
     acc = 0
     multiplier = 1
     for by in sequ:
         acc += (by & 0x7f) * multiplier
         if by > 0x7f:
             break
         multiplier *= 128
     return acc

Here's a couple of ranges of output, showing that the 7bit scheme does 
better for values between 384 and 16379.

382 2 80fe --- 2 7e82
383 2 80ff --- 2 7f82
384 3 810000 --- 2 0083
384  jan grew 3 810000
385 3 810001 --- 2 0183
386 3 810002 --- 2 0283
387 3 810003 --- 2 0383
388 3 810004 --- 2 0483
389 3 810005 --- 2 0583

16380 3 813e7c --- 2 7cff
16380  jan grew 3 813e7c
16380 7bit grew 2 7cff
16381 3 813e7d --- 2 7dff
16382 3 813e7e --- 2 7eff
16383 3 813e7f --- 2 7fff
16384 3 813e80 --- 3 000081
16384 7bit grew 3 000081
16385 3 813e81 --- 3 010081
16386 3 813e82 --- 3 020081
16387 3 813e83 --- 3 030081
16388 3 813e84 --- 3 040081
16389 3 813e85 --- 3 050081

In all my experimenting, I haven't found any values where the 7bit 
scheme does worse.  It seems likely that for extremely large integers, 
it will, but if those are to be the intended distribution, the 7bit 
scheme could be replaced by something else, like just encoding a length 
at the beginning, and using raw bytes after that.


--
DaveA