Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CALwzidkHuWJkqFEDHp6LT2UJxHh6sHZM=2qde0acrSvp12vyRw@mail.gmail.com>
References: <777831f0-d4b4-48f6-ae0b-c9b1ea7ffc06@googlegroups.com> <CALwzidms2BGRjHCuLB5_uszbx9Q-rdtOob_LGHQoO3K3ZD=Q7Q@mail.gmail.com> <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: Tue, 30 Jun 2015 09:45:05 -0600
Subject: Re: Linear time baseconversion
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.190.1435679147.3674.python-list@python.org>
Lines: 34
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93333

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.