高效的数制转换算法

Question

当源整数大小任意时，是否有有效的数字系统之间转换的算法？

例如，假设有一个整数数组 {1, 4, 8} 作为十进制格式的 148 作为输入。它可能会转换为十六进制格式的 {9, 4}，或八进制格式的 {2, 2, 4}，或二进制格式的 {1, 0, 0, 1, 0, 1, 0, 0}，或者只是 { 148} 采用 1234 进制格式或其他格式。

当实际值可以用机器支持的字长来表示时，这很简单。但是当它达到任意大小时，我找不到比 O(n^2) 更好的有效方法。

Answer 1

除以底数，推回模块，冲洗并重复，同时商！= 0。

因此，例如将 148 转换为底数 16

148 / 16 = 9 r 4
  9 / 16 = 0 r 9

因此，十六进制的 148 是 0x94。这不应该花这么长时间。

Answer 2

假设我们想要从基 b1 转换为基 b2。如果 b1 和 b2 都是公共基数 b 的幂，则说 b1 = b^i1 和 b2 = b^i2 那么这可以在 O(n) 内完成。特别是这适用于二进制、八进制、十六进制、2^32、2^64 等之间的转换。那是因为您实际上只是对位进行重新分区。考虑八进制和十六进制中数字 3214 的数字位：

3214 = 12*16^2 + 8*16 + 14 = 6*8^3 + 2*8^2 + 1*8 + 6
     = {1100, 1000, 1110} base 16
     = {110, 010, 001, 110} base 8

您可以看到它们都是相同的位，只是在每个基数的数字之间划分不同。制作一种使用位移位和掩码从一种算法转换为另一种算法并不难。从例如基数 9 到基数 27 的转换也是如此，只不过您将基数 3 数字而不是位进行分区，然后将它们转移到不同的存储桶中。

现在，如果 b1 和 b2 不相称，那么事情就不那么简单了，但仍然可以使用分而治之的方法在次二次时间内完成。教科书[1]的7.1节描述了基数转换的算法1.25和1.26。这些算法的假设是您正在转换为用于大整数算术的基数（并且您可以在该基数中进行大整数算术）。您可以使用它通过转换 b1 ->; 来实现任意基数转换。 bigint -> b2 不过。

在这里，我将在 Python 中演示算法 1.25，它自然支持开箱即用的大整数算术：

# Algorithm 1.25:

def parse_int(S: str, B: int = 10) -> int:
    """parse string S as an integer in base B"""
    m = len(S)
    l = list(map(int, S[::-1]))
    b, k = B, m
    while k > 1:
        last = [l[-1]] if k % 2 == 1 else []
        l = [l1 + b*l2 for l1, l2 in zip(l[::2], l[1::2])]
        l.extend(last)
        b, k = b**2, (k + 1) >> 1
    [l0] = l
    return l0

因为这首先使用 str 将所有字符转换为 int，所以此实现仅适用于基数从 2 到 10，但如果输入是作为整数列表而不是字符串提供的，则不需要该步骤。请注意，此代码中并未明确说明，但 l1 + b*l2 和 b**2 需要使用大整数算术进行计算。这里返回的结果是一个大整数。

算法1.26可以将一个大整数转换为任意基数的数字字符串。一个简单的实现：

# Algorithm 1.26:

def format_int(A: int, B: int = 10) -> str:
    """Format integer A as a string in base B"""
    if A < B:
        # Here we use str for the base case of a single digit but probably
        # there should be some cutoff for using an O(n^2) algorithm for
        # sufficiently small inputs.
        return str(A)
    else:
        # find k so that B**(2*k-2) <= A < B**(2*k)
        k = 1
        B2k = B2 = B**2
        while A > B2k:
            k += 1
            B2k *= B2
        if A == B2k:
            k += 1
        # assert B**(2*k - 2) <= A < B**(2*k)

        Q, R = divmod(A, B**k)
        r = format_int(R, B)
        q = format_int(Q, B)
        pad = '0'*(k - len(r))
        return ''.join([q, pad, r])

这些算法都具有复杂度M(n)*log(n)，其中n是大整数中的位数，M(n) ) 是两个 n 位整数相乘的成本。如果大整数乘法和除法具有次二次乘法性能，那么这些算法也将如此。

[1] Richard P. Brent 和 Paul Zimmermann，《现代计算机算术》。
https://members.loria.fr/PZimmermann/mca/ mca-cup-0.5.9.pdf