Am 30.06.15 um 17:40 schrieb Ian Kelly:
On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <aurio...@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
--
https://mail.python.org/mailman/listinfo/python-list
