Function _dec_str_to_int_inner

Lib/_pylong.py:271–387

(s, *, GUARD=8)

del defaultdict

def _dec_str_to_int_inner(s, *, GUARD=8):
    # Yes, BYTELIM is "large". Large enough that CPython will usually
    # use the Karatsuba _str_to_int_inner to convert the string. This
    # allowed reducing the cutoff for calling _this_ function from 3.5M
    # to 2M digits. We could almost certainly do even better by
    # fine-tuning this and/or using a larger output base than 256.
    BYTELIM = 100_000
    D = decimal.Decimal
    result = bytearray()
    # See notes at end of file for discussion of GUARD.
    assert GUARD > 0 # if 0, `decimal` can blow up - .prec 0 not allowed

    def inner(n, w):
        #assert n < D256 ** w # required, but too expensive to check
        if w <= BYTELIM:
            # XXX Stefan Pochmann discovered that, for 1024-bit ints,
            # `int(Decimal)` took 2.5x longer than `int(str(Decimal))`.
            # Worse, `int(Decimal) is still quadratic-time for much
            # larger ints. So unless/until all that is repaired, the
            # seemingly redundant `str(Decimal)` is crucial to speed.
            result.extend(int(str(n)).to_bytes(w)) # big-endian default
            return
        w1 = w >> 1
        w2 = w - w1
        if 0:
            # This is maximally clear, but "too slow". `decimal`
            # division is asymptotically fast, but we have no way to
            # tell it to reuse the high-precision reciprocal it computes
            # for pow256[w2], so it has to recompute it over & over &
            # over again :-(
            hi, lo = divmod(n, pow256[w2][0])
        else:
            p256, recip = pow256[w2]
            # The integer part will have a number of digits about equal
            # to the difference between the log10s of `n` and `pow256`
            # (which, since these are integers, is roughly approximated
            # by `.adjusted()`). That's the working precision we need,
            ctx.prec = max(n.adjusted() - p256.adjusted(), 0) + GUARD
            hi = +n * +recip # unary `+` chops back to ctx.prec digits
            ctx.prec = decimal.MAX_PREC
            hi = hi.to_integral_value() # lose the fractional digits
            lo = n - hi * p256
            # Because we've been uniformly rounding down, `hi` is a
            # lower bound on the correct quotient.
            assert lo >= 0
            # Adjust quotient up if needed. It usually isn't. In random
            # testing on inputs through 5 billion digit strings, the
            # test triggered once in about 200 thousand tries.
            count = 0
            if lo >= p256:
                count = 1
                lo -= p256
                hi += 1
                if lo >= p256:
                    # Complete correction via an exact computation. I
                    # believe it's not possible to get here provided
                    # GUARD >= 3. It's tested by reducing GUARD below
                    # that.