<p>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)$.)</p>

<p>The standard divide-and-conquer algorithms are described e.g. in Brent&amp;Zimmermann, <em>Modern computer arithmetic</em>, and go as follows:</p>

<ol>
<li><strong>Conversion from binary to base $b$</strong></li>
</ol>

<p>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}$.</p>

<p>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$:</p>

<p>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$.</p>

<p>($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.)</p>

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

<ol start="2">
<li><strong>Conversion from base $b$ to binary</strong></li>
</ol>

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

CC BY-SA 3.0
2017-11-21T15:12:25.433Z
2017-11-21T15:12:25.433Z
Emil Jeřábek
<p>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).</p>

<p>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 &lt; 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.</p>

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

CC BY-SA 3.0
2017-11-21T10:45:00.840Z
This [answer](https://cs.stackexchange.com/a/21799/8532) on a sister website is relevant.
Bruno
CC BY-SA 3.0
2017-11-21T02:42:05.713Z
2017-11-21T02:55:00.217Z
2017-11-21T02:55:00.217Z
Dan Brumleve
<p>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.</p>

<p>Is base conversion known to be computable in better than essentially quadratic time?</p>

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

<reference-request><time-complexity><turing-machines>
What is the time complexity of base conversion on a multi-tape Turing machine?
Dan Brumleve
# What is the time complexity of base conversion on a multi-tape Turing machine?

(Asked by: username_0 on 2017-11-20)

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.

**Tags:** reference-request, time-complexity, turing-machines


---

## 2 answers

### Answer by username_1 on 2017-11-21. Score: 4 | Accepted answer

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

Using division with remainder, compute $a\_0,a\_1

That is, in the second stage, compute $a\_{00},a\_{01},a\_{10},a\_{11}

($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 by username_0 on 2017-11-21. Score: 1

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.

> **Comments:**
> **username_2**: This [answer](https://cs.stackexchange.com/a/21799/8532) on a sister website is relevant.  

---

