Linear time baseconversion

Christian Gollwitzer auriocus at gmx.de
Tue Jun 30 18:22:01 EDT 2015


Am 30.06.15 um 17:40 schrieb Ian Kelly:
> On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <auriocus at gmx.de> wrote:
>> 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.
>

OK. Show it for bases 2 and 3. It will just be a table of 6 entries, no?

Actually, you showed a very special case, for conversion from base b^4 
to base b. I'm pretty convinced it is not possible for the general case.

	Christian




More information about the Python-list mailing list