import sys
import functools
from timeit import default_timer as clock

# Based on code from bjorn-martinsson GH-90716, faster str-to-int conversion
# for large numbers.

@functools.cache
def _pow5(n):
    if n == 0:
        return 5
    p = _pow5(n-1)
    return p*p

def str_to_long(s):
    def inner(l, r):
        if r - l <= 3000:
            return int(s[l:r])
        lg_split = (r - l - 1).bit_length() - 1
        split = 1 << lg_split
        return ((inner(l, r - split) * _pow5(lg_split)) << split) + inner(
            r - split, r
        )

    return inner(0, len(s))


def time_func(upto=20):
    fmt = "%10s %12.3f %12.3f %8.2f %8s"
    print(
        "%10s %12s %12s %8s %8s"
        % ("digits", "old time", "new time", "faster", "correct")
    )
    print("-" * 78)
    for i in range(10, upto):
        n = 2**i
        Q = '1'*n
        t1 = clock()
        R1 = int(Q)
        t2 = clock()
        R2 = str_to_long(Q)
        t3 = clock()
        size =len(Q)
        old_time, new_time = t2 - t1, t3 - t2
        faster, correct = old_time / new_time, R2 == R1
        print(fmt % (size, old_time, new_time, faster, correct))


if __name__ == '__main__':
    time_func()