一种有效的整数到十进制转换算法

Question

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

给出了将给定的β-bit (二进制)整数转换为十进制表示的有效算法。如果长度最多为β的整数的乘法或除法需要时间M(β)，则可以在time Θ( M(β) lg β)中执行从二进制到十进制的转换。(提示:使用分而治之的方法，通过单独的递归获得结果的上、下两部分。

它要求时间Θ( M(β) lg β)。如果仅以lg β为递归树的高度，那么分而治之算法怎么可能呢？有人知道计划的解决方案是什么吗？

Answer 1

若要使提示工作，则必须证明M(β)是线性函数，特别是M(β)≈2·M(β/2) )。

如果是这样的话，有一个明显的解决方案:递归地将数据分割成各个部分，分别处理各个部分，并将结果组合起来。在递归的k级，将有2个ᵏ部件，每个长度约为β/( 2ᵏ)位，或约为β总计。在k级下处理总时间为2ᵏ·m(β/(2ᵏ))≈M(β) )，其中O(M(β)·lgβ)为总时间。

若要将一个值u与2·d+1位分开，并处理其两个部分(v，w)，设2·d或2·d+1=⌊β·ln(2)/ln(10)⌋，v=⌊u/10ᵈ⌋和w= u-v·10ᵈ。