Linear time baseconversion
jonas.thornvall at gmail.com
jonas.thornvall at gmail.com
Tue Jun 30 05:34:56 EDT 2015
Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> 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
Any new digit will be found in SQRT(base) comparissons.
Averaged case will be in (SQRT(base)*(SQRT(base)+1))/2
More information about the Python-list
mailing list