python implementations of some algorithms for use by longobject c the goal is to provide asymptotically faster algorithms that can be used for operations on integers with many digits in those cases the performance overhead of the python implementation is not significant since the asymptotic behavior is what dominates runtime functions provided by this module should be considered private and not part of any public api note for ease of maintainability please prefer clear code and avoid microoptimizations this module will only be imported and used for integers with a huge number of digits saving a few microseconds with tricky or nonobvious code is not worth it for people looking for maximum performance they should use something like gmpy2 import re import decimal def inttodecimaln function due to tim peters see gh issue 90716 for details https github compythoncpythonissues90716 the implementation in longobject c of base conversion algorithms between powerof2 and nonpowerof2 bases are quadratic time this function implements a divideandconquer algorithm that is faster for large numbers builds an equal decimal decimal in a clever recursive way if we want a string representation we apply str to that return d2w and store the result also possibly save some intermediate results in context these are likely to be reused across various levels of the conversion to decimal if result mem getw is none if w bitlim result d2w elif w 1 in mem result t memw 1 t else w2 w 1 if w happens to be odd ww2 is one larger then w2 now recurse on the smaller first w2 so that it s in the cache and the larger ww2 can be handled by the cheaper w1 in mem branch instead result w2poww2 w2poww w2 memw result return result def innern w if w bitlim return dn w2 w 1 hi n w2 lo n hi w2 return innerlo w2 innerhi w w2 w2poww2 with decimal localcontext as ctx ctx prec decimal maxprec ctx emax decimal maxemax ctx emin decimal minemin ctx trapsdecimal inexact 1 if n 0 negate true n n else negate false result innern n bitlength if negate result result return result def inttodecimalstringn asymptotically fast conversion of a str to an int function due to bjorn martinsson see gh issue 90716 for details https github compythoncpythonissues90716 the implementation in longobject c of base conversion algorithms between powerof2 and nonpowerof2 bases are quadratic time this function implements a divideandconquer algorithm making use of python s built in big int multiplication since python uses the karatsuba algorithm for multiplication the time complexity of this function is olens1 58 diglim 2048 mem def w5poww if result mem getw is none if w diglim result 5w elif w 1 in mem result memw 1 5 else w2 w 1 if w happens to be odd ww2 is one larger then w2 now recurse on the smaller first w2 so that it s in the cache and the larger ww2 can be handled by the cheaper w1 in mem branch instead result w5poww2 w5poww w2 memw result return result def innera b if b a diglim return intsa b mid a b 1 1 return innermid b innera mid w5powb mid b mid return inner0 lens def intfromstrings pylongfromstring has already removed leading checked for invalid use of underscore characters checked that string consists of only digits and underscores and stripped leading whitespace the input can still contain underscores and have trailing whitespace asymptotically fast version of decimal string to int conversion fixme this doesn t support the full syntax that int supports m re matchr s 09s s if not m raise valueerror invalid literal for int with base 10 v intfromstringm group2 if m group1 v v return v fast integer division based on code from mark dickinson fastdiv py gh47701 additional refinements and optimizations by bjorn martinsson the algorithm is due to burnikel and ziegler in their paper fast recursive division divlimit 4000 def div2n1na b n if a bitlength n divlimit return divmoda b pad n 1 if pad a 1 b 1 n 1 halfn n 1 mask 1 halfn 1 b1 b2 b halfn b mask q1 r div3n2na n a halfn mask b b1 b2 halfn q2 r div3n2nr a mask b b1 b2 halfn if pad r 1 return q1 halfn q2 r def div3n2na12 a3 b b1 b2 n decompose nonnegative int a into base 2n input a is a nonnegative integer output list of the digits of a in base 2n in littleendian order meaning the most significant digit is last the most significant digit is guaranteed to be nonzero if a is 0 then the output is an empty list combine base2n digits into an int this function is the inverse of int2digits for more details see int2digits divide a nonnegative integer a by a positive integer b giving quotient and remainder use gradeschool algorithm in base 2n n nbitsb n b bitlength adigits int2digitsa n r 0 qdigits for adigit in reversedadigits qdigit r div2n1nr n adigit b n qdigits appendqdigit qdigits reverse q digits2intqdigits n return q r def intdivmoda b if b 0 raise zerodivisionerror elif b 0 q r intdivmoda b return q r elif a 0 q r intdivmoda b return q b r else return divmodposa b asymptotically fast conversion of an int to decimal function due to tim peters see gh issue 90716 for details https github com python cpython issues 90716 the implementation in longobject c of base conversion algorithms between power of 2 and non power of 2 bases are quadratic time this function implements a divide and conquer algorithm that is faster for large numbers builds an equal decimal decimal in a clever recursive way if we want a string representation we apply str to _that_ return d 2 w and store the result also possibly save some intermediate results in context these are likely to be reused across various levels of the conversion to decimal if w happens to be odd w w2 is one larger then w2 now recurse on the smaller first w2 so that it s in the cache and the larger w w2 can be handled by the cheaper w 1 in mem branch instead asymptotically fast conversion of an int to a decimal string asymptotically fast conversion of a str to an int function due to bjorn martinsson see gh issue 90716 for details https github com python cpython issues 90716 the implementation in longobject c of base conversion algorithms between power of 2 and non power of 2 bases are quadratic time this function implements a divide and conquer algorithm making use of python s built in big int multiplication since python uses the karatsuba algorithm for multiplication the time complexity of this function is o len s 1 58 return 5 w and store the result also possibly save some intermediate results in context these are likely to be reused across various levels of the conversion to int if w happens to be odd w w2 is one larger then w2 now recurse on the smaller first w2 so that it s in the cache and the larger w w2 can be handled by the cheaper w 1 in mem branch instead asymptotically fast version of pylong_fromstring conversion of a string of decimal digits into an int pylong_fromstring has already removed leading checked for invalid use of underscore characters checked that string consists of only digits and underscores and stripped leading whitespace the input can still contain underscores and have trailing whitespace asymptotically fast version of decimal string to int conversion fixme this doesn t support the full syntax that int supports fast integer division based on code from mark dickinson fast_div py gh 47701 additional refinements and optimizations by bjorn martinsson the algorithm is due to burnikel and ziegler in their paper fast recursive division divide a 2n bit nonnegative integer a by an n bit positive integer b using a recursive divide and conquer algorithm inputs n is a positive integer b is a positive integer with exactly n bits a is a nonnegative integer such that a 2 n b output q r such that a b q r and 0 r b helper function for _div2n1n not intended to be called directly decompose non negative int a into base 2 n input a is a non negative integer output list of the digits of a in base 2 n in little endian order meaning the most significant digit is last the most significant digit is guaranteed to be non zero if a is 0 then the output is an empty list combine base 2 n digits into an int this function is the inverse of _int2digits for more details see _int2digits divide a non negative integer a by a positive integer b giving quotient and remainder use grade school algorithm in base 2 n n nbits b asymptotically fast replacement for divmod for int its time complexity is o n 1 58 where n bits a bits b
import re
import decimal


