Linear time baseconversion

[jonas.thornvall at gmail.com]

Den tisdag 30 juni 2015 kl. 11:35:06 UTC+2 skrev jonas.t... at gmail.com:
> 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

Well that averaging was balloney. How do i write that the digit will be found in.
Average values from 1 to SQRT(base)?