仅使用 O(lg β) 次乘法和除法将 β 位整数转换为数字数组
convert β-bit integer to array of digits using only O(lg β) multiplications and divisions
(编辑：我的问题被标记为重复的 question 已经 link 编辑在我原来的 post 中，甚至在标记之前，我没有考虑这足以回答我的具体问题，为什么在不对未知函数做出任何假设的情况下如何获得一定的复杂性。）
我正在尝试解决 CLRS 中的练习（Cormen 算法介绍，第 3 版）。练习内容如下：
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).
这个问题有人问过 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 甚至明确指出了 Θ[M(β)lgβ] 结果，但解释起来很手忙脚乱，好像结果很明显:
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.
这个解释对我来说并不完全清楚：如果不对 M(n) 做任何假设，这样的递归将导致 O(M(n) n) 时间，而不是 O(M(n) log(n )). （编辑：我的问题已被标记为该线程的重复，但我已经在我的原始 post 中包含了该线程的 link，然后才被标记为重复，因为我觉得答案那个线程没有充分解决我感到困惑的问题）。
据我了解，问题是说每个乘法、商和余数运算都需要一个常数时间 M，它支配所有其他类型的运算，例如加法。因此，主导项 M(β)lgβ 仅来自仅执行 lgβ 乘法和除法。
然而，我想不出任何只需要 lgβ 分裂的东西。例如，如果我们从问题中得到提示，我们可以用伪代码提出以下分治算法。
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)
在 d 位数字 n 上调用 decimal(x,1,d,n)，为简单起见，d 是 2 的幂，将 in 的十进制表示形式放入大小为 d 的数组 x 中。假设行 quotient, remainder = n / t 花费时间 M 并支配运行时的所有其他内容，运行时递归为 T(β) = 2T(β/2) + M，其解为 T(β) = Θ( βM)，而不是 Θ(Mlgβ)。
我对问题的理解是否正确？如果是这样，如何仅使用 Θ(lgβ) 乘法 and/or 除法得到十进制表示？
The following page by a very well-known Whosebug user讨论了这个问题。特别是：
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.
但是，我仍然不明白这是 O(lg B) 乘法；如果你在两半上递归，根据定义，你访问递归树中的每个节点，因此有 O(B) 乘法！
Brent 的《现代计算机算术》第 239 页第 55 页，which can be seen here，也讨论了 "subquadratic algorithms"，并提到了 M(β)lgβ 分而治之算法。但是，我仍然不知道 lg β 从何而来。同样，如果你分而治之，并在 两半 上递归，运行时间至少是线性的，而不是对数的！该书第239页第55页提供了以下算法（略有转述）：
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)
布伦特声称：
If the input A has n words, Algorithm FastIntegerOutput has complexity O(M(n) log n)
但是，我还是不明白这怎么可能，因为行 (Q, R) = DivRem(A, B^k) 被调用了 O(n) 次，而不是 O(lg n)?
首先，先说明一下：据我所知，我的问题的标题要求的是用对数的除法和乘法进行转换是不可能的；这只是我基于对问题阅读的误解而做出的假设。
我和教科书的作者Modern Computer Arithmetic通信，他们说算法确实调用除法Θ(β)次，而不是Θ(lgβ)，在更深的递归层次上，M在fact 作用于 smaller-sized 参数，而不是常数，top-level β 正如我在问题中错误假设的那样。特别是，树的顶层调用有 M(β/2)，下一层有 2M(β/4)，然后是 4M(β/8)，等等，总共 lg β 层。只要M(β) = Ω(β)，树求和就是O(M(β) lg β)，虽然一般来说是not Ω(M(β) lgβ)，因此 而不是 Θ(M(β) lgβ)。例如，对于多项式 M(β) = Θ(β^α)，对于 α = 1，树求和为 Θ(β lg β) = Θ(M(β) lg β)，并且 Θ(β^α) = Θ(M(β)) 对于 α > 1.
因此，如果我们只假设 M(β) = Ω(β)，那么运行时间将更准确地描述为 O(M(β) lg β)，而不是 Θ(M(β) lg β)就像在 CLRS 练习中一样。 （在我与现代计算机算术的一位作者的通信中，他们认为 CLRS 意味着 "give an efficient algorithm" 意味着假设 M(β) 是线性或拟线性的，但 CLRS 通常非常明确地说明了我们应该make，"give an efficient algorithm" 只是一个有点通用的短语，他们经常在课文中使用它来解决练习和问题，所以我觉得这可能是 CLRS 的一个小错字。
更新：我向 CLRS errata page 提交了这个小更正，现在已经上线了：
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.
(编辑：我的问题被标记为重复的 question 已经 link 编辑在我原来的 post 中，甚至在标记之前，我没有考虑这足以回答我的具体问题，为什么在不对未知函数做出任何假设的情况下如何获得一定的复杂性。）
我正在尝试解决 CLRS 中的练习（Cormen 算法介绍，第 3 版）。练习内容如下：
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).
这个问题有人问过 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 甚至明确指出了 Θ[M(β)lgβ] 结果，但解释起来很手忙脚乱，好像结果很明显:
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.
这个解释对我来说并不完全清楚：如果不对 M(n) 做任何假设，这样的递归将导致 O(M(n) n) 时间，而不是 O(M(n) log(n )). （编辑：我的问题已被标记为该线程的重复，但我已经在我的原始 post 中包含了该线程的 link，然后才被标记为重复，因为我觉得答案那个线程没有充分解决我感到困惑的问题）。
据我了解，问题是说每个乘法、商和余数运算都需要一个常数时间 M，它支配所有其他类型的运算，例如加法。因此，主导项 M(β)lgβ 仅来自仅执行 lgβ 乘法和除法。
然而，我想不出任何只需要 lgβ 分裂的东西。例如，如果我们从问题中得到提示，我们可以用伪代码提出以下分治算法。
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)
在 d 位数字 n 上调用 decimal(x,1,d,n)，为简单起见，d 是 2 的幂，将 in 的十进制表示形式放入大小为 d 的数组 x 中。假设行 quotient, remainder = n / t 花费时间 M 并支配运行时的所有其他内容，运行时递归为 T(β) = 2T(β/2) + M，其解为 T(β) = Θ( βM)，而不是 Θ(Mlgβ)。
我对问题的理解是否正确？如果是这样，如何仅使用 Θ(lgβ) 乘法 and/or 除法得到十进制表示？
The following page by a very well-known Whosebug user讨论了这个问题。特别是：
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.
但是，我仍然不明白这是 O(lg B) 乘法；如果你在两半上递归，根据定义，你访问递归树中的每个节点，因此有 O(B) 乘法！
Brent 的《现代计算机算术》第 239 页第 55 页，which can be seen here，也讨论了 "subquadratic algorithms"，并提到了 M(β)lgβ 分而治之算法。但是，我仍然不知道 lg β 从何而来。同样，如果你分而治之，并在 两半 上递归，运行时间至少是线性的，而不是对数的！该书第239页第55页提供了以下算法（略有转述）：
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)
布伦特声称：
If the input A has n words, Algorithm FastIntegerOutput has complexity O(M(n) log n)
但是，我还是不明白这怎么可能，因为行 (Q, R) = DivRem(A, B^k) 被调用了 O(n) 次，而不是 O(lg n)?
首先，先说明一下：据我所知，我的问题的标题要求的是用对数的除法和乘法进行转换是不可能的；这只是我基于对问题阅读的误解而做出的假设。
我和教科书的作者Modern Computer Arithmetic通信，他们说算法确实调用除法Θ(β)次，而不是Θ(lgβ)，在更深的递归层次上，M在fact 作用于 smaller-sized 参数，而不是常数，top-level β 正如我在问题中错误假设的那样。特别是，树的顶层调用有 M(β/2)，下一层有 2M(β/4)，然后是 4M(β/8)，等等，总共 lg β 层。只要M(β) = Ω(β)，树求和就是O(M(β) lg β)，虽然一般来说是not Ω(M(β) lgβ)，因此 而不是 Θ(M(β) lgβ)。例如，对于多项式 M(β) = Θ(β^α)，对于 α = 1，树求和为 Θ(β lg β) = Θ(M(β) lg β)，并且 Θ(β^α) = Θ(M(β)) 对于 α > 1.
因此，如果我们只假设 M(β) = Ω(β)，那么运行时间将更准确地描述为 O(M(β) lg β)，而不是 Θ(M(β) lg β)就像在 CLRS 练习中一样。 （在我与现代计算机算术的一位作者的通信中，他们认为 CLRS 意味着 "give an efficient algorithm" 意味着假设 M(β) 是线性或拟线性的，但 CLRS 通常非常明确地说明了我们应该make，"give an efficient algorithm" 只是一个有点通用的短语，他们经常在课文中使用它来解决练习和问题，所以我觉得这可能是 CLRS 的一个小错字。
更新：我向 CLRS errata page 提交了这个小更正，现在已经上线了：
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.