(edit: the question that my question has been flagged a duplicate of was already linked in my original post, even before the flagging, and I did not consider it sufficient to answer my specific question, why was how to get a certain complexity without making any assumptions about an unknown function.)
I'm trying to solve exercise in CLRS (Cormen Intro to Algorithms, 3ed). The exercise reads:
Give an efficient algorithm to convert a given β-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most β takes time M(β), then we can convert binary to decimal in time Θ[M(β)lgβ]. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions).
This question has been asked here, and here. However, the answers there either make incorrect assumptions, such as M(β)=O(β), or give an answer the completely ignores what the question is asking for. Another answer here even explicitly states the Θ[M(β)lgβ] result, but the explanation is quite handwavey, as if the result were obvious:
You can do base conversion in O(M(n) log(n)) time, however, by picking a power of target-base that's roughly the square root of the to-be-converted number, doing divide-and-remainder by it (which can be done in O(M(n)) time via Newton's method), and recursing on the two halves.
That explanation was not entirely clear to me: without making any assumptions about M(n), such a recursion would result in O(M(n) n) time, not O(M(n) log(n)). (edit: my question has been marked a duplicate of that thread, but I had already included the link to that thread in my original post, before it was marked as duplicate, as I feel that the answer to that thread did not sufficiently address the issue I was confused about).
As I understand, the question is saying that each multiplication, quotient, and remainder operation takes a constant time M, which dominates every other kind of operation, such as addition. Hence, the dominant term M(β)lgβ comes simply from performing only lgβ multiplications and divisions.
However, I am not able to come up with anything that requires only lgβ divisions. For example, if we take the hint from the question, we can come up with the following divide and conquer algorithm, in pseudocode.
decimal(x, start, end, n):
digits = end - start + 1 // assume power of 2
if digits == 1:
x[start] = n // 1-based index
else:
t = 10^(digits/2) // assume negligible time
quotient, remainder = n / t // takes M time
decimal(x, start, start+digits/2-1, quotient)
decimal(x, start+digits/2, end, remainder)
Calling decimal(x,1,d,n) on d-digit number n, with d a power of 2 for simplicity, places the decimal representation of in in the size-d array x. Assuming that the line quotient, remainder = n / t, takes time M and dominates everything else in the runtime, the runtime recursion is T(β) = 2T(β/2) + M, which has the solution T(β) = Θ(βM), not Θ(Mlgβ).
Is my understanding of the question correct? If so, how is it possible to get the decimal representation using only Θ(lgβ) multiplications and/or divisions?
The following page by a very well-known StackOverflow user discusses this problem. In particular:
Binary -> Radix: The binary -> radix conversion is the same but in reverse. Start with an N-digit number X in base 16. You wish to convert this into an M-digit number R in base b. Compute: high = floor( X / bM/2 ). Compute: low = X - bM/2 * high. Recursively convert low and high. Append the results. The final result R will be the original number converted into base b.
However, I still don't see how this is O(lg B) multiplications; if you are recursing on both halves, you are by definition visiting every node in the recursion tree, therefore there are O(B) multiplications!
page 55 of 239 of Modern Computer Arithmetic by Brent, which can be seen here, also discusses "subquadratic algorithms", and mentions the M(β)lgβ divide and conquer algorithm. However, I am still clueless as to where the lg β comes from. Again, if you divide and conquer, and recurse on both halves, the runtime is at least linear, not logarithmic! On page 55 of 239 of that book, the following algorithm is provided (slightly paraphrased):
Algorithm 1.26 FastIntegerOutput
Input: A = (sum 0 to n-1) a_i 2^i
Output: a string S of characters, representing A in based 10
if A < 10 then
return char(A)
else
find k such that 10^(2k-2) <= A < 10^(2k)
(Q, R) = DivRem(A, 10^k)
r = FastIntegerOutput(R)
return concatenate(FastIntegerOutput(Q), zeros(k-len(r)), r)
Brent claims:
If the input A has n words, Algorithm FastIntegerOutput has complexity O(M(n) log n)
but again, I don't see how this is possible, as the line (Q, R) = DivRem(A, B^k) is called O(n) times, not O(lg n)?
First, to get it out of the way: what the title of my question is asking for, to make the conversion with a logarithmic number of divisions and multiplications, is not possible as far as I know; and that was only an assumption I made based on a misunderstanding of a reading of the question.
I corresponded with the authors of the textbook Modern Computer Arithmetic, and they said that the algorithm indeed calls division Θ(β) times, not Θ( lg β), and at deeper recursive levels, M does in fact act on smaller-sized arguments, not on the constant, top-level β as I had incorrectly assumed in my question. In particular, the tree's top level call has M(β/2), the next level has 2M(β/4), then 4M(β/8), etc. for a total of lg β levels. As long as M(β) = Ω(β), the tree summation is O(M(β) lg β), though in general not Ω(M(β) lgβ), and hence not Θ(M(β) lgβ). For example, for polynomial M(β) = Θ(β^α), the tree summation is Θ(β lg β) = Θ(M(β) lg β) for α = 1, and Θ(β^α) = Θ(M(β)) for α > 1.
Hence, if we only assume M(β) = Ω(β), then the runtime would more accurately be described as O(M(β) lg β), not Θ(M(β) lg β) as in the CLRS exercise. (In my correspondance with one of the authors of Modern Computer Arithmetic, they suggested that CLRS meant that "give an efficient algorithm" meant to assume M(β) is linear or quasilinear, but CLRS is usually pretty explicit about the assumptions we are supposed to make, and "give an efficient algorithm" is just a somewhat generic phrase that they use pretty often in the text to exercises and problems, so I feel like this might be a minor typo on the part of CLRS.
Update: I submitted this minor correction to the CLRS errata page, and it is up now:
Page 933, Exercise 31.1-13. Add the restriction that M(β) = Ω(β), and change the desired time bound from Θ(M(β) lg β) to O(M(β) lg β). Reported by David Liu. Posted 25 December 2017. Severity level: 3 To be corrected in the eighth printing of the third edition.