divide_mod_7_to_L.py

import timeit

def to_base_7(n):
    """
    Express an int as a base 7 string
    If libraries are allowed - numpy.base_repr()
    would almost certainly be faster
    """
    s, n = [], int(n)
    while n > 7:
        n, r = divmod(n, 7)
        s.append(str(r))
    s.append(str(n))
    return ''.join(s[::-1])
    
def generate_input(a,b):
    """
    Generate small input sets - very slow for more than a few
    hundred characters
    """
    a = to_base_7(a)
    b = to_base_7(b)
    L = 20000
    return a,b,L
    
def interpret_input(x,y,L):
    """
    Remove common multiples of powers of 7 from x and y
    and reduce them to modulo 7**L by string manipulation
    before returning them as ints
    """
    # The while loop deals with the case where
    # b is not coprime to the modulus
    i=0
    while y[-i-1] == '0':
        i+=1
    #print('Truncate the strings')
    
    # 'Divide by 7**i where i is the highest power of 7 in b    
    if i:
        y = y[:-i]       
        # Left truncate a - equivalent to doing (% 7**L)
        if len(x) > L+i:
            x = x[-(L+i+1):-i]
        else:
            x = x[:-i]
    else:
        x = x[-(L+1):]
        
    a = int(x,base=7)
    b = int(y,base=7)
    return a,b
    
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
 
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m

def main():
    #a,b,L = generate_input(7**5*5**3*2**4,125*49)
    #print('Started input')
    with open('real_data.txt') as f:
        a=f.readline().strip()
        b=f.readline().strip()
        L = int(f.readline())   
    
    #print('Strings are in')
    a,b = interpret_input(a,b,L)   
    #print('Strings interpreted')
    
    m = 7**L
    #a%=m # This step replaced by simple string truncation in interpret_input   
    c = a * modinv(b,m)
    c %= m

    return to_base_7(c)
    
if __name__ == '__main__':
    #Currently has all my proposed tricks in it, but still takes around
    #2 seconds on realistic sized input (i.e. real_data.txt)
    print(timeit.timeit("main()", setup="from __main__ import main", number=50))
    print(main())

initial_data.txt

202
13
2

medium_data_res_5346_base_7.txt

6623344600000
360100000
4

real_data.txt