# @file bignum.004.py
# @ingroup experimental
# Experimental big-number representation.
# @date 11/22/2024
 
import itertools
import operator
import random
 
class Num:
    base = 2**8
 
    def __init__(self, init):
        if isinstance(init, tuple):
            self.m = init[0]
            self.s = init[1]
        else:
            self.m = iton(abs(init), Num.base)
            self.s = init < 0
 
    def __neg__(self):
        return Num(_fixsign(self.m.copy(), not self.s))
 
    def __add__(self, other):
        return Num(nadd(self.m, self.s, other.m, other.s, Num.base))
 
    def __sub__(self, other):
        t = _fixsign(other.m, not other.s)[1]
        return Num(nadd(self.m, self.s, other.m, t, Num.base))
 
    def __mul__(self, other):
        return Num(nmul(self.m, self.s, other.m, other.s, Num.base))
 
    def __floordiv__(self, other):
        return Num(ndivmod(self.m, self.s, other.m, other.s, Num.base)[0])
 
    def __mod__(self, other):
        return Num(ndivmod(self.m, self.s, other.m, other.s, Num.base)[1])
 
    def __str__(self):
        return '-' * self.s + ntos(self.m, Num.base)
 
    def __repr__(self):
        return str((self.m, self.s))
 
# Utility.
 
def _iszero(a):
    return len(a) == 1 and a[0] == 0
 
def _fixsign(a, s):
    return a, s and not _iszero(a)
 
def _zeroextend(a, n):
    return a[:] + [0] * (n - len(a))
 
def _zeroreduce(a):
    n = len(a)
    while n != 1 and a[n-1] == 0:
        n -= 1
    return a[:n]
 
def _inplace_mul1(r, x, c, b):
    for i in range(len(r)):
        c, r[i] = divmod(r[i] * x + c, b)
    return c, r
 
# Convert.
 
def iton(x, b):
    r = []
    while True:
        x, y = divmod(x, b)
        r.append(y)
        if x == 0:
            return r
 
def nton(a, bi, bo):
    r = [0]
    for x in reversed(a):
        c = _inplace_mul1(r, bi, x, bo)[0]
        if c != 0:
            r.extend(iton(c, bo))
    return r
 
def ntos(a, b):
    return ''.join(map(str, reversed(nton(a, b, 10))))
 
# Compare.
 
def _cmp(x, y):
    return -1 if x < y else 1
 
def ncmp(a, b):
    n = len(a)
    m = len(b)
    if n != m:
        return _cmp(n, m)
    for x, y in zip(reversed(a), reversed(b)):
        if x != y:
            return _cmp(x, y)
    return 0
 
# Shift.
 
def nshl(a, n):
    return _zeroreduce([0] * n + a[:])
 
def nshr(a, n):
    return _zeroextend(a[n:], 1)
 
# Add.
 
def _add(a, b, base, op):
    n = 1 + max(len(a), len(b))
    r = _zeroextend(a, n)
    b = _zeroextend(b, n)
    c = 0
    for i in range(n):
        c, r[i] = divmod(op(r[i], b[i] + abs(c)), base)
    return _zeroreduce(r)
 
def nadd(a, s, b, t, base):
    if s == t:
        op = operator.add
    else:
        op = operator.sub
        if ncmp(a, b) < 0:
            a, b, s = b, a, t
    return _fixsign(_add(a, b, base, op), s)
 
# Multiply.
 
def _mul1(a, x, base):
    n = 1 + len(a)
    return _zeroreduce(_inplace_mul1(_zeroextend(a, n), x, 0, base)[1])
 
def _mul(a, b, base):
    if _iszero(b):
        return [0]
    return _add(_mul1(a, b[0], base), _mul(nshl(a, 1), nshr(b, 1), base),
                base, operator.add)
 
def nmul(a, s, b, t, base):
    return _fixsign(_mul(a, b, base), s != t)
 
# Divide.
 
def _divmodbase2(a, b):
    if len(a) < len(b):
        q, r = [0], a
    else:
        q, r = _divmodbase2(a, nshl(b, 1))
        q = nshl(q, 1)
        if ncmp(r, b) >= 0:
            q = _add(q, [1], 2, operator.add)
            r = _add(r, b, 2, operator.sub)
    return q, r
 