def int_to_decimal(n):

    D = decimal.Decimal
    D2 = D(2)

    BITLIM = 128

    mem = {}

    def w2pow(w):
        
        if (result := mem.get(w)) is None:
            if w <= BITLIM:
                result = D2**w
            elif w - 1 in mem:
                result = (t := mem[w - 1]) + t
            else:
                w2 = w >> 1
                
                
                
                
                result = w2pow(w2) * w2pow(w - w2)
            mem[w] = result
        return result

    def inner(n, w):
        if w <= BITLIM:
            return D(n)
        w2 = w >> 1
        hi = n >> w2
        lo = n - (hi << w2)
        return inner(lo, w2) + inner(hi, w - w2) * w2pow(w2)

    with decimal.localcontext() as ctx:
        ctx.prec = decimal.MAX_PREC
        ctx.Emax = decimal.MAX_EMAX
        ctx.Emin = decimal.MIN_EMIN
        ctx.traps[decimal.Inexact] = 1

        if n < 0:
            negate = True
            n = -n
        else:
            negate = False
        result = inner(n, n.bit_length())
        if negate:
            result = -result
    return result


def int_to_decimal_string(n):
    
    return str(int_to_decimal(n))


def _str_to_int_inner(s):
    
    DIGLIM = 2048

    mem = {}

    def w5pow(w):
        
        if (result := mem.get(w)) is None:
            if w <= DIGLIM:
                result = 5**w
            elif w - 1 in mem:
                result = mem[w - 1] * 5
            else:
                w2 = w >> 1
                
                result = w5pow(w2) * w5pow(w - w2)
            mem[w] = result
        return result

    def inner(a, b):
        if b - a <= DIGLIM:
            return int(s[a:b])
        mid = (a + b + 1) >> 1
        return inner(mid, b) + ((inner(a, mid) * w5pow(b - mid)) << (b - mid))

    return inner(0, len(s))


