1
$\begingroup$

Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$. The obvious algorithm is: interpret $P$ to obtain $n$, then calculate $Q$ from $n$. This is easy.

But if $n$ is very large this could require a lot of memory, and it could require a large amount of processing before any of the digits of $Q$ are emitted. In certain special cases we can do better; there is an online algorithm which can start producing output before all the input is read. For example, if $p^i = q^j$ then the algorithm can read $i$ digits of $P$ and immediately produce $j$ digits of $Q$ without any further input and with only a constant amount of memory. This method is used, for example, in converting generic computer data ($p=256$) to “Base64” format ($q=64$).

Is there a general online algorithm for radix conversion? I expect that if there is such an algorithm, in the worst case it cannot emit any digits of $Q$ without first reading all of $P$, but are there algorithms that can often do better than this, in cases more general than the very unusual $p^i=q^j$ situation? Or are there any other special cases of interest?

[ Related thread: The math behind converting from any base to any base without going through base 10? but all of the suggestions there ingest the entire input before producing any output. ]

$\endgroup$
  • $\begingroup$ There seems to be no hope of producing the units digit of $Q$ before reading all of $P$ unless the sequence $p^i\bmod q$ is eventually zero, which in general it isn't; exceptions include the $p^i = q^j$ case. And to produce the initial digit of $Q$ it seems that we would need to get at least a rough approximation of $p^aq^{-b}$ where $a$ is the length of $P$, which we can't know without reading $P$. The idea of producing the middle digits when we can't get the initial or final ones is risible. But I hope someone has thought of something I haven't. $\endgroup$ – Mark Dominus Oct 23 '17 at 16:20
  • $\begingroup$ In an odd coincidence, there is a post on this topic today on Jeremy Gibbons' blog. $\endgroup$ – Mark Dominus Nov 10 '17 at 17:42
1
$\begingroup$

This answer is not complete, but it is the start of a complete answer, and nothing else has been offered. I hope to finish it another time.

I have found that an online right-to-left algorithm exists in a more general case than I mentioned in my original question.


I suspect that no such algorithm exists in general, for reasons I outlined in my comment. What would the online algorithm produce first?

Units digit first

Suppose the algorithm wants to produce the units digit of $Q$ without reading all of $P$. Represent $n$ in base-$p$ as $n = \sum_i d_ip^i$ where each base-$p$ digit $d_i$ is between $0$ and $p-1$ inclusive. The units digit of $Q$ is equal to $n\bmod q$ which is $$\Bigl(\sum_i d_ip^i\Bigr)\bmod q.\tag{$\star$}$$ The result depends on every one of the $d_i$ unless the corresponding term $d_ip^i$ has the same value $\bmod q$ for each possible value of $d_i$. In particular we must have $$0\cdot p^i \equiv 1\cdot p^i\pmod q$$ so $p^i$ must be a multiple of $q$ in order for us to ignore the $i$th term of the sum. Say $p^{k_0}$ is a multiple of $q$ for some $k_0$. Then in computing the units digit of $Q$ we can disregard all the terms of the sum with $i\ge k_0$, and we need only examine the first $k_0$ digits of $P$.

To compute the next digit of $Q$ we can disregard all the terms of the sum with $i\ge k_1$ where $k_1$ is the smallest number for which $p^{k_1}$ is a multiple of $q^2$, and so on.

For example, suppose $p=6$ and $q=8$ and $n=3021213_6$. $6^3$ is a multiple of $8$ so we can generate the units digit of $Q$ just by examining the last three digits of $P$. $2\cdot6^2 + 1\cdot 6 +3 \equiv 1\pmod 8$ so the units digit of $Q$ is 1. Reading the next three digits of $P$ will allow us to compute another digit of $Q$, and so on.

This situation includes the case of $p^i=q^j$ that I discussed in the original question, but it is more general.

Note that although the $k_i = O(i)$ it may not increase smoothly. We actually have $k_i = \lfloor c(i+1)\rfloor$ for some rational constant $c$ that depends on $P$ and $Q$. For example, $24$ is a multiple of $4$, and so $24^2$ must be a multiple of $4^2$, but it is also a multiple of $4^3$. Next $24^3$ is a multiple of $4^4$ but not of $4^5$. So when converting from base $24$ to base $4$, reading the first digit of $P$ gets you one digit of $Q$, but reading the next digit of $P$ gets you not one but two more digits of $Q$. Reading the third digit of $P$ gets you only one more digit of $Q$. Here $c = \frac32$.


(To come: most significant digit first; intermediate digits first.)

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