def _divmod(a, b, base):
    a = nton(a, base, 2)
    b = nton(b, base, 2)
    q, r = _divmodbase2(a, b)
    q = nton(q, 2, base)
    r = nton(r, 2, base)
    return q, r
 
def ndivmod(a, s, b, t, base):
    if _iszero(b):
        raise ZeroDivisionError
    q, r = _divmod(a, b, base)
    if s != t and not _iszero(r):
        q = _add(q, [1], base, operator.add)
        r = _add(b, r, base, operator.sub)
    return _fixsign(q, s != t), _fixsign(r, t)
 
# Test.
 
def _test(n, z, op, nozeroy=False):
    for x, y in itertools.product(z, repeat=2):
        if not nozeroy or y != 0:
            u = int(str(op(Num(x), Num(y))))
            v = op(x, y)
            assert u == v, f'{op}({x}, {y})\nExpected:{v}, Got:{u}'
    z = Num.base ** 3
    for _ in range(n):
        x = random.randint(-z, z)
        y = random.randint(-z, z)
        if not nozeroy or y != 0:
            u = int(str(op(Num(x), Num(y))))
            v = op(x, y)
            assert u == v, f'{op}({x}, {y})\nExpected:{v}, Got:{u}'
 
n = 1000
w = Num.base
z = (0, 1, -1, w, -w, w-1, 1-w)
_test(n, z, operator.add)
_test(n, z, operator.sub)
_test(n, z, operator.mul)
_test(n, z, operator.floordiv, True)
_test(n, z, operator.mod, True)
 
def show1(a):
    print(repr(a), a, sep='; ')
 
def _show(z, op, nozeroy=False):
    print(op)
    for x, y in itertools.product(z, repeat=2):
        if not nozeroy or y != 0:
            show1(op(Num(x), Num(y)))
 
w = Num.base
z = (0, 1, -1, w, -w)
_show(z, operator.add)
_show(z, operator.sub)
_show(z, operator.mul)
_show(z, operator.floordiv, True)
_show(z, operator.mod, True)
 
def factorial(n):
    r = Num(1)
    for i in range(2, n+1):
        r *= Num(i)
    return r
 
print(factorial)
for i in range(5):
    show1(factorial(10*i))

IyBAZmlsZSBiaWdudW0uMDA0LnB5CiMgQGluZ3JvdXAgZXhwZXJpbWVudGFsCiMgRXhwZXJpbWVudGFsIGJpZy1udW1iZXIgcmVwcmVzZW50YXRpb24uCiMgQGRhdGUgMTEvMjIvMjAyNAoKaW1wb3J0IGl0ZXJ0b29scwppbXBvcnQgb3BlcmF0b3IKaW1wb3J0IHJhbmRvbQoKY2xhc3MgTnVtOgogICAgYmFzZSA9IDIqKjgKCiAgICBkZWYgX19pbml0X18oc2VsZiwgaW5pdCk6CiAgICAgICAgaWYgaXNpbnN0YW5jZShpbml0LCB0dXBsZSk6CiAgICAgICAgICAgIHNlbGYubSA9IGluaXRbMF0KICAgICAgICAgICAgc2VsZi5zID0gaW5pdFsxXQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYubSA9IGl0b24oYWJzKGluaXQpLCBOdW0uYmFzZSkKICAgICAgICAgICAgc2VsZi5zID0gaW5pdCA8IDAKCiAgICBkZWYgX19uZWdfXyhzZWxmKToKICAgICAgICByZXR1cm4gTnVtKF9maXhzaWduKHNlbGYubS5jb3B5KCksIG5vdCBzZWxmLnMpKQoKICAgIGRlZiBfX2FkZF9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gTnVtKG5hZGQoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIG90aGVyLnMsIE51bS5iYXNlKSkKCiAgICBkZWYgX19zdWJfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgdCA9IF9maXhzaWduKG90aGVyLm0sIG5vdCBvdGhlci5zKVsxXQogICAgICAgIHJldHVybiBOdW0obmFkZChzZWxmLm0sIHNlbGYucywgb3RoZXIubSwgdCwgTnVtLmJhc2UpKQoKICAgIGRlZiBfX211bF9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gTnVtKG5tdWwoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIG90aGVyLnMsIE51bS5iYXNlKSkKCiAgICBkZWYgX19mbG9vcmRpdl9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gTnVtKG5kaXZtb2Qoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIG90aGVyLnMsIE51bS5iYXNlKVswXSkKCiAgICBkZWYgX19tb2RfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIE51bShuZGl2bW9kKHNlbGYubSwgc2VsZi5zLCBvdGhlci5tLCBvdGhlci5zLCBOdW0uYmFzZSlbMV0pCgogICAgZGVmIF9fc3RyX18oc2VsZik6CiAgICAgICAgcmV0dXJuICctJyAqIHNlbGYucyArIG50b3Moc2VsZi5tLCBOdW0uYmFzZSkKCiAgICBkZWYgX19yZXByX18oc2VsZik6CiAgICAgICAgcmV0dXJuIHN0cigoc2VsZi5tLCBzZWxmLnMpKQoKIyBVdGlsaXR5LgoKZGVmIF9pc3plcm8oYSk6CiAgICByZXR1cm4gbGVuKGEpID09IDEgYW5kIGFbMF0gPT0gMAoKZGVmIF9maXhzaWduKGEsIHMpOgogICAgcmV0dXJuIGEsIHMgYW5kIG5vdCBfaXN6ZXJvKGEpCgpkZWYgX3plcm9leHRlbmQoYSwgbik6CiAgICByZXR1cm4gYVs6XSArIFswXSAqIChuIC0gbGVuKGEpKQoKZGVmIF96ZXJvcmVkdWNlKGEpOgogICAgbiA9IGxlbihhKQogICAgd2hpbGUgbiAhPSAxIGFuZCBhW24tMV0gPT0gMDoKICAgICAgICBuIC09IDEKICAgIHJldHVybiBhWzpuXQoKZGVmIF9pbnBsYWNlX211bDEociwgeCwgYywgYik6CiAgICBmb3IgaSBpbiByYW5nZShsZW4ocikpOgogICAgICAgIGMsIHJbaV0gPSBkaXZtb2QocltpXSAqIHggKyBjLCBiKQogICAgcmV0dXJuIGMsIHIKCiMgQ29udmVydC4KCmRlZiBpdG9uKHgsIGIpOgogICAgciA9IFtdCiAgICB3aGlsZSBUcnVlOgogICAgICAgIHgsIHkgPSBkaXZtb2QoeCwgYikKICAgICAgICByLmFwcGVuZCh5KQogICAgICAgIGlmIHggPT0gMDoKICAgICAgICAgICAgcmV0dXJuIHIKCmRlZiBudG9uKGEsIGJpLCBibyk6CiAgICByID0gWzBdCiAgICBmb3IgeCBpbiByZXZlcnNlZChhKToKICAgICAgICBjID0gX2lucGxhY2VfbXVsMShyLCBiaSwgeCwgYm8pWzBdCiAgICAgICAgaWYgYyAhPSAwOgogICAgICAgICAgICByLmV4dGVuZChpdG9uKGMsIGJvKSkKICAgIHJldHVybiByCgpkZWYgbnRvcyhhLCBiKToKICAgIHJldHVybiAnJy5qb2luKG1hcChzdHIsIHJldmVyc2VkKG50b24oYSwgYiwgMTApKSkpCgojIENvbXBhcmUuCgpkZWYgX2NtcCh4LCB5KToKICAgIHJldHVybiAtMSBpZiB4IDwgeSBlbHNlIDEKCmRlZiBuY21wKGEsIGIpOgogICAgbiA9IGxlbihhKQogICAgbSA9IGxlbihiKQogICAgaWYgbiAhPSBtOgogICAgICAgIHJldHVybiBfY21wKG4sIG0pCiAgICBmb3IgeCwgeSBpbiB6aXAocmV2ZXJzZWQoYSksIHJldmVyc2VkKGIpKToKICAgICAgICBpZiB4ICE9IHk6CiAgICAgICAgICAgIHJldHVybiBfY21wKHgsIHkpCiAgICByZXR1cm4gMAoKIyBTaGlmdC4KCmRlZiBuc2hsKGEsIG4pOgogICAgcmV0dXJuIF96ZXJvcmVkdWNlKFswXSAqIG4gKyBhWzpdKQoKZGVmIG5zaHIoYSwgbik6CiAgICByZXR1cm4gX3plcm9leHRlbmQoYVtuOl0sIDEpCgojIEFkZC4KCmRlZiBfYWRkKGEsIGIsIGJhc2UsIG9wKToKICAgIG4gPSAxICsgbWF4KGxlbihhKSwgbGVuKGIpKQogICAgciA9IF96ZXJvZXh0ZW5kKGEsIG4pCiAgICBiID0gX3plcm9leHRlbmQoYiwgbikKICAgIGMgPSAwCiAgICBmb3IgaSBpbiByYW5nZShuKToKICAgICAgICBjLCByW2ldID0gZGl2bW9kKG9wKHJbaV0sIGJbaV0gKyBhYnMoYykpLCBiYXNlKQogICAgcmV0dXJuIF96ZXJvcmVkdWNlKHIpCgpkZWYgbmFkZChhLCBzLCBiLCB0LCBiYXNlKToKICAgIGlmIHMgPT0gdDoKICAgICAgICBvcCA9IG9wZXJhdG9yLmFkZAogICAgZWxzZToKICAgICAgICBvcCA9IG9wZXJhdG9yLnN1YgogICAgICAgIGlmIG5jbXAoYSwgYikgPCAwOgogICAgICAgICAgICBhLCBiLCBzID0gYiwgYSwgdAogICAgcmV0dXJuIF9maXhzaWduKF9hZGQoYSwgYiwgYmFzZSwgb3ApLCBzKQoKIyBNdWx0aXBseS4KCmRlZiBfbXVsMShhLCB4LCBiYXNlKToKICAgIG4gPSAxICsgbGVuKGEpCiAgICByZXR1cm4gX3plcm9yZWR1Y2UoX2lucGxhY2VfbXVsMShfemVyb2V4dGVuZChhLCBuKSwgeCwgMCwgYmFzZSlbMV0pCgpkZWYgX211bChhLCBiLCBiYXNlKToKICAgIGlmIF9pc3plcm8oYik6CiAgICAgICAgcmV0dXJuIFswXQogICAgcmV0dXJuIF9hZGQoX211bDEoYSwgYlswXSwgYmFzZSksIF9tdWwobnNobChhLCAxKSwgbnNocihiLCAxKSwgYmFzZSksCiAgICAgICAgICAgICAgICBiYXNlLCBvcGVyYXRvci5hZGQpCgpkZWYgbm11bChhLCBzLCBiLCB0LCBiYXNlKToKICAgIHJldHVybiBfZml4c2lnbihfbXVsKGEsIGIsIGJhc2UpLCBzICE9IHQpCgojIERpdmlkZS4KCmRlZiBfZGl2bW9kYmFzZTIoYSwgYik6CiAgICBpZiBsZW4oYSkgPCBsZW4oYik6CiAgICAgICAgcSwgciA9IFswXSwgYQogICAgZWxzZToKICAgICAgICBxLCByID0gX2Rpdm1vZGJhc2UyKGEsIG5zaGwoYiwgMSkpCiAgICAgICAgcSA9IG5zaGwocSwgMSkKICAgICAgICBpZiBuY21wKHIsIGIpID49IDA6CiAgICAgICAgICAgIHEgPSBfYWRkKHEsIFsxXSwgMiwgb3BlcmF0b3IuYWRkKQogICAgICAgICAgICByID0gX2FkZChyLCBiLCAyLCBvcGVyYXRvci5zdWIpCiAgICByZXR1cm4gcSwgcgoKZGVmIF9kaXZtb2QoYSwgYiwgYmFzZSk6CiAgICBhID0gbnRvbihhLCBiYXNlLCAyKQogICAgYiA9IG50b24oYiwgYmFzZSwgMikKICAgIHEsIHIgPSBfZGl2bW9kYmFzZTIoYSwgYikKICAgIHEgPSBudG9uKHEsIDIsIGJhc2UpCiAgICByID0gbnRvbihyLCAyLCBiYXNlKQogICAgcmV0dXJuIHEsIHIKCmRlZiBuZGl2bW9kKGEsIHMsIGIsIHQsIGJhc2UpOgogICAgaWYgX2lzemVybyhiKToKICAgICAgICByYWlzZSBaZXJvRGl2aXNpb25FcnJvcgogICAgcSwgciA9IF9kaXZtb2QoYSwgYiwgYmFzZSkKICAgIGlmIHMgIT0gdCBhbmQgbm90IF9pc3plcm8ocik6CiAgICAgICAgcSA9IF9hZGQocSwgWzFdLCBiYXNlLCBvcGVyYXRvci5hZGQpCiAgICAgICAgciA9IF9hZGQoYiwgciwgYmFzZSwgb3BlcmF0b3Iuc3ViKQogICAgcmV0dXJuIF9maXhzaWduKHEsIHMgIT0gdCksIF9maXhzaWduKHIsIHQpCgojIFRlc3QuCgpkZWYgX3Rlc3Qobiwgeiwgb3AsIG5vemVyb3k9RmFsc2UpOgogICAgZm9yIHgsIHkgaW4gaXRlcnRvb2xzLnByb2R1Y3QoeiwgcmVwZWF0PTIpOgogICAgICAgIGlmIG5vdCBub3plcm95IG9yIHkgIT0gMDoKICAgICAgICAgICAgdSA9IGludChzdHIob3AoTnVtKHgpLCBOdW0oeSkpKSkKICAgICAgICAgICAgdiA9IG9wKHgsIHkpCiAgICAgICAgICAgIGFzc2VydCB1ID09IHYsIGYne29wfSh7eH0sIHt5fSlcbkV4cGVjdGVkOnt2fSwgR290Ont1fScKICAgIHogPSBOdW0uYmFzZSAqKiAzCiAgICBmb3IgXyBpbiByYW5nZShuKToKICAgICAgICB4ID0gcmFuZG9tLnJhbmRpbnQoLXosIHopCiAgICAgICAgeSA9IHJhbmRvbS5yYW5kaW50KC16LCB6KQogICAgICAgIGlmIG5vdCBub3plcm95IG9yIHkgIT0gMDoKICAgICAgICAgICAgdSA9IGludChzdHIob3AoTnVtKHgpLCBOdW0oeSkpKSkKICAgICAgICAgICAgdiA9IG9wKHgsIHkpCiAgICAgICAgICAgIGFzc2VydCB1ID09IHYsIGYne29wfSh7eH0sIHt5fSlcbkV4cGVjdGVkOnt2fSwgR290Ont1fScKCm4gPSAxMDAwCncgPSBOdW0uYmFzZQp6ID0gKDAsIDEsIC0xLCB3LCAtdywgdy0xLCAxLXcpCl90ZXN0KG4sIHosIG9wZXJhdG9yLmFkZCkKX3Rlc3Qobiwgeiwgb3BlcmF0b3Iuc3ViKQpfdGVzdChuLCB6LCBvcGVyYXRvci5tdWwpCl90ZXN0KG4sIHosIG9wZXJhdG9yLmZsb29yZGl2LCBUcnVlKQpfdGVzdChuLCB6LCBvcGVyYXRvci5tb2QsIFRydWUpCgpkZWYgc2hvdzEoYSk6CiAgICBwcmludChyZXByKGEpLCBhLCBzZXA9JzsgJykKCmRlZiBfc2hvdyh6LCBvcCwgbm96ZXJveT1GYWxzZSk6CiAgICBwcmludChvcCkKICAgIGZvciB4LCB5IGluIGl0ZXJ0b29scy5wcm9kdWN0KHosIHJlcGVhdD0yKToKICAgICAgICBpZiBub3Qgbm96ZXJveSBvciB5ICE9IDA6CiAgICAgICAgICAgIHNob3cxKG9wKE51bSh4KSwgTnVtKHkpKSkKCncgPSBOdW0uYmFzZQp6ID0gKDAsIDEsIC0xLCB3LCAtdykKX3Nob3coeiwgb3BlcmF0b3IuYWRkKQpfc2hvdyh6LCBvcGVyYXRvci5zdWIpCl9zaG93KHosIG9wZXJhdG9yLm11bCkKX3Nob3coeiwgb3BlcmF0b3IuZmxvb3JkaXYsIFRydWUpCl9zaG93KHosIG9wZXJhdG9yLm1vZCwgVHJ1ZSkKCmRlZiBmYWN0b3JpYWwobik6CiAgICByID0gTnVtKDEpCiAgICBmb3IgaSBpbiByYW5nZSgyLCBuKzEpOgogICAgICAgIHIgKj0gTnVtKGkpCiAgICByZXR1cm4gcgoKcHJpbnQoZmFjdG9yaWFsKQpmb3IgaSBpbiByYW5nZSg1KToKICAgIHNob3cxKGZhY3RvcmlhbCgxMCppKSk=