6
$\begingroup$

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 ?

$\endgroup$
  • 4
    $\begingroup$ When the two bases are powers of the same integer, there is a trivial algorithm that converts between the two bases. So the question is really, why do we think that in general base conversion cannot be done in linear time. One explanation would be to reduce multiplication to base conversion. I don't know if anyone ever tried that. $\endgroup$ – Yuval Filmus Feb 17 '14 at 19:20
  • 4
    $\begingroup$ I can't quite tell what your question is. What is your exact question? This is not a discussion forum, and it's not the right site if you are looking for "discussion about topic X" or "I would like to know more about topic X". Can you formulate a precise, technical question? $\endgroup$ – D.W. Feb 17 '14 at 23:55
  • 1
    $\begingroup$ @D.W. I give one possible interpretation of the question: is it necessarily the case that general base conversion is not linear time? This can be shown (conditionally, of course), for example, by reducing multiplication to base conversion. This might be easy, and a reduction in the other direction (losing a logarithmic factor) is already known. $\endgroup$ – Yuval Filmus Feb 18 '14 at 0:17
  • $\begingroup$ @D.W. There is no intention of discussing this, I explained why I see conversion faster for power-related-bases, then the question: Is this a well known fact? Does this have a name?(a name would suffice), and you can answer more, Is there any proof about this? What are the restriction ? Is there a more general approach behind this behaviour? Why being different bases "merely representation of numbers" there is time complexity separation appearing among them? and so on, just one of those answer is enough because I am clearly searching for some help with any reference material over this topic. $\endgroup$ – Hernan_eche Feb 18 '14 at 3:40
  • 1
    $\begingroup$ @Hernan_eche, that's 6 questions, which is approximately 5 too many for a single question. Moreover, almost none of that appears in the question itself. Don't stop at posting comments here; edit the question to make it a narrowly focused, well-posed technical question. $\endgroup$ – D.W. Feb 18 '14 at 6:52
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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..

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.