Linear time baseconversion

[Christian Gollwitzer]

Am 30.06.15 um 18:34 schrieb Ian Kelly:
> On Tue, Jun 30, 2015 at 10:10 AM, Chris Angelico <rosuav at gmail.com> wrote:
>> When there's a simple ratio between the bases, it's fairly
>> straight-forward to convert a few digits at a time. Converting base
>> 256 into base 64, for instance, can be done by taking three digits and
>> yielding four. But within that, you would still need a complete table
>> of all sixteen million possibilities, if you want to do the lookup
>> table. And that only works when there is that kind of relationship.
>
> You're right. I was thinking that for base 5 to base 7, for instance,
> one could read digits in groups of 7, but that doesn't work out; you
> can't map any discrete number of base 5 digits to a corresponding
> number of base 7 digits.

Yes, because there is no n for which 5^n=7^n (except n=0). This gives 
more-or-less the proof that the algorithm must be O(N^2) - at least that 
is my feeling. Fun fact, though: you can convert pi to hexadeicmal base 
without computing the preceding digits:

https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula

	Christian