Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #85918
| Date | 2015-02-19 13:24 -0500 |
|---|---|
| From | Dave Angel <davea@davea.name> |
| Subject | Re: python implementation of a new integer encoding algorithm. |
| References | (2 earlier) <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> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.18894.1424370292.18130.python-list@python.org> (permalink) |
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
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-17 03:22 -0800
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 00:16 +1100
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 00:55 -0800
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 20:36 +1100
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:29 -0800
Re: python implementation of a new integer encoding algorithm. Laura Creighton <lac@openend.se> - 2015-02-18 11:32 +0100
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:48 -0800
People hated it for the same reasons I found them cool (was: python implementation of a new integer encoding algorithm.) Ben Finney <ben+python@benfinney.id.au> - 2015-02-18 21:57 +1100
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 09:12 -0500
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 00:59 -0800
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 11:46 -0500
Re: python implementation of a new integer encoding algorithm. Grant Edwards <invalid@invalid.invalid> - 2015-02-18 17:30 +0000
Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-18 18:12 +0000
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:55 -0800
Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-18 23:54 +0200
Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 00:08 +0200
Re: python implementation of a new integer encoding algorithm. Grant Edwards <invalid@invalid.invalid> - 2015-02-18 22:58 +0000
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 17:19 -0500
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-19 07:45 -0800
Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:04 -0700
Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:16 -0700
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:24 -0500
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-20 05:34 +1100
Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:32 -0700
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:41 -0500
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:46 -0500
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-20 05:49 +1100
Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-18 17:00 +0000
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 01:34 +1100
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 01:04 -0800
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 08:54 -0500
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:52 -0800
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-19 01:16 +1100
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 09:50 -0500
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 01:58 +1100
Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 10:18 -0500
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 02:25 +1100
Re: python implementation of a new integer encoding algorithm. Paul Rubin <no.email@nospam.invalid> - 2015-02-17 08:43 -0800
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 01:06 -0800
Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 08:44 +0100
Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 08:06 +0000
Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 10:36 +0200
Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 09:33 +0000
Re: python implementation of a new integer encoding algorithm. Terry Reedy <tjreedy@udel.edu> - 2015-02-19 14:50 -0500
Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 21:55 +0200
Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-19 19:36 +1100
Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 10:42 +0100
Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 10:28 +0000
Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 14:27 +0100
Re: python implementation of a new integer encoding algorithm. Jonas Wielicki <jonas@wielicki.name> - 2015-02-19 09:38 +0100
Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-19 07:58 -0800
Re: python implementation of a new integer encoding algorithm. Denis McMahon <denismfmcmahon@gmail.com> - 2015-02-20 02:46 +0000
Re: python implementation of a new integer encoding algorithm. wxjmfauth@gmail.com - 2015-02-20 00:58 -0800
csiph-web