Linear time baseconversion
Christian Gollwitzer
auriocus at gmx.de
Tue Jun 30 05:07:50 EDT 2015
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).
Christian
More information about the Python-list
mailing list