What is the time complexity of base conversion on a multi-tape Turing machine?
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&amp;Zimmermann, Modern computer arithmetic, and go as follows:


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&lt;b^{2^k}$.

Using division with remainder, compute $a_0,a_1&lt;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}&lt;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 $&lt;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).$$


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.