Speedily calculate base 3 value of real huge integer number with Python 3

Question

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).

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. Using only built-in functions of Python 3 (no numpy)?
2. Using numpy (or another CAS library) from within a normal Python 3 program?

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.

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

Answer 1

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:]

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.