live
 —    ‹      ­“QKÃ0…ßý1 oím7Ñ,¢ë@qÎá&âcÖdK kJruÎ_oº`QÁPhÚ|œ{Nï-ÛÏîúÓ§ñ€\Mo‡düp9¼î<vû Ù4kŽâ$Œ(¡±:X­Vñª[·€é=h\GàÑ™c‰’ò=V¿ã{„i%d¸†Å¯K©^‰ ;œµÏÞ×Â)(L®J¯<TkÔ¶ìF^ás…ÖžA#¤a«ÍfV®ë’éÈ•]1ÛT©·Ž3ÔäEfQö(ÚŠòÃræ«³`F×gœ	¢š÷èy¿7:»ëe”ÄR1ü[æ60”…G²´ÒÌ’­ð¤'æ­]0k˜LùÜ™
-?Qvƒä!g%B’cÊ™v»TƒÈ–¬²>û,äÇ«õÛS>Ï%’Ì8•£uëÚñ¶cÅ¾Ö&[[Î,4Ò Gß“Ï0šBKšÍŽ—Õâ¢“¤'Qru’¤§éI+˜ÆéM»Ý_6¶ƒÉ`3õší²èAáË    )   	ˆÌËÊÉÈl–ßi~”*hŠq@Šã/Üd
bÑ¿Ç„|ÆÄÃ *&    	"""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
"micro-optimizations".  This module will only be imported and used for
integers with a huge number of digits.  Saving a few microseconds with
tricky or non-obvious code is not worth it.  For people looking for
maximum performance, they should use something like gmpy2."""

import re
import decimal
try:
    import _decimal
except ImportError:
    _decimal = None


def int_to_decimal(n):
    """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_.

    D = decimal.Decimal
    D2 = D(2)

    BITLIM = 128

    mem = {}

    def w2pow(w):
        """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 (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
                # 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.
                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):
    """Asymptotically fast conversion of an 'int' to a decimal string."""
    w = n.bit_length()
    if w > 450_000 and _decimal is not None:
        # It is only usable with the C decimal implementation.
        # _pydecimal.py calls str() on very large integers, which in its
        # turn calls int_to_decimal_string(), causing very deep recursion.
        return str(int_to_decimal(n))

    # Fallback algorithm for the case when the C decimal module isn't
    # available.  This algorithm is asymptotically worse than the algorithm
    # using the decimal module, but better than the quadratic time
    # implementation in