使用Python 3快速计算实大整数的基数3值 [英] Speedily calculate base 3 value of real huge integer number with Python 3

问题描述

我们有一个很大的数字，例如(10 ** 1500000)+1，并且想要将其转换为基数3. 下面是使用普通Python(不使用numpy或CAS库)发现的最快方式运行的代码.

We have a large number like (10**1500000)+1, and want to convert it to base 3. Below is running code with the fastest way we found with normal Python (without using numpy or CAS libraries).

如何加速基本转换(至基本3)的性能?

How could the performance of base conversion (to base 3) be accelerated?

我们想知道如何通过以下两种方式做到这一点:

We'd like to know how this could be done in both of the following ways:

1. 仅使用Python 3的内置函数(无numpy)?
2. 在普通的Python 3程序中使用numpy(或其他CAS库)吗?

非常欢迎任何帮助.这是我们当前的代码:

Any help is very welcome. Here is our current code:

#### --- 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])

在

In How to calculate as quick as possible the base 3 value of an integer which is given as a huge sequence of decimal digits (more than one million)? was a similar question with some more steps before the base conversion. In this question here, we concentrate on that part, which consumed by far the major part of the time, and for which we didn't get an answer yet.

也在>将以10为底的数字转换为以3为底的数字，则没有处理HUGE数字的性能方面.

Also in Convert a base 10 number to a base 3 number, the performance aspect of HUGE numbers was not dealt with.

推荐答案

以下是通过在每次调用中对基数平方进行递归来扩展您的convsteps解决方案的方法.要删除前导零，还需要做一些额外的工作.

Here's a method that expands on your convsteps solution by recursing with the base squaring with each call. Some extra work is required to remove leading zeros.

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在误差范围内相同.但这更简单，并且可能有更少的错误.

My quick timing test shows that it's the same as your step2 within the margin of error. But it's simpler and probably has fewer bugs.

这篇关于使用Python 3快速计算实大整数的基数3值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！