def int_from_string(s):
    
    
    
    
    
    s = s.rstrip().replace('_', '')
    return _str_to_int_inner(s)


def str_to_int(s):
    
    
    m = re.match(r'\s*([+-]?)([0-9_]+)\s*', s)
    if not m:
        raise ValueError('invalid literal for int() with base 10')
    v = int_from_string(m.group(2))
    if m.group(1) == '-':
        v = -v
    return v

_DIV_LIMIT = 4000


def _div2n1n(a, b, n):
    
    if a.bit_length() - n <= _DIV_LIMIT:
        return divmod(a, b)
    pad = n & 1
    if pad:
        a <<= 1
        b <<= 1
        n += 1
    half_n = n >> 1
    mask = (1 << half_n) - 1
    b1, b2 = b >> half_n, b & mask
    q1, r = _div3n2n(a >> n, (a >> half_n) & mask, b, b1, b2, half_n)
    q2, r = _div3n2n(r, a & mask, b, b1, b2, half_n)
    if pad:
        r >>= 1
    return q1 << half_n | q2, r


def _div3n2n(a12, a3, b, b1, b2, n):
    
    if a12 >> n == b1:
        q, r = (1 << n) - 1, a12 - (b1 << n) + b1
    else:
        q, r = _div2n1n(a12, b1, n)
    r = (r << n | a3) - q * b2
    while r < 0:
        q -= 1
        r += b
    return q, r


def _int2digits(a, n):
    
    a_digits = [0] * ((a.bit_length() + n - 1) // n)

    def inner(x, L, R):
        if L + 1 == R:
            a_digits[L] = x
            return
        mid = (L + R) >> 1
        shift = (mid - L) * n
        upper = x >> shift
        lower = x ^ (upper << shift)
        inner(lower, L, mid)
        inner(upper, mid, R)

    if a:
        inner(a, 0, len(a_digits))
    return a_digits


def _digits2int(digits, n):
    

    def inner(L, R):
        if L + 1 == R:
            return digits[L]
        mid = (L + R) >> 1
        shift = (mid - L) * n
        return (inner(mid, R) << shift) + inner(L, mid)

    return inner(0, len(digits)) if digits else 0


def _divmod_pos(a, b):
    
    
    n = b.bit_length()
    a_digits = _int2digits(a, n)

    r = 0
    q_digits = []
    for a_digit in reversed(a_digits):
        q_digit, r = _div2n1n((r << n) + a_digit, b, n)
        q_digits.append(q_digit)
    q_digits.reverse()
    q = _digits2int(q_digits, n)
    return q, r


def int_divmod(a, b):
    
    if b == 0:
        raise ZeroDivisionError
    elif b < 0:
        q, r = int_divmod(-a, -b)
        return q, -r
    elif a < 0:
        q, r = int_divmod(~a, b)
        return ~q, b + ~r
    else:
        return _divmod_pos(a, b)