What is the time complexity of base conversion on a multi-tape Turing machine?

Question

Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to imagine a single type of machine that can handle all cases even though the bases are fixed, so consider a base-$b$ number as being represented by a concatenation of $\lceil \log_2{(b)} \rceil$-bit words, and let our multi-tape Turing machines have a binary input and output alphabet. But equivalently we can build a machine whose input and output tape alphabet sizes match the source and target bases.

Is base conversion known to be computable in better than essentially quadratic time?

This question has been asked many times but every reference I can find is in a practical context. I have seen claims that it can be accomplished in quasilinear time, but I can't understand how this is supposed to work, in part because assumptions about the model are often unstated in such discussions.

Answer 1

Base conversion can be done in time $O(M(n)\log n)$, where $M(n)$ is a bound on the time complexity of multiplication of two $n$-bit integers. (We assume that $M(n)$ satisfies usual regularity conditions: it is monotone, and $2M(n)\le M(2n)$.)

The standard divide-and-conquer algorithms are described e.g. in Brent&Zimmermann, Modern computer arithmetic, and go as follows:

1. Conversion from binary to base $b$

Let $a$ be the input number, of length $n$. By repeated squaring, compute the sequence $b$, $b^2$, $b^4$, $b^8$, ..., $b^{2^k}$, where $k\le\log n$ is such that $a<b^{2^k}$.

Using division with remainder, compute $a_0,a_1<b^{2^{k-1}}$ such that $a=a_1b^{2^{k-1}}+a_0$. Recurse with $a_0$ and $a_1$:

That is, in the second stage, compute $a_{00},a_{01},a_{10},a_{11}<b^{2^{k-2}}$ such that $a_0=a_{01}b^{2^{k-2}}+a_{00}$ and $a_1=a_{11}b^{2^{k-2}}+a_{10}$. In the third stage, split each of the 4 numbers in two using division by $b^{2^{k-3}}$, and so on. After the $k$-th stage, we will have a sequence of numbers $<b$, which is the base-$b$ expansion of $a$.

($a$ is its own expansion in base $b^{2^k}$. After the first stage, $a_1a_0$ is the expansion of $a$ in base $b^{2^{k-1}}$. After the second stage, we have the expansion of $a$ in base $b^{2^{k-2}}$, etc.)

The running time is $$O(M(n)+2M(n/2)+4M(n/4)+\dots)\le O(M(n)\log n).$$

2. Conversion from base $b$ to binary

Reverse the process above: given the base-$b$ expansion $a_ma_{m-1}\dots a_0$, in the first stage, combine the elements in pairs as $a_{2i+1}b+a_{2i}$ to form the base-$b^2$ expansion; in the second stage, combine the blocks to larger blocks using multiplication by $b^2$ to obtain the base-$b^4$ expansion, and so on. After $\log n$ stages, we will have a single number. The running time is as above.

Answer 2

I think I just figured it out, and maybe this means it is too obvious to be an appropriate question for this site, but I'll post my solution here anyway (maybe it is wrong).

Given a number $n$ in the source base, write it as $n = a^2+b$, with $a$ and $b$ also represented in the source base. We don't even require $b < a$, just that $a$ and $b$ are of similar size, about half that of $n$. I claim finding $a$ and $b$ takes just quasilinear time, by guessing $a$ and squaring it using the Schönhage–Strassen algorithm or equivalent to find $b$. Then, recursively, convert $a$ and $b$ to the target base and compute $n = a^2+b$ in the target base, for a total time which remains quasilinear.

I'm still not completely convinced this is possible on a Turing machine, so I'll need to do some more research, and I'm still interested in any references.