将整数转换为小数的高效算法

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

给出一个有效的算法来转换给定的β-bit（二进制）整数到十进制表示。论证如果对长度最多为 的整数进行乘法或除法β需要时间M(β)，那么就可以及时进行二进制到十进制的转换Θ( M(β) lg β). (Hint:使用分而治之的方法，通过单独的递归获得结果的上半部分和下半部分。

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

为了使提示发挥作用，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ᵈ。