Am 30.06.15 um 18:34 schrieb Ian Kelly:
On Tue, Jun 30, 2015 at 10:10 AM, Chris Angelico <ros...@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

--
https://mail.python.org/mailman/listinfo/python-list

Reply via email to