# Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$

The following problem is from CLRS (31.1-13, Page 933, 3rd edition):

Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $Θ(M(\beta)\log \beta)$. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)

By a simple divide and conquer (by dividing $\beta$-bit integer into two $\beta/2$-bit integers), I obtain the recurrence $T(\beta) = 2T(\beta/2) + M(\beta)$. However, how to argue that it is $O(M(\beta) \log \beta)$?

My attempt: I think the result relies on $M(\beta)$. If $M(\beta) = \Theta(\beta)$, then $T(\beta) = \Theta(M(\beta)\log \beta)$. But, if, for example, $M(\beta) = o(\beta)$ or $M(\beta) = \omega(\beta^2)$, you may not obtain $T(\beta) = \Theta(M(\beta)\log \beta)$.

According to the hint, it seems that we should use different recursions to obtain $O(M(\beta)\log \beta)$ and $\Omega(M(\beta) \log \beta)$, respectively. But how?

The exercise seems fine. You can take care of those issues with a little more work, by reasoning about what the running time of a multiplication algorithm must look like.

One can show that, for any correct multiplication algorithm, we have $M(\beta)=\Omega(\beta)$. Indeed, any correct algorithm has to read all bits of the input, so the lower bound follows. Thus, the first case you were worried about, where $M(\beta)=o(\beta)$, can't happen.

We can consider two remaining cases:

• If $M(\beta)= \Theta(\beta \cdot \text{poly}(\log(\beta))$, then by the Master theorem, we have $T(\beta) = \Theta(M(\beta) \log(\beta))$. This matches the bound proposes in the exercise statement.

• If $M(\beta) = \Omega(\beta^{1+\epsilon})$ for some $\epsilon>0$, then by the Master theorem $T(\beta)=\Theta(M(\beta))$. Of course, if you can solve a problem in time $T(\beta)$, you can also solve it in time $T'(\beta)$, if $T'(\beta) \ge T(\beta)$ by padding (just add some extra no-ops). Consequently, in this case there also exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.

In either case, we achieve the claimed result.

OK, technically I realize that these don't cover all remaining cases. But I believe it is still true that once we know that $M(\beta)=\Omega(\beta)$, then it follows that the solution to the recurrence relation satisfies $T(\beta) = O(M(\beta) \log(\beta)$, so there exists a binary-to-decimal conversion algorithm whose running time is $\Theta(M(\beta) \log(\beta))$.

• "just add some extra no-ops": This sounds a little bit weird in algorithm analysis. However, it is a possible answer. – hengxin Apr 2 '17 at 6:07

If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align*} T(\beta) &= 2T(\beta/2) + M(\beta)&\text{given}\\ T(\beta) &= 2T(\beta/2) + \log \beta&\text{given (1)}\\ T(\beta) &= 2\beta - \log (\beta) - 2&\text{inductive hypothesis (2)}\\ T(\beta) &= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&\text{substitute (2) into (1)}\\ T(\beta) &= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&\text{algebra}\\ T(\beta) &= 2\beta - \log (\beta) -2&\text{QED}\\ \end{align*}

So we've proven that if $M(\beta) = \log \beta$ then $T(\beta) = O(\beta)$. However the assignment claims $O(T(\beta)) = M(\beta)\log \beta = \log^2 \beta$. This cannot be true.

If we read between the lines it seems implied that $M = Ω(\beta)$.

• Good observation. But... Multiplication has to read all bits of the input (any correct algorithm has to read the entire input), so it follows that any multiplication algorithm will satisfy $M(\beta) = \Omega(\beta)$, and we can rule out the case you are worried about here. I don't see why the exercise needs to assume that $M(\beta) = O(\beta)$; I don't think that assumption is necessary. – D.W. Mar 29 '17 at 6:03
• @D.W. You're assuming a computational model which may or may not apply. Consider hardware multiplication, where you have parallelism for every bit. – orlp Mar 29 '17 at 6:07
• @D.W. I corrected an error in my answer, I had written $M = O(\beta)$ instead of $M = Ω(\beta)$. – orlp Mar 29 '17 at 6:13
• OK, good point, I overlooked that other models of computation might be possible! But isn't that usually assumed implicitly: when we talk about a problem taking time $T(n)$, that usually implicitly refers to sequential RAM machine algorithms, unless otherwise noted, doesn't it? Do you agree? – D.W. Mar 29 '17 at 6:13
• @D.W. I definitely agree and if anything my answer is trying to be 'too clever'. – orlp Mar 29 '17 at 6:17