Linear time baseconversion

[Ian Kelly]

On Tue, Jun 30, 2015 at 9:40 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <auriocus at gmx.de> wrote:
>> Am 30.06.15 um 10:52 schrieb jonas.thornvall at 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.