import sys
import time
import decimal


def long_to_decimal(n):
    if 0:
        print('long_to_decimal', n.bit_length(), file=sys.stderr)
    # 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,
    # and then applies str to _that_.
    D = decimal.Decimal
    D2 = D(2)

    BITLIM = 128

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

    if n < 0:
        negate = True
        n = -n
    else:
        negate = False

    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

        w2pow = {}
        w = n.bit_length()
        while w >= BITLIM:
            w2 = w >> 1
            if w & 1:
                w2pow[w2 + 1] = None
            w2pow[w2] = None
            w = w2
        if w2pow:
            it = reversed(w2pow.keys())
            w = next(it)
            w2pow[w] = D2**w
            for w in it:
                if w - 1 in w2pow:
                    val = w2pow[w - 1] * D2
                else:
                    w2 = w >> 1
                    assert w2 in w2pow
                    assert w - w2 in w2pow
                    val = w2pow[w2] * w2pow[w - w2]
                w2pow[w] = val
        result = inner(n, n.bit_length())
        if negate:
            result = -result
    return result


def long_to_decimal_string(n):
    return str(long_to_decimal(n))


def timeit(n, func):
    t = time.time()
    s = func(n)
    return time.time() - t, s


print(f'{"bits":>10s} {"old":>8s} {"new":>8s}  {"ratio":>6s} {"equal"}')
for shift in range(1, 22):
    n = 1 << (1 << shift)
    t1, v1 = timeit(n, str)
    t2, v2 = timeit(n, long_to_decimal_string)
    print(f'{n.bit_length():10d} {t1:8.3f} {t2:8.3f} {t1/t2:6.1f}x {v1==v2}')