fork(1) download
copy 
  1. # (1).
  2. # @see 6SDvDi
  3.  
  4. # Conversion.
  5.  
  6. def iton(x):
  7.     r = []
  8.     while True:
  9.         x, y = divmod(x, 10)
  10.         r.append(y)
  11.         if x == 0:
  12.             return r
  13.  
  14. def ntos(a):
  15.     return ''.join(map(str, reversed(a)))
  16.  
  17. # Math.
  18.  
  19. def _iszero(a):
  20.     return len(a) == 1 and a[0] == 0
  21.  
  22. def _zeroextend(a, n):
  23.     return a[:] + [0] * (n - len(a))
  24.  
  25. def _zeroreduce(a):
  26.     n = len(a)
  27.     while n != 1 and a[n-1] == 0:
  28.         n -= 1
  29.     return a[:n]
  30.  
  31. def nshl(a, n):
  32.     return _zeroreduce([0] * n + a[:])
  33.  
  34. def nshr(a, n):
  35.     return _zeroextend(a[n:], 1)
  36.  
  37. def nadd(a, b):
  38.     n = 1 + max(len(a), len(b))
  39.     r = _zeroextend(a, n)
  40.     b = _zeroextend(b, n)
  41.     c = 0
  42.     for i in range(n):
  43.         c, r[i] = divmod(r[i] + b[i] + c, 10)
  44.     return _zeroreduce(r)
  45.  
  46. def nmul(a, b):
  47.     if _iszero(b):
  48.         return [0]
  49.     if b[0] == 0:
  50.         return nmul(nshl(a, 1), nshr(b, 1))
  51.     return nadd(a, nmul(a, nadd(b, [-1])))
  52.  
  53. # Test.
  54.  
  55. n = 50
  56. for x in range(0, n+1):
  57.     for y in range(0, n+1):
  58.         # nadd
  59.         u = int(ntos(nadd(iton(x), iton(y))))
  60.         v = x + y
  61.         assert u == v, f'{x} + {y}; {u}, {v}'
  62.         # nmul
  63.         u = int(ntos(nmul(iton(x), iton(y))))
  64.         v = x * y
  65.         assert u == v, f'{x} * {y}; {u}, {v}'
  66.  
  67. def show(y):
  68.     return y, ntos(y)
  69.  
  70. x = 123
  71. print(show(iton(0)))
  72. print(show(iton(1)))
  73. print(show(iton(x)))
  74. print('-')
  75. print(show(nadd(iton(0), iton(0))))
  76. print(show(nadd(iton(1), iton(1))))
  77. print(show(nadd(iton(x), iton(x))))
  78. print('-')
  79. print(show(nmul(iton(0), iton(0))))
  80. print(show(nmul(iton(0), iton(1))))
  81. print(show(nmul(iton(1), iton(0))))
  82. print(show(nmul(iton(1), iton(1))))
  83. print(show(nmul(iton(x), iton(1))))
  84. print(show(nmul(iton(1), iton(x))))
  85. print(show(nmul(iton(x), iton(x))))
  86. print(show(nmul(iton(x), iton(x*x))))
  87. print(show(nmul(iton(x*x), iton(x))))
Success #stdin #stdout 0.12s 9796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
([0], '0')
([1], '1')
([3, 2, 1], '123')
-
([0], '0')
([2], '2')
([6, 4, 2], '246')
-
([0], '0')
([0], '0')
([0], '0')
([1], '1')
([3, 2, 1], '123')
([3, 2, 1], '123')
([9, 2, 1, 5, 1], '15129')
([7, 6, 8, 0, 6, 8, 1], '1860867')
([7, 6, 8, 0, 6, 8, 1], '1860867')
https://ideone.com/bOJ7Zy
language:
Python 3 (python  3.9.5)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!