Time complexity of base conversion

Question

Why can't arbitrary base conversion be as fast as converting from base $b$ to base $b^k$ ?

Seems to be a big time complexity difference! I am also interested in reading material about it.

---

Old. Original detailed question

Conversion between power-2-radix can be done faster than between non-power-of-2 radix, they can be even done in parallel, as every digit (or some groups of them) can be decoded independently of the rest.

For example the binary number 00101001 can be converted to hexadecimal 0x29 nibble by nibble (0010 and 1001), and vice versa (i.e. every hex-digit can be parsed to 4 bits independently of the rest), but doing that conversion from decimal (or any other non-power-of-2 radix) to binary, it's not so easy because digits affects each other!.

I've seen time complexity of maths operations in wikipedia, and there is also a related question in stackoverflow saying time complexity of conversions of arbitrary digit length to be $\mathcal{O}(M(n) log(n))$

I'm not interested in a "general time complexity bounds for any base conversion" but I would like to know more about these big differences in time complexity between "power-of-2 conversions" vs "any other base conversions".

I think there is a general fact about conversions that can be done faster if they are done between numbers where its bases are power among themselves, not only for 2, but the same to a base 10 to base 100.

Is there any known proof or materials around this ?

Answer 1

Conversion from base $b^k$ to base $b^l$ can be done by reading the original number in chunks of length $\mathrm{lcm}(k,l)/k$, and converting each such chunk into $\mathrm{lcm}(l,k)/l$ digits in the new base. For fixed $b,k,l$, this is linear time.

There is a non-trivial algorithm for base conversion in time $O(M(n)\log n)$, where $M(n)$ is the time it takes to multiply two $n$-bit numbers, $n$ is the length of the number (in digits), and the two bases are fixed. See for example page 14 of these notes by Brent.

The question you are asking is, for fixed $b_1,b_2$ which cannot be written in the form $b^k,b^l$, whether there exists a linear time algorithm for converting from base $b_1$ to base $b_2$. One possible approach to show that this is impossible might be by reducing multiplication (or any other equivalent operation, such as division) to base conversion for some fixed constant bases -- but it's not clear if it is in fact possible to build such a reduction or not. I don't believe the question has been asked in the literature.

Answer 2

You seem to have asked 2 questions:

1. Why is it that for some pairs of bases, there is no linear time algorithm for converting from one base in that pair to the other?
2. How to you compare converting between any two bases to converting to and from base 2?

I'm afraid I don't know how to answer the first question because I don't know how to prove that for some pairs of bases, there is no linear time algorithm for converting from one to the other, but I'm pretty sure that for any two bases that are not a power of the same number, there is no linear time algorithm for converting from one to the other.

However, I will answer the second question because nobody else seems to have. Converting between any two bases is provably no harder than converting between any base and base 2. That's easy to prove because for any two bases, converting from one to the other can be done by converting from one base to base 2 and then from base 2 to the other base. It probably does not go the other way. Converting between one base and another base is probably sometimes easier than converting from some base to base 2. For example, converting from base 3 to base 9 is a linear time problem but converting from base 3 to base 2 probably isn't.

Answer 3

To make a conversion of a natural number

Representation $A$ in base $r_a$ with $n$ digits $a_{n-1}a_{n-2}...a_0$ , $A=\sum\limits_{k=0}^{n-1} a_k{r_a}^k$

Representation $B$ in base $r_b$ with $m$ digits $b_{m-1}b_{m-2}...b_0$ , $B=\sum\limits_{k=0}^{m-1}b_k{r_b}^k$

As they are the same number, $A$=$B$ then $A-B=0$

$\sum\limits_{k=0}^{n-1}a_k{r_a}^k - \sum\limits_{k=0}^{m-1}b_k{r_b}^k = 0$

Representations can be forced to be the same length by filling with zeros the shorter. $n=m$, so

---

$\sum\limits_{k=0}^{n-1}a_k{r_a}^k - b_k{r_b}^k = 0$

Equation 1

$a_k = b_k(\frac{r_b}{r_a})^k$

---

That's not a method for solving the conversion but complexity of base conversion is related to solving that equation, where either $a_k$ or $b_k$ are the unknown variables (depending on what base conversion we are doing).

On the other hand, in the case of power related bases $r_b={r_a}^c \implies {r_b}^k={{r_a}^c}^k$ so the equation get simpler, taking out ${r_a}^k$ as common factor

$\sum\limits_{k=0}^{n-1} (a_k- b_k{r_a}^c){r_a}^k = 0$

So for it to be zero

---

$a_k=b_k{r_a}^c$

name the constant $Q={r_a}^c$

Equation 2

$a_k=b_k{Q}$

Solving $a_k$ or $b_k$ is just a product to, or a division by, a constant factor Q for every k.

So comparing $(1)$ with $(2)$ this second one is clearly simpler.

To speed up $(1)$ there are some techniques by the moment I've found The Horner Method that reduce operations in solving polynomials.

This what I've found by now to answer my own question..