将整数转换为十进制的高效算法 [英] Efficient algorithm to convert integer to decimal

问题描述

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

给出一种有效的算法来转换给定的β位（二进制）整数到十进制表示形式。认为如果长度最大为β的整数的乘法或除法需要时间 M（β），则二进制-十进制转换可以在Θ（M（β）lgβ）的时间执行。 （提示：使用分而治之的方法，分别获得递归的结果的上半部分和下半部分。

它要求时间Θ（M（β）lgβ）。考虑到 lgβ到底是递归树的高度吗？有人知道目标解决方案是什么吗？

解决方案

要使提示起作用，必须是M（β）是线性函数的情况；尤其是M（β）≈2·M（β/ 2）。

如果给出的话，有一个明显的解决方案：将数据递归拆分为多个部分，分别处理各个部分，然后组合结果，在递归的k层将有2个部分，每个部分的长度大约β/（2ᵏ）位，或总共约β。在级别k处的处理总时间为2ᵏ·M（β/（2ᵏ））≈M（β），而总时间为O（M（β）·lgβ）。 / p>

要用β位拆分值u并处理其两个部分（v，w），则令2·d或2 ·d + 1 ＝⌊β·ln（2）/ ln（10）⌋；令v =⌊u/10ᵈ⌋和w = u-v·10ᵈ。

Problem 31.1-12 of the CLRS algorithms book asks the following question:

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.

It asks for time Θ( M(β) lg β). How is that even possible for a divide and conquer algorithm given that lg β alone is the height of the recursion tree? Does anyone know what the intended solution is?

解决方案

For the hint to work, it must be the case that M(β) is a linear function; in particular, that M(β) ≈ 2·M(β/2).

If that is given, there is an obvious solution: Recursively split the data into parts, process the parts separately, and combine the results. At level k of the recursion there will be 2ᵏ parts, each of length approximately β/(2ᵏ) bits, or about β total. The processing at level k costs 2ᵏ·M(β/(2ᵏ)) ≈ M(β), whence O(M(β)·lg β) total time.

To split a value u with β bits and process its two parts (v,w), let 2·d or 2·d+1 = ⌊β·ln(2)/ln(10)⌋; let v = ⌊u/10ᵈ⌋ and w = u-v·10ᵈ.

这篇关于将整数转换为十进制的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！