fork(1) download
copy 
  1. # (3)
  2. # @see 6SDvDi
  3.  
  4. import operator
  5.  
  6. class Num:
  7.     def __init__(self, init=0):
  8.         self.s = init < 0
  9.         self.m = iton(abs(init))
  10.  
  11.     def __neg__(self):
  12.         self.s = not self.s
  13.         return self
  14.  
  15.     def __add__(self, other):
  16.         self.m, self.s = nadd(self.m, self.s, other.m, other.s)
  17.         return self
  18.  
  19.     def __sub__(self, other):
  20.         self.m, self.s = nadd(self.m, self.s, other.m, not other.s)
  21.         return self
  22.  
  23.     def __mul__(self, other):
  24.         self.m, self.s = nmul(self.m, self.s, other.m, other.s)
  25.         return self
  26.  
  27.     def __str__(self):
  28.         return '-' * self.s + ntos(self.m)
  29.  
  30.     def __repr__(self):
  31.         return str(self.s) + ':' + str(self.m)
  32.  
  33. # Utility.
  34.  
  35. def _iszero(a):
  36.     return len(a) == 1 and a[0] == 0
  37.  
  38. def _fixsign(a, s):
  39.     return a, False if _iszero(a) else s
  40.  
  41. def _zeroextend(a, n):
  42.     return a[:] + [0] * (n - len(a))
  43.  
  44. def _zeroreduce(a):
  45.     n = len(a)
  46.     while n != 1 and a[n-1] == 0:
  47.         n -= 1
  48.     return a[:n]
  49.  
  50. # Conversion.
  51.  
  52. def iton(x):
  53.     r = []
  54.     while True:
  55.         x, y = divmod(x, 10)
  56.         r.append(y)
  57.         if x == 0:
  58.             return r
  59.  
  60. def ntos(a):
  61.     return ''.join(map(str, reversed(a)))
  62.  
  63. # Compare.
  64.  
  65. def _cmp(x, y):
  66.     if x != y:
  67.         return -1 if x < y else 1
  68.     return 0
  69.  
  70. def ncmp(a, b):
  71.     n = len(a)
  72.     m = len(b)
  73.     if n != m:
  74.         return _cmp(n, m)
  75.     for x, y in zip(reversed(a), reversed(b)):
  76.         if x != y:
  77.             return _cmp(x, y)
  78.     return 0
  79.  
  80. # Shift.
  81.  
  82. def nshl(a, n):
  83.     return _zeroreduce([0] * n + a[:])
  84.  
  85. def nshr(a, n):
  86.     return _zeroextend(a[n:], 1)
  87.  
  88. # Add.
  89.  
  90. def _add(a, b, op):
  91.     n = 1 + max(len(a), len(b))
  92.     r = _zeroextend(a, n)
  93.     b = _zeroextend(b, n)
  94.     c = 0
  95.     for i in range(n):
  96.         c, r[i] = divmod(op(r[i], b[i] + abs(c)), 10)
  97.     return _zeroreduce(r)
  98.  
  99. def nadd(a, s, b, t):
  100.     if s == t:
  101.         return _fixsign(_add(a, b, operator.add), s)
  102.     elif ncmp(a, b) < 0:
  103.         return _fixsign(_add(b, a, operator.sub), t)
  104.     else:
  105.         return _fixsign(_add(a, b, operator.sub), s)
  106.  
  107. # Multiply.
  108.  
  109. def _mul1(a, x):
  110.     assert 0 <= x < 10
  111.     n = 1 + len(a)
  112.     r = _zeroextend(a, n)
  113.     c = 0
  114.     for i in range(n):
  115.         c, r[i] = divmod(r[i] * x + c, 10)
  116.     return _zeroreduce(r)
  117.  
  118. def _mul(a, b):
  119.     if _iszero(b):
  120.         return [0]
  121.     return _add(_mul1(a, b[0]), _mul(nshl(a, 1), nshr(b, 1)), operator.add)
  122.  
  123. def nmul(a, s, b, t):
  124.     return _fixsign(_mul(a, b), s != t)
  125.  
  126. # Test.
  127.  
  128. n = 50
  129. for x in range(-n, n+1):
  130.     for y in range(-n, n+1):
  131.         # nadd
  132.         u = int(str(Num(x) + Num(y)))
  133.         v = x + y
  134.         assert u == v, f'{x} + {y}; {u}, {v}'
  135.         # nmul
  136.         u = int(str(Num(x) * Num(y)))
  137.         v = x * y
  138.         assert u == v, f'{x} * {y}; {u}, {v}'
  139.  
  140. def show(a):
  141.     print(repr(a), a, sep='; ')
  142.  
  143. x = 123
  144. show(Num( 0))
  145. show(Num( 1))
  146. show(Num(-1))
  147. show(Num( x))
  148. show(Num(-x))
  149. print('+')
  150. show(Num(0) + Num(0))
  151. show(Num(0) + Num(1))
  152. show(Num(1) + Num(0))
  153. show(Num(1) + Num(x))
  154. show(Num(x) + Num(1))
  155. show(Num(x) + Num(x))
  156. print('-')
  157. show(Num(0) - Num(0))
  158. show(Num(0) - Num(1))
  159. show(Num(1) - Num(0))
  160. show(Num(1) - Num(x))
  161. show(Num(x) - Num(1))
  162. show(Num(x) - Num(x))
  163. print('*')
  164. show(Num(0) * Num(0))
  165. show(Num(0) * Num(1))
  166. show(Num(1) * Num(0))
  167. show(Num(1) * Num(x))
  168. show(Num(x) * Num(1))
  169. show(Num(x) *-Num(1))
  170. show(Num(x) * Num(x))
  171. show(Num(x) *-Num(x))
Success #stdin #stdout 0.37s 9904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
False:[0]; 0
False:[1]; 1
True:[1]; -1
False:[3, 2, 1]; 123
True:[3, 2, 1]; -123
+
False:[0]; 0
False:[1]; 1
False:[1]; 1
False:[4, 2, 1]; 124
False:[4, 2, 1]; 124
False:[6, 4, 2]; 246
-
False:[0]; 0
True:[1]; -1
False:[1]; 1
True:[2, 2, 1]; -122
False:[2, 2, 1]; 122
False:[0]; 0
*
False:[0]; 0
False:[0]; 0
False:[0]; 0
False:[3, 2, 1]; 123
False:[3, 2, 1]; 123
True:[3, 2, 1]; -123
False:[9, 2, 1, 5, 1]; 15129
True:[9, 2, 1, 5, 1]; -15129
https://ideone.com/kuVRVb
language:
Python 3 (python  3.9.5)
created:
6 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!