algorithm - 整数转小数的高效算法

Question

CLRS 算法书的问题 31.1-12 提出以下问题:

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 binary-to-decimal conversion can be performed in time Θ( M(β) lg β). (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.

它要求时间 Θ( M(β) lg β)。考虑到 lg β 本身就是递归树的高度，分而治之算法怎么可能呢？有谁知道预期的解决方案是什么？

Answer 1

要使提示起作用，必须满足 M(β) 是线性函数的情况；特别地，M(β) ≈ 2·M(β/2)。

如果给出，则有一个明显的解决方案:递归地将数据拆分为多个部分，分别处理这些部分，然后合并结果。在递归的第 k 层，将有 2ᵏ 个部分，每个部分的长度大约为 β/(2ᵏ) 位，或者总共大约 β 个。级别 k 的处理成本为 2ᵏ·M(β/(2ᵏ)) ≈ M(β)，因此总时间为 O(M(β)·lg β)。

要用 β 位拆分值 u 并处理它的两个部分 (v,w)，令 2·d 或 2·d+1 = ⌊β·ln(2)/ln(10)⌋；令 v = ⌊u/10ᵈ⌋ 且 w = u-v·10ᵈ。