Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #93333
| References | (2 earlier) <mailman.175.1435619500.3674.python-list@python.org> <87r3ouawgt.fsf@bsb.me.uk> <7c6dac9d-5722-4179-bd7e-ceaac6698490@googlegroups.com> <mmtm6k$8b7$1@dont-email.me> <CALwzidkHuWJkqFEDHp6LT2UJxHh6sHZM=2qde0acrSvp12vyRw@mail.gmail.com> |
|---|---|
| From | Ian Kelly <ian.g.kelly@gmail.com> |
| Date | 2015-06-30 09:45 -0600 |
| Subject | Re: Linear time baseconversion |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.190.1435679147.3674.python-list@python.org> (permalink) |
On Tue, Jun 30, 2015 at 9:40 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
>> Am 30.06.15 um 10:52 schrieb jonas.thornvall@gmail.com:
>>>
>>> It still bug out on very big numbers if base outside integer scope.
>>> I am very keen on suggestions regarding the logic to make it faster.
>>
>>
>> Concerning the algorithmic complexity, it can't be faster than square time
>> in the number of digits N. Baseconversion needs to do a sequence of division
>> operations, where every operation gves you one digit in the new base. The
>> number of digits in the new base is proportional to the number of digits in
>> the old base (the ratio is log b1/log b2). Therefore it will be O(N^2).
>
> I don't think that's true. Here's a linear hexadecimal to binary function:
>
>>>> def hextobin(value):
> ... digits = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
> ... '4': '0100', '5': '0101', '6': '0110', '7': '0111',
> ... '8': '1000', '9': '1001', 'A': '1010', 'B': '1011',
> ... 'C': '1100', 'D': '1101', 'E': '1110', 'F': '1111'}
> ... return ''.join(digits[d.upper()] for d in value)
> ...
>>>> hextobin('3f')
> '00111111'
>
> I believe this approach can be extended to arbitrary bases with some
> effort, although for converting arbitrary base b1 to b2, you would
> need up to b2 different mappings if b1 and b2 are relatively prime.
Actually, I think you need up to b1 * b2 mappings, as you're
effectively building a state machine with b1 * b2 states. The mappings
can be pre-computed, however, so actually running the state machine
would then just be a linear algorithm.
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 15:39 -0700
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 16:56 -0600
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 17:10 -0600
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 16:23 -0700
Re: Linear time baseconversion Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-06-30 01:09 +0100
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 01:52 -0700
Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-06-30 11:07 +0200
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:20 -0700
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:34 -0700
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:43 -0700
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 06:22 -0700
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 07:13 -0700
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:29 -0600
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:45 -0600
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:40 -0600
Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:22 +0200
Re: Linear time baseconversion Chris Angelico <rosuav@gmail.com> - 2015-07-01 02:10 +1000
Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 10:34 -0600
Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:27 +0200
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 23:49 -0700
Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 10:12 -0600
Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 09:24 -0700
Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 13:55 -0600
csiph-web