DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
intmod.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.intmod Entiers modulo k (éléments de \htmlonly &#8484;<sub>k</sub>\endhtmlonly)
4 
5 ##\file
6 # Entiers modulo k (éléments de \htmlonly &#8484;<sub>k</sub>\endhtmlonly)
7 
8 # (c) Olivier Pirson --- DragonSoft
9 # http://www.opimedia.be/DS/
10 # Débuté le 12 décembre 2009
11 ####################################
12 from __future__ import division
13 from __future__ import print_function
14 
15 ## Date du dernier changement pour ce module
16 VERSION = 'intmod --- 2010 March 16'
17 
18 import numbers
19 
20 import DSPython
21 
22 
23 
24 # ########
25 # Classe #
26 ##########
27 ##\brief Type nombre entier modulo k
28 # \htmlonly(c.-à-d.\endhtmlonly un élément de \htmlonly&#8484;<sub>k</sub>\endhtmlonly)
29 class Intmod(int):
30  """Type nombre entier modulo k (c.-à-d. un élément de Z_k) :
31  0, 1, 2, &hellip;, k-1"""
32 
33  ## Crée l'élément
34  def __new__(cls, value, k, base=10):
35  """Crée l'élément
36 
37  Pre: value: Integral ou String
38  k: Integral >= 1"""
39  assert isinstance(value, numbers.Integral) or isinstance(value, str), value
40  assert DSPython.natural_is(k), k
41  assert k >= 1, k
42 
43  if isinstance(value, str):
44  value = int(value, base=base)
45 
46  assert isinstance(value, numbers.Integral), value
47 
48  return int.__new__(cls, value%k)
49 
50 
51  ## Initialise l'élément à self%k
52  def __init__(self, value, k):
53  """Initialise l'élément à self%k
54 
55  Pre: value: Integral ou String
56  k: Integral >= 1"""
57  assert isinstance(value, numbers.Integral) or isinstance(value, str), value
58  assert DSPython.natural_is(k), k
59  assert k >= 1, k
60 
61  self._k = k
62 
63 
64 
65  ## Renvoie self + other
66  def __add__(self, other):
67  """Renvoie self + other (modulo self.k())
68 
69  Pre: other: Intmod ou Integral
70 
71  Result: Intmod(, k=self.k())"""
72  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
73 
74  return Intmod(int.__add__(self, other), self._k)
75 
76 
77  ## Renvoie le naturel correspondant à la valeur self
78  def __int__(self):
79  """Renvoie le naturel correspondant à la valeur self
80 
81  Result: Integral < self.k()"""
82  return int.__int__(self)
83 
84 
85  ## Renvoie ~self
86  def __invert__(self):
87  """Renvoie ~self (modulo self.k())
88 
89  Result: Intmod(, k=self.k())"""
90  return Intmod(int.__invert__(self), self._k)
91 
92 
93  ## Renvoie self<<other
94  def __lshift__(self, other):
95  """Renvoie self<<other (modulo self.k())
96 
97  Pre: other: Intmod ou (Integral >= 0)
98 
99  Result: Intmod(, k=self.k())"""
100  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
101 
102  return Intmod(int.__lshift__(self, other), self._k)
103 
104 
105  ## Renvoie self*other
106  def __mul__(self, other):
107  """Renvoie self*other (modulo self.k())
108 
109  Pre: other: Intmod ou Integral
110 
111  Result: Intmod(, k=self.k())"""
112  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
113 
114  return Intmod(int.__mul__(self, other), self._k)
115 
116 
117  ## Renvoie -self
118  def __neg__(self):
119  """Renvoie -self (modulo self.k())
120 
121  Result: Intmod(, k=self.k())"""
122  return Intmod(int.__neg__(self), self._k)
123 
124 
125  ## Renvoie self | other
126  def __or__(self, other):
127  """Renvoie self | other (modulo self.k())
128 
129  Pre: other: Intmod ou Integral
130 
131  Result: Intmod(, k=self.k())"""
132  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
133 
134  return Intmod(int.__or__(self, other), self._k)
135 
136 
137  ## Renvoie self**other
138  def __pow__(self, other):
139  """Renvoie self**other (modulo self.k())
140 
141  Pre: other: Intmod ou Integral
142 
143  Result: Intmod(, k=self.k())"""
144  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
145 
146  return Intmod(int.__pow__(self, (other if isinstance(other, Intmod) or (other >= 0)
147  else self._k - other), self._k), self._k)
148 
149 
150  ## Renvoie self - other
151  def __sub__(self, other):
152  """Renvoie self - other (modulo self.k())
153 
154  Pre: other: Intmod ou Integral
155 
156  Result: Intmod(, k=self.k())"""
157  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
158 
159  return Intmod(int.__sub__(self, other), self._k)
160 
161 
162  ## Renvoie self ^ other
163  def __xor__(self, other):
164  """Renvoie self ^ other (modulo self.k())
165 
166  Pre: other: Intmod ou Integral
167 
168  Result: Intmod(, k=self.k())"""
169  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
170 
171  return Intmod(int.__xor__(self, other), self._k)
172 
173 
174  ## Renvoie la valeur du modulo k
175  def k(self):
176  """Renvoie la valeur du modulo k
177 
178  Result: Integral >= 1"""
179  return self._k
180 
181 
182 #__i...__ ???
183 #__r...__ ???
184 
185  ## Renvoie (self//other, self%other)
186  def __divmod__(self, other):
187  """Renvoie (self//other, self%other) (modulo self.k())
188 
189  Pre: other: Intmod ou Integral
190 
191  Result: NotImplemented"""
192  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
193 
194  return NotImplemented
195 
196 
197  ## Renvoie self//other
198  def __floordiv__(self, other):
199  """Renvoie self//other (modulo self.k())
200 
201  Pre: other: Intmod ou Integral
202 
203  Result: NotImplemented"""
204  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
205 
206  return NotImplemented
207 
208 
209  ## Renvoie self%other
210  def __mod__(self, other):
211  """Renvoie self%other (modulo self.k())
212 
213  Pre: other: Intmod ou Integral
214 
215  Result: NotImplemented"""
216  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
217 
218  return NotImplemented
219 
220 
221  ## Renvoie NotImplemented
222  def __truediv__(self, other):
223  """Renvoie NotImplemented
224 
225  Pre: other: Intmod ou Integral
226 
227  Result: NotImplemented"""
228  assert isinstance(other, Intmod) or isinstance(other, numbers.Integral), other
229 
230  return NotImplemented
231 
232 
233 
234 # ######\cond MAINTEST
235 # Main #
236 ########
237 if __name__ == '__main__':
238  def main_test():
239  """Test du module"""
240  import sys
241 
242  import DSPython.debug as debug
243 
244  debug.test_begin(VERSION, __debug__)
245 
246  print('Intmod()...', end='') ; sys.stdout.flush()
247  for k in range(1, 11):
248  for n in range(-k*2, k*3):
249  a = Intmod(n, k)
250  assert a._k == k, (k, n, a, a_k)
251  assert int(a) == n%k, (k, n, a, int(a))
252  print('ok') ; sys.stdout.flush()
253 
254 
255  print('Intmod.__add__()...', end='') ; sys.stdout.flush()
256  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
257  for a in range(-k*2, k*3):
258  a = Intmod(a, k)
259  for b in range(-k, k*2):
260  b = Intmod(b, k)
261 
262  assert a + b == int(a + b)%k, (k, a, b, a + b, int(a + b)%k)
263  assert a + b == b + a, (k, a, b)
264  for b in range(-k, k*2):
265  assert a + b == int(a + b)%k, (k, a, b, a + b, int(a + b)%k)
266  print('ok') ; sys.stdout.flush()
267 
268 
269  print('Intmod.__and__()...', end='') ; sys.stdout.flush()
270  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
271  for a in range(-k*2, k*3):
272  a = Intmod(a, k)
273  for b in range(-k, k*2):
274  b = Intmod(b, k)
275 
276  assert a & b == int(a & b)%k, (k, a, b, a & b, int(a & b)%k)
277  assert a & b == b & a, (k, a, b)
278  for b in range(-k, k*2):
279  assert a & b == int(a & b)%k, (k, a, b, a & b, int(a & b)%k)
280  print('ok') ; sys.stdout.flush()
281 
282 
283  print('Intmod.__divmod__()...', end='') ; sys.stdout.flush()
284  for k in range(1, 5):
285  for a in range(-k*2, k*2):
286  a = Intmod(a, k)
287  for b in range(-k, k*2):
288  b = Intmod(b, k)
289  try:
290  assert divmod(a, b), (k, a, b)
291  except TypeError:
292  pass
293  print('ok') ; sys.stdout.flush()
294 
295 
296  print('Intmod.__floordiv__()...', end='') ; sys.stdout.flush()
297  for k in range(1, 5):
298  for a in range(-k*2, k*2):
299  a = Intmod(a, k)
300  for b in range(-k, k*2):
301  b = Intmod(b, k)
302  try:
303  assert a//b, (k, a, b)
304  except TypeError:
305  pass
306  print('ok') ; sys.stdout.flush()
307 
308 
309  print('Intmod.__int__()...', end='') ; sys.stdout.flush()
310  for k in range(1, 11):
311  for n in range(-k*2, k*3):
312  a = Intmod(n, k)
313  assert a == n%k, (k, n, a)
314  print('ok') ; sys.stdout.flush()
315 
316 
317  print('Intmod.__invert__()...', end='') ; sys.stdout.flush()
318  for k in range(1, 11):
319  for a in range(-k*2, k*3):
320  a = Intmod(a, k)
321  assert ~a == int(~a)%k, (k, a, ~a, int(~a)%k)
322  print('ok') ; sys.stdout.flush()
323 
324 
325  print('Intmod.__lshift__()...', end='') ; sys.stdout.flush()
326  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
327  for a in range(-k*2, k*3):
328  a = Intmod(a, k)
329  for b in range(-k, k*2):
330  b = Intmod(b, k)
331 
332  assert a<<b == int(a<<b)%k, (k, a, b, a<<b, int(a<<b)%k)
333  for b in range(k*2):
334  assert a<<b == int(a<<b)%k, (k, a, b, a<<b, int(a<<b)%k)
335  print('ok') ; sys.stdout.flush()
336 
337 
338  print('Intmod.__mod__()...', end='') ; sys.stdout.flush()
339  for k in range(1, 5):
340  for a in range(-k*2, k*2):
341  a = Intmod(a, k)
342  for b in range(-k, k*2):
343  b = Intmod(b, k)
344  try:
345  assert a%b, (k, a, b)
346  except TypeError:
347  pass
348  print('ok') ; sys.stdout.flush()
349 
350 
351  print('Intmod.__mul__()...', end='') ; sys.stdout.flush()
352  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
353  for a in range(-k*2, k*3):
354  a = Intmod(a, k)
355  for b in range(-k, k*2):
356  b = Intmod(b, k)
357 
358  assert a*b == int(a*b)%k, (k, a, b, a*b, int(a*b)%k)
359  assert a*b == b*a, (k, a, b)
360  for b in range(-k, k*2):
361  assert a*b == int(a*b)%k, (k, a, b, a*b, int(a*b)%k)
362  print('ok') ; sys.stdout.flush()
363 
364 
365  print('Intmod.__neg__()...', end='') ; sys.stdout.flush()
366  for k in range(1, 11):
367  for a in range(-k*2, k*3):
368  a = Intmod(a, k)
369  assert -a == int(-a)%k, (k, a, -a, int(-a)%k)
370  print('ok') ; sys.stdout.flush()
371 
372 
373  print('Intmod.__or__()...', end='') ; sys.stdout.flush()
374  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
375  for a in range(-k*2, k*3):
376  a = Intmod(a, k)
377  for b in range(-k, k*2):
378  b = Intmod(b, k)
379 
380  assert a | b == int(a | b)%k, (k, a, b, a | b, int(a | b)%k)
381  assert a | b == b | a, (k, a, b)
382  for b in range(-k, k*2):
383  assert a | b == int(a | b)%k, (k, a, b, a | b, int(a | b)%k)
384  print('ok') ; sys.stdout.flush()
385 
386 
387  print('Intmod.__pow__()...', end='') ; sys.stdout.flush()
388  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
389  for a in range(-k*2, k*3):
390  a = Intmod(a, k)
391  for b in range(-k, k*2):
392  b = Intmod(b, k)
393 
394  assert a**b == int(a**b)%k, (k, a, b, a**b, int(a**b)%k)
395  for b in range(-k, k*2):
396  assert a**b == int(a**b)%k, (k, a, b, a**b, int(a**b)%k)
397  print('ok') ; sys.stdout.flush()
398 
399 
400  print('Intmod.__rshift__()...', end='') ; sys.stdout.flush()
401  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
402  for a in range(-k*2, k*3):
403  a = Intmod(a, k)
404  for b in range(-k, k*2):
405  b = Intmod(b, k)
406 
407  assert a>>b == int(a>>b)%k, (k, a, b, a>>b, int(a>>b)%k)
408  for b in range(k*2):
409  assert a>>b == int(a>>b)%k, (k, a, b, a>>b, int(a>>b)%k)
410  print('ok') ; sys.stdout.flush()
411 
412 
413  print('Intmod.__str__()...', end='') ; sys.stdout.flush()
414  for k in range(1, 11):
415  for n in range(-k*2, k*3):
416  a = Intmod(n, k)
417  assert str(a) == str(n%k), (k, n, str(a))
418  print('ok') ; sys.stdout.flush()
419 
420 
421  print('Intmod.__sub__()...', end='') ; sys.stdout.flush()
422  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
423  for a in range(-k*2, k*3):
424  a = Intmod(a, k)
425  for b in range(-k, k*2):
426  b = Intmod(b, k)
427 
428  assert a - b == int(a - b)%k, (k, a, b, a - b, int(a - b)%k)
429  assert a - b == -(b - a), (k, a, b)
430  for b in range(-k, k*2):
431  assert a - b == int(a - b)%k, (k, a, b, a - b, int(a - b)%k)
432  print('ok') ; sys.stdout.flush()
433 
434 
435  print('Intmod.__truediv__()...', end='') ; sys.stdout.flush()
436  for k in range(1, 5):
437  for a in range(-k*2, k*2):
438  a = Intmod(a, k)
439  for b in range(-k, k*2):
440  b = Intmod(b, k)
441  try:
442  assert a/b, (k, a, b)
443  except TypeError:
444  pass
445  print('ok') ; sys.stdout.flush()
446 
447 
448  print('Intmod.__xor__()...', end='') ; sys.stdout.flush()
449  for k in range(1, 11 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
450  for a in range(-k*2, k*3):
451  a = Intmod(a, k)
452  for b in range(-k, k*2):
453  b = Intmod(b, k)
454 
455  assert a ^ b == int(a ^ b)%k, (k, a, b, a ^ b, int(a ^ b)%k)
456  assert a ^ b == b ^ a, (k, a, b)
457  for b in range(-k, k*2):
458  assert a ^ b == int(a ^ b)%k, (k, a, b, a ^ b, int(a ^ b)%k)
459  print('ok') ; sys.stdout.flush()
460 
461 
462  print('Intmod.k()...', end='') ; sys.stdout.flush()
463  for k in range(1, 11):
464  for a in range(-k*2, k*3):
465  a = Intmod(a, k)
466  assert a.k() == k, (k, a, a.k())
467  print('ok') ; sys.stdout.flush()
468  debug.test_end()
469 
470  main_test()
471 ##\endcond MAINTEST