使用Python 3快速计算大实数的3进制值

Question

我们有一个非常大的数字，类似于(10**1500000)+1，并希望将其转换为3进制。以下是我们在普通Python中发现的最快方法的运行代码（不使用numpy或CAS库）。

如何加速底数转换（转换为3进制）的性能？

我们想知道以下两种方式中都可以如何实现：

1.仅使用Python 3的内置函数（无numpy）？ 2.从正常的Python 3程序中使用numpy（或其他CAS库）？

欢迎任何帮助。这是我们目前的代码：

#### --- Convert a huge integer to base 3 --- ####

# Convert decimal number n to a sequence of list elements
# with integer values in the range 0 to base-1.
# With divmod, it's ca. 1/3 faster than using n%b and then n//=b.
def numberToBase(n, b):
    digits = []
    while n:
        n, rem = divmod(n, b)
        digits.append(rem)
    return digits[::-1]

# Step 2: Convert given integer to another base
# With convsteps == 3, it's about 50-100 times faster than
# with with convsteps == 1, where numberToBase() is called only once.
def step2(n, b, convsteps):
    nList = []
    if convsteps == 3:  # Here the conversion is done in 3 steps
        expos = 10000, 300
        base_a = b ** expos[0]
        base_b = b ** expos[1]
        nList1 = numberToBase(n, base_a)  # time killer in this part
        nList2 = [numberToBase(ll, base_b) for ll in nList1]
        nList3 = [numberToBase(mm, b) for ll in nList2 for mm in ll]
        nList = [mm for ll in nList3 for mm in ll]
    else: # Do conversion in one bulk
        nList = numberToBase(n, b)  # that's the time killer in this part
    return nList


if __name__ == '__main__':

    int_value = (10**1500000)+1  # sample huge numbers
                          # expected begin: [2, 2, 0, 1, 1, 1, 1, 0, 2, 0]
                          # expected time: 4 min with convsteps=3
    base = 3

    # Convert int_value to list of numbers of given base
    # -- two variants of step2() using different convsteps params
    numList = step2(int_value, base, convsteps=1)
    print('   3-1: numList begin:', numList[:10])

    # A value of '3' for the parameter "convsteps" makes
    # step2() much faster than a value of '1'
    numList = step2(int_value, base, convsteps=3)
    print('   3-3: numList begin:', numList[:10])

在如何尽快计算一个大于一百万位的十进制整数的三进制值?中有一个类似的问题，但在基本转换之前需要进行更多的步骤。 在这个问题中，我们集中讨论了远远占用时间的部分，并且我们还没有得到答案。

此外，在将十进制数转换为三进制数中，没有涉及到处理大数的性能方面。

- phdgroupA

---

我想知道 yield 是否比 list.append 更快？你也可以尝试将字符串反转而不是列表。 - Mark Ransom

对于 n = 10**30000 + 1，n = 10**80000 + 1 和其他大数值，我从 numberToBase(n, 3) 和 step2(n, 3, 3) 得到了不同的结果；答案长度也不同。我认为在 convsteps == 3 代码中组装结果的方式存在错误，因为对结果开头和结尾数字的目测检查表明它们是一致的。 - Warren Weckesser

@WarrenWeckesser 你是正确的，这里有一个 bug。如果任何中间结果中有前导零，则将被删除。 - Mark Ransom

我建议尝试使用类似于 gmpy2 的大数库包装器；例如 gmpy2.digits(your_num, 3)，即使与设计良好的纯 Python 替代方案相比，也能提高几个数量级。 - DSM

@Mark Ransom：你说过，如果中间结果中有前导零，它们会被删除。这该怎么解决？ - phdgroupA

Answer 1

这里有一种方法，它在您的 convsteps 解决方案的基础上通过每次调用进行平方递归。需要一些额外的工作来移除前导零。

def number_to_base(n, b):
    if n < b:
        return [n]
    else:
        digits = [d for x in number_to_base(n, b*b) for d in divmod(x, b)]
        return digits if digits[0] else digits[1:]

我的快速时间测试显示，它与您的step2相同，误差在可接受范围内。但是它更简单，可能有更少的错误。

- Mark Ransom

---

只是想补充一下，我做了一些基准测试，对于十进制数，在 ~ n=10**1000000 后，此函数开始优于 str(n)，这最终归结为 long_to_decimal_string_internal() 使用的 TAOCP，Knuth - Vol. 2 Sect. 4.4 Method 1b。这包括 "".join(map(str, ... )) 的时间。对于 n=10**10000000，它比内置转换快两倍。在 Windows 10 上的 Python 3.6.4 上进行测试。 - Dillon Davis

@DillonDavis：您能否详细说明一下，当您写下“开始优于str(n)”时，您比较了什么？numberToBase()或number_to_base()在哪里使用了str(n)？还是这是一般性的评论。如果是这样，是的，对于巨大的整数，len(str(int))和str(int)正在降低。 - phdgroupA

@DillonDavis 你可以加快转换为字符串的速度：''.join('0123456789'[x] for x in seq)。我的测试使用的是10**1500000+1，这是不典型的，因为大多数数字都是零。 - Mark Ransom

@MarkRansom 我实际上测试了一下我的代码，使用了“7**N”来得到与该精度同级别的值，正是出于这个原因。 - Dillon Davis

@MarkRansom 我认为提交一个补丁或者至少创建一个工单是值得的。除了渐进地更快，它还是一个更通用的算法-相同的代码适用于所有基数，而不仅仅是十进制。这将为未来支持其他进制数系统打开大门。 - Dillon Davis