Быстрое вычисление значения базы 3 реального огромного целого числа с помощью Python 3

Question

У нас есть большое число, например (10 ** 1500000) +1, и мы хотим преобразовать его в базу 3. Ниже приведен код, выполняемый самым быстрым способом, который мы нашли в обычном Python (без использования библиотек numpy или CAS).

Как можно повысить производительность преобразования базы (в базу 3)?

Мы хотели бы знать, как это можно сделать одним из следующих способов:

1. Использование только встроенных функций Python 3 (без numpy)?
2. Использование numpy (или другой библиотеки CAS) из обычной программы на Python 3?

Любая помощьочень приветствуетсяВот наш текущий код:

#### --- 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 Как посчитать как можно быстрее целое значение из целого числа 3, которое задается в виде огромной последовательности десятичных цифр (более одного миллиона)? был похожий вопрос с еще несколькими шагами до базового преобразования.В этом вопросе здесь мы сконцентрируемся на той части, которая потребляла большую часть времени и на которую мы еще не получили ответ.

Также в Преобразование базового числа 10на базовый номер 3 аспект производительности ОГРОМНЫХ номеров не рассматривался.

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 в пределах допустимой погрешности.Но это проще и, вероятно, содержит меньше ошибок.