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