NZMATH  1.2.0 About: NZMATH is a Python based number theory oriented calculation system. Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation) rational.py
Go to the documentation of this file.
1 """
2 rational module provides Rational, Integer, RationalField, and IntegerRing.
3 """
4
5 import nzmath.gcd as gcd
6 import nzmath.ring as ring
7 from nzmath.plugins import MATHMODULE as math, FLOATTYPE as Float
8
9
11  """
12  Rational is the class of rational numbers.
13  """
14
15  def __init__(self, numerator, denominator=1):
16  """
17  Create a rational from:
18  * integers,
19  * float, or
20  * Rational.
21  Other objects can be converted if they have toRational
22  methods. Otherwise raise TypeError.
23  """
24  if not denominator:
25  raise ZeroDivisionError
26  # numerator
27  integer = (int, long)
28  initDispatcher = {
29  (Rational, Rational): Rational._init_by_Rational_Rational,
30  (float, Rational): Rational._init_by_float_Rational,
31  (integer, Rational): Rational._init_by_int_Rational,
32  (Rational, float): Rational._init_by_Rational_float,
33  (float, float): Rational._init_by_float_float,
34  (integer, float): Rational._init_by_int_float,
35  (Rational, integer): Rational._init_by_Rational_int,
36  (float, integer): Rational._init_by_float_int,
37  (integer, integer): Rational._init_by_int_int,
38  }
39  if not isinstance(numerator, (Rational, float, int, long)):
40  if hasattr(numerator, "toRational"):
41  numerator = numerator.toRational()
42  elif hasattr(numerator, "__pos__"):
43  numerator = +numerator
44  if not isinstance(denominator, (Rational, float, int, long)):
45  if hasattr(denominator, "toRational"):
46  denominator = denominator.toRational()
47  elif hasattr(numerator, "__pos__"):
48  denominator = +denominator
49  for (t1, t2) in initDispatcher:
50  if isinstance(numerator, t1) and isinstance(denominator, t2):
51  initDispatcher[(t1, t2)](self, numerator, denominator)
52  break
53  else:
54  try:
55  cfe = continued_fraction_expansion(numerator / denominator, 50)
56  approx0 = Rational(cfe)
57  approx1 = Rational(cfe * cfe + 1, cfe)
58  for q in cfe[2:]:
59  approx0, approx1 = approx1, Rational(q * approx1.numerator + approx0.numerator, q * approx1.denominator + approx0.denominator)
60  self.numerator, self.denominator = approx1.numerator, approx1.denominator
61  return
62  except Exception:
63  # maybe some type could raise strange error ...
64  pass
65  raise TypeError("Rational cannot be created with %s(%s) and %s(%s)." % (numerator, numerator.__class__, denominator, denominator.__class__))
66  self._reduce()
67
69  """
70  self + other
71
72  If other is a rational or an integer, the result will be a
73  rational. If other is a kind of float the result is an
74  instance of other's type. Otherwise, other would do the
75  computation.
76  """
77  if isinstance(other, Rational):
78  numerator = self.numerator*other.denominator + self.denominator*other.numerator
79  denominator = self.denominator*other.denominator
80  return +Rational(numerator, denominator)
81  elif isIntegerObject(other):
82  numerator = self.numerator + self.denominator*other
83  denominator = self.denominator
84  return +Rational(numerator, denominator)
85  elif isinstance(other, Float):
86  return self.toFloat() + other
87  elif isinstance(other, float):
88  return float(self) + other
89  else:
90  return NotImplemented
91
92  def __sub__(self, other):
93  """
94  self - other
95
96  If other is a rational or an integer, the result will be a
97  rational. If other is a kind of float the result is an
98  instance of other's type. Otherwise, other would do the
99  computation.
100  """
101  if isinstance(other, Rational):
102  numerator = self.numerator*other.denominator - self.denominator*other.numerator
103  denominator = self.denominator*other.denominator
104  return +Rational(numerator, denominator)
105  elif isIntegerObject(other):
106  numerator = self.numerator - self.denominator*other
107  denominator = self.denominator
108  return +Rational(numerator, denominator)
109  elif isinstance(other, Float):
110  return self.toFloat() - other
111  elif isinstance(other, float):
112  return float(self) - other
113  else:
114  return NotImplemented
115
116  def __mul__(self, other):
117  """
118  self * other
119
120  If other is a rational or an integer, the result will be a
121  rational. If other is a kind of float the result is an
122  instance of other's type. Otherwise, other would do the
123  computation.
124  """
125  if isinstance(other, Rational):
126  numerator = self.numerator*other.numerator
127  denominator = self.denominator*other.denominator
128  return +Rational(numerator, denominator)
129  elif isIntegerObject(other):
130  numerator = self.numerator*other
131  denominator = self.denominator
132  return +Rational(numerator, denominator)
133  elif isinstance(other, Float):
134  return self.toFloat() * other
135  elif isinstance(other, float):
136  return float(self) * other
137  else:
138  return NotImplemented
139
140  def __truediv__(self, other):
141  """
142  self / other
143  self // other
144
145  If other is a rational or an integer, the result will be a
146  rational. If other is a kind of float the result is an
147  instance of other's type. Otherwise, other would do the
148  computation.
149  """
150  if isinstance(other, Rational):
151  numerator = self.numerator*other.denominator
152  denominator = self.denominator*other.numerator
153  return +Rational(numerator, denominator)
154  elif isIntegerObject(other):
155  q, r = divmod(self.numerator, other)
156  if r == 0:
157  return Rational(q, self.denominator)
158  numerator = self.numerator
159  denominator = self.denominator*other
160  return +Rational(numerator, denominator)
161  elif isinstance(other, Float):
162  return self.toFloat() / other
163  elif isinstance(other, float):
164  return float(self) / other
165  else:
166  return NotImplemented
167
168  __div__ = __truediv__
169  __floordiv__ = __truediv__
170
172  """
173  other + self
174
175  If other is an integer, the result will be a rational. If
176  other is a kind of float the result is an instance of other's
177  type. Otherwise, other would do the computation.
178  """
179  if isIntegerObject(other):
180  numerator = self.numerator + self.denominator*other
181  denominator = self.denominator
182  return +Rational(numerator, denominator)
183  elif isinstance(other, Float):
184  return other + self.toFloat()
185  elif isinstance(other, float):
186  return other + float(self)
187  else:
188  return NotImplemented
189
190  def __rsub__(self, other):
191  """
192  other - self
193
194  If other is an integer, the result will be a rational. If
195  other is a kind of float the result is an instance of other's
196  type. Otherwise, other would do the computation.
197  """
198  if isIntegerObject(other):
199  numerator = self.denominator*other - self.numerator
200  denominator = self.denominator
201  return +Rational(numerator, denominator)
202  elif isinstance(other, Float):
203  return other - self.toFloat()
204  elif isinstance(other, float):
205  return other - float(self)
206  else:
207  return NotImplemented
208
209  def __rmul__(self, other):
210  """
211  other * self
212
213  If other is an integer, the result will be a rational. If
214  other is a kind of float the result is an instance of other's
215  type. Otherwise, other would do the computation.
216  """
217  if isIntegerObject(other):
218  numerator = self.numerator*other
219  denominator = self.denominator
220  return +Rational(numerator, denominator)
221  elif isinstance(other, Float):
222  return other * self.toFloat()
223  elif isinstance(other, float):
224  return other * float(self)
225  else:
226  return NotImplemented
227
228  def __rtruediv__(self, other):
229  """
230  other / self
231  other // self
232
233  If other is an integer, the result will be a rational. If
234  other is a kind of float the result is an instance of other's
235  type. Otherwise, other would do the computation.
236  """
237  if isIntegerObject(other):
238  if other == 1:
239  return Rational(self.denominator, self.numerator)
240  numerator = self.denominator*other
241  denominator = self.numerator
242  return +Rational(numerator, denominator)
243  elif isinstance(other, Float):
244  return other / self.toFloat()
245  elif isinstance(other, float):
246  return other / float(self)
247  else:
248  return NotImplemented
249
250  __rdiv__ = __rtruediv__
251  __rfloordiv__ = __rtruediv__
252
253  def __pow__(self, index):
254  assert isIntegerObject(index)
255  if index > 0:
256  return +Rational(self.numerator ** index, self.denominator ** index)
257  elif index < 0:
258  if index == -1:
259  return Rational(self.denominator, self.numerator)
260  return +Rational(self.denominator ** (-index), self.numerator ** (-index))
261  else:
262  return Integer(1)
263
264  def __lt__(self, other):
265  return self.compare(other) < 0
266
267  def __le__(self, other):
268  return self.compare(other) <= 0
269
270  def __eq__(self, other):
271  if isIntegerObject(other):
272  if self.denominator == 1:
273  return self.numerator == other
274  elif self.numerator % self.denominator == 0:
275  return self.numerator // self.denominator == other
276  else:
277  return False
278  elif hasattr(other, "denominator") and hasattr(other, "numerator"):
279  return self.compare(other) == 0
280  else:
281  return NotImplemented
282
283  def __ne__(self, other):
284  return self.compare(other) != 0
285
286  def __gt__(self, other):
287  return self.compare(other) > 0
288
289  def __ge__(self, other):
290  return self.compare(other) >= 0
291
292  def __pos__(self):
293  common_divisor = theIntegerRing.gcd(self.numerator, self.denominator)
294  if common_divisor != 1:
295  self.numerator //= common_divisor
296  self.denominator //= common_divisor
297  return Rational(self.numerator, self.denominator)
298
299  def __neg__(self):
300  return Rational(-self.numerator, self.denominator)
301
302  def __abs__(self):
303  return +Rational(abs(self.numerator), self.denominator)
304
305  def __long__(self):
306  return self.numerator // self.denominator
307
308  __int__ = __long__
309
310  def __str__(self):
311  return str(self.numerator) + "/" + str(self.denominator)
312
313  def __repr__(self):
314  return "%s(%d, %d)" % (self.__class__.__name__, self.numerator, self.denominator)
315
316  def __nonzero__(self):
317  if self.numerator:
318  return True
319  else:
320  return False
321
322  def __hash__(self):
323  """
324  a==b => hash(a)==hash(b)
325  """
326  hashed = hash(self.__class__.__name__)
327  if self.numerator % self.denominator == 0:
328  hashed ^= hash(self.numerator // self.denominator)
329  else:
330  hashed ^= hash(self.numerator)
331  hashed ^= hash(self.denominator)
332  return hashed
333
334  def expand(self, base, limit):
335  """
336  r.expand(k, limit) returns the nearest rational number whose
337  denominator is a power of k and at most limit, if k > 0. if
338  k==0, it returns the nearest rational number whose denominator
339  is at most limit, i.e. r.expand(0, limit) == r.trim(limit).
340  """
341  if base == 0:
342  return self.trim(limit)
343  assert isIntegerObject(base) and base > 0
344  if self < 0:
345  return -(-self).expand(base, limit)
346  numerator, rest = divmod(self.numerator, self.denominator)
347  i = 0
348  if base == 2:
349  while numerator*2 <= limit and rest:
350  numerator <<= 1
351  rest <<= 1
352  i += 1
353  if rest >= self.denominator:
354  numerator += 1
355  rest -= self.denominator
356  if rest*2 > self.denominator:
357  numerator += 1
358  else:
359  while numerator*base <= limit and rest:
360  numerator *= base
361  rest *= base
362  i += 1
363  while rest >= self.denominator:
364  numerator += 1
365  rest -= self.denominator
366  if rest*2 > self.denominator:
367  numerator += 1
368  return Rational(numerator, base ** i)
369
370  def trim(self, max_denominator):
371  quotient, remainder = divmod(self.numerator, self.denominator)
372  approximant0 = Rational(quotient, 1)
373  if remainder == 0:
374  return approximant0
375  rest = Rational(remainder, self.denominator)
376  quotient, remainder = divmod(rest.denominator, rest.numerator)
377  if quotient > max_denominator:
378  return approximant0
379  approximant1 = Rational(quotient * approximant0.numerator + 1, quotient)
380  if remainder == 0:
381  return approximant1
382  rest = Rational(remainder, rest.numerator)
383  while remainder:
384  if rest.numerator > 1:
385  quotient, remainder = divmod(rest.denominator, rest.numerator)
386  elif rest.denominator > 1:
387  quotient, remainder = (rest.denominator-1, 1)
388  else:
389  quotient, remainder = (1, 0)
390  approximant = Rational(quotient * approximant1.numerator + approximant0.numerator, quotient * approximant1.denominator + approximant0.denominator)
391  if approximant.denominator > max_denominator:
392  break
393  approximant0, approximant1 = approximant1, approximant
394  rest = Rational(remainder, rest.numerator)
395  return approximant1
396
397  def compare(self, other):
398  if isIntegerObject(other):
399  return self.numerator - self.denominator * other
400  if isinstance(other, float):
401  return self.compare(Rational(other))
402  if isinstance(other, Float):
403  return cmp(self.toFloat(), other)
404  return self.numerator*other.denominator - self.denominator*other.numerator
405
406  def getRing(self):
407  return theRationalField
408
409  def _reduce(self):
410  if self.denominator < 0:
411  self.numerator = -self.numerator
412  self.denominator = -self.denominator
413  common_divisor = theIntegerRing.gcd(self.numerator, self.denominator)
414  if common_divisor != 1:
415  self.numerator //= common_divisor
416  self.denominator //= common_divisor
417  def __float__(self):
418  return float(self.decimalString(17))
419
420  def toFloat(self):
421  return Float(self.numerator) / Float(self.denominator)
422
423  def decimalString(self, N):
424  """
425  Return a string of the number to N decimal places.
426  """
427  n = self.numerator
428  d = self.denominator
429  L = []
430  if n < 0:
431  L.append('-')
432  n = -n
433  i = 1
434  L.append(str(n//d))
435  L.append('.')
436  while i <= N:
437  n = n % d * 10
438  L.append(str(n//d))
439  i += 1
440  return ''.join(L)
441
442  def _init_by_Rational_Rational(self, numerator, denominator):
443  """
444  Initialize by a rational numbers.
445  """
446  self.numerator = numerator.numerator * denominator.denominator
447  self.denominator = numerator.denominator * denominator.numerator
448
449  def _init_by_float_Rational(self, numerator, denominator):
450  """
451  Initialize by a float number and a rational number.
452  """
453  dp = 53
454  frexp = math.frexp(numerator)
455  self.numerator = denominator.denominator * (frexp * 2 ** dp)
456  self.denominator = denominator.numerator * (2 ** (dp - frexp))
457
458  def _init_by_int_Rational(self, numerator, denominator):
459  """
460  Initailize by an integer and a rational number.
461  """
462  self.numerator = denominator.denominator * numerator
463  self.denominator = denominator.numerator
464
465  def _init_by_Rational_float(self, numerator, denominator):
466  """
467  Initialize by a rational number and a float.
468  """
469  dp = 53
470  frexp = math.frexp(denominator)
471  self.numerator = numerator.numerator * (2 ** (dp - frexp))
472  self.denominator = numerator.denominator * (frexp * 2 ** dp)
473
474  def _init_by_float_float(self, numerator, denominator):
475  """
476  Initialize by a float numbers.
477  """
478  dp = 53
479  frexp_num = math.frexp(numerator)
480  frexp_den = math.frexp(denominator)
481  self.numerator = Integer(frexp_num * 2 ** (2 * dp - frexp_den))
482  self.denominator = Integer(frexp_den * 2 ** (2 * dp - frexp_num))
483
484  def _init_by_int_float(self, numerator, denominator):
485  """
486  Initailize by an integer and a float
487  """
488  dp = 53
489  frexp_den = math.frexp(denominator)
490  self.numerator = Integer(numerator * (2 ** (dp - frexp_den)))
491  self.denominator = Integer(frexp_den * 2 ** dp)
492
493  def _init_by_Rational_int(self, numerator, denominator):
494  """
495  Initialize by a rational number and integer.
496  """
497  self.numerator = numerator.numerator
498  self.denominator = numerator.denominator * denominator
499
500  def _init_by_float_int(self, numerator, denominator):
501  """
502  Initialize by a float number and an integer.
503  """
504  dp = 53
505  frexp = math.frexp(numerator)
506  self.numerator = Integer(frexp * 2 ** dp)
507  self.denominator = Integer(2 ** (dp - frexp) * denominator)
508
509  def _init_by_int_int(self, numerator, denominator):
510  """
511  Initailize by an integers.
512  """
513  self.numerator = Integer(numerator)
514  self.denominator = Integer(denominator)
515
516
518  """
519  RationalField is a class of field of rationals.
520  The class has the single instance 'theRationalField'.
521  """
522
523  def __init__(self):
524  ring.QuotientField.__init__(self, theIntegerRing)
525
526  def __contains__(self, element):
527  try:
528  reduced = +element
529  return (isinstance(reduced, Rational) or isIntegerObject(reduced))
530  except (TypeError, AttributeError):
531  return False
532
533  def __eq__(self, other):
534  """
535  Equality test.
536  """
537  return isinstance(other, RationalField)
538
539  def classNumber(self):
540  """The class number of the rational field is one."""
541  return 1
542
543  def getQuotientField(self):
544  """getQuotientField returns the rational field itself."""
545  return self
546
547  def getCharacteristic(self):
548  """The characteristic of the rational field is zero."""
549  return 0
550
551  def createElement(self, numerator, denominator=1):
552  """
553  createElement returns a Rational object.
554  If the number of arguments is one, it must be an integer or a rational.
555  If the number of arguments is two, they must be integers.
556  """
557  return Rational(numerator, denominator)
558
559  def __str__(self):
560  return "Q"
561
562  def __repr__(self):
563  return "RationalField()"
564
565  def __hash__(self):
566  """
567  Return a hash number (always 1).
568  """
569  return 1
570
571  def issubring(self, other):
572  """
573  reports whether another ring contains the rational field as
574  subring.
575
576  If other is also the rational field, the output is True. If
577  other is the integer ring, the output is False. In other
578  cases it depends on the implementation of another ring's
579  issuperring method.
580  """
581  if isinstance(other, RationalField):
582  return True
583  elif isinstance(other, IntegerRing):
584  return False
585  try:
586  return other.issuperring(self)
587  except RuntimeError:
588  # reached recursion limit by calling on each other
589  raise NotImplementedError("no common super ring")
590
591  def issuperring(self, other):
592  """
593  reports whether the rational number field contains another
594  ring as subring.
595
596  If other is also the rational number field or the ring of
597  integer, the output is True. In other cases it depends on the
598  implementation of another ring's issubring method.
599  """
600  if isinstance(other, (RationalField, IntegerRing)):
601  return True
602  try:
603  return other.issubring(self)
604  except RuntimeError:
605  # reached recursion limit by calling on each other
606  raise NotImplementedError("no common super ring")
607
608  def getCommonSuperring(self, other):
609  """
610  Return common superring of the ring and another ring.
611  """
612  if self.issubring(other):
613  return other
614  elif self.issuperring(other):
615  return self
616  try:
617  return other.getCommonSuperring(self)
618  except RuntimeError:
619  # reached recursion limit by calling on each other
620  raise NotImplementedError("no common super ring")
621
622  def _getOne(self):
623  "getter for one"
624  if self._one is None:
625  self._one = Rational(1, 1)
626  return self._one
627
628  one = property(_getOne, None, None, "multiplicative unit.")
629
630  def _getZero(self):
631  "getter for zero"
632  if self._zero is None:
633  self._zero = Rational(0, 1)
634  return self._zero
635
636  zero = property(_getZero, None, None, "additive unit.")
637
638
640  """
641  Integer is a class of integer. Since 'int' and 'long' do not
642  return rational for division, it is needed to create a new class.
643  """
644  def __init__(self, value):
645  ring.CommutativeRingElement.__init__(self)
646
647  def __div__(self, other):
648  if other in theIntegerRing:
649  return +Rational(self, +other)
650  else:
651  return NotImplemented
652
653  def __rdiv__(self, other):
654  if other in theIntegerRing:
655  return +Rational(+other, self)
656  else:
657  return NotImplemented
658
659  __truediv__ = __div__
660
661  __rtruediv__ = __rdiv__
662
663  def __floordiv__(self, other):
664  return Integer(long(self)//other)
665
666  def __rfloordiv__(self, other):
667  try:
668  return Integer(other//long(self))
669  except:
670  return NotImplemented
671
672  def __mod__(self, other):
673  if isinstance(other, (int, long)):
674  return Integer(long(self)%long(other))
675  return NotImplemented
676
677  def __rmod__(self, other):
678  return Integer(other%long(self))
679
680  def __divmod__(self, other):
681  return tuple([Integer(x) for x in divmod(long(self), other)])
682
683  def __rdivmod__(self, other):
684  return tuple([Integer(x) for x in divmod(other, long(self))])
685
687  if isIntegerObject(other):
688  return Integer(long(self)+other)
689  else:
690  return NotImplemented
691
693
694  def __sub__(self, other):
695  if isIntegerObject(other):
696  return Integer(long(self)-other)
697  else:
698  return NotImplemented
699
700  def __rsub__(self, other):
701  return Integer(other-long(self))
702
703  def __mul__(self, other):
704  if isinstance(other, (int, long)):
705  return self.__class__(long(self) * other)
706  try:
707  retval = other.__rmul__(self)
708  if retval is not NotImplemented:
709  return retval
710  except Exception:
711  pass
713
714  def __rmul__(self, other):
715  if isinstance(other, (int, long)):
716  return self.__class__(other * long(self))
717  elif other.__class__ in __builtins__.values():
718  return other.__mul__(long(self))
720
721  def __pow__(self, index, modulo=None):
722  """
723  If index is negative, result may be a rational number.
724  """
725  if modulo is None and index < 0:
726  return Rational(1, long(self) ** (-index))
727  return Integer(pow(long(self), index, modulo))
728
729  def __pos__(self):
730  return Integer(self)
731
732  def __neg__(self):
733  return Integer(-long(self))
734
735  def __abs__(self):
736  return Integer(abs(long(self)))
737
738  def __eq__(self, other):
739  return long(self) == long(other)
740
741  def __hash__(self):
742  return hash(long(self))
743
744  def getRing(self):
745  return theIntegerRing
746
747  def inverse(self):
748  return Rational(1, self)
749
751  """
752  Act on other additively, i.e. n is expanded to n time
753  additions of other. Naively, it is:
754  return sum([+other for _ in xrange(self)])
755  but, here we use a binary addition chain.
756  """
757  nonneg, absVal = (self >= 0), abs(self)
758  result = 0
759  doubling = +other
760  while absVal:
761  if absVal & 1:
762  result += doubling
763  doubling += doubling
764  absVal >>= 1
765  if not nonneg:
766  result = -result
767  return result
768
769  def actMultiplicative(self, other):
770  """
771  Act on other multiplicatively, i.e. n is expanded to n time
772  multiplications of other. Naively, it is:
773  return reduce(lambda x,y:x*y, [+other for _ in xrange(self)])
774  but, here we use a binary addition chain.
775  """
776  nonneg, absVal = (self >= 0), abs(self)
777  result = 1
778  doubling = +other
779  while absVal:
780  if absVal& 1:
781  result *= doubling
782  doubling *= doubling
783  absVal >>= 1
784  if not nonneg:
785  result = result.inverse()
786  return result
787
788
790  """
791  IntegerRing is a class of ring of rational integers.
792  The class has the single instance 'theIntegerRing'.
793  """
794
795  def __init__(self):
796  ring.CommutativeRing.__init__(self)
797  self.properties.setIseuclidean(True)
798  self.properties.setIsfield(False)
799
800  def __contains__(self, element):
801  """
802  `in' operator is provided for checking an object be in the
803  rational integer ring mathematically. To check an object be
804  an integer object in Python, please use isIntegerObject.
805  """
806  try:
807  return isIntegerObject(+element)
808  except (TypeError, AttributeError):
809  return False
810
811  def __eq__(self, other):
812  """
813  Equality test.
814  """
815  return isinstance(other, IntegerRing)
816
817  def getQuotientField(self):
818  """
819  getQuotientField returns the rational field.
820  """
821  return theRationalField
822
823  def createElement(self, seed):
824  """
825  createElement returns an Integer object with seed,
826  which must be an integer.
827  """
828  return Integer(seed)
829
830  def __str__(self):
831  return "Z"
832
833  def __repr__(self):
834  return "IntegerRing()"
835
836  def __hash__(self):
837  """
838  Return a hash number (always 0).
839  """
840  return 0
841
842  def getCharacteristic(self):
843  """
844  The characteristic of the integer ring is zero.
845  """
846  return 0
847
848  def issubring(self, other):
849  """
850  reports whether another ring contains the integer ring as
851  subring.
852
853  If other is also the integer ring, the output is True. In
854  other cases it depends on the implementation of another ring's
855  issuperring method.
856  """
857  if isinstance(other, IntegerRing):
858  return True
859  return other.issuperring(self)
860
861  def issuperring(self, other):
862  """
863  reports whether the integer ring contains another ring as
864  subring.
865
866  If other is also the integer ring, the output is True. In
867  other cases it depends on the implementation of another ring's
868  issubring method.
869  """
870  if isinstance(other, IntegerRing):
871  return True
872  return other.issubring(self)
873
874  def getCommonSuperring(self, other):
875  """
876  Return common superring of the ring and another ring.
877  """
878  if self.issubring(other):
879  return other
880  elif self.issuperring(other):
881  return self
882  try:
883  return other.getCommonSuperring(self)
884  except RuntimeError:
885  # reached recursion limit by calling on each other
886  raise NotImplementedError("no common super ring")
887
888  def gcd(self, n, m):
889  """
890  Return the greatest common divisor of given 2 integers.
891  """
892  a, b = abs(n), abs(m)
893  return Integer(gcd.gcd(a, b))
894
895  def lcm(self, a, b):
896  """
897  Return the least common multiple of given 2 integers.
898  If both are zero, it raises an exception.
899  """
900  return a // self.gcd(a, b) * b
901
902  def extgcd(self, a, b):
903  """
904  Return a tuple (u, v, d); they are the greatest common divisor
905  d of two given integers x and y and u, v such that
906  d = x * u + y * v.
907  """
908  return tuple(map(Integer, gcd.extgcd(a, b)))
909
910  def _getOne(self):
911  "getter for one"
912  if self._one is None:
913  self._one = Integer(1)
914  return self._one
915
916  one = property(_getOne, None, None, "multiplicative unit.")
917
918  def _getZero(self):
919  "getter for zero"
920  if self._zero is None:
921  self._zero = Integer(0)
922  return self._zero
923
924  zero = property(_getZero, None, None, "additive unit.")
925
926
927 theIntegerRing = IntegerRing()
928 theRationalField = RationalField()
929
930
931 def isIntegerObject(anObject):
932  """
933  True if the given object is instance of int or long,
934  False otherwise.
935  """
936  return isinstance(anObject, (int, long))
937
938 def IntegerIfIntOrLong(anObject):
939  """
940  Cast int or long objects to Integer.
941  The objects in list or tuple can be casted also.
942  """
943  objectClass = anObject.__class__
944  if objectClass == int or objectClass == long:
945  return Integer(anObject)
946  elif isinstance(anObject, (list,tuple)):
947  return objectClass([IntegerIfIntOrLong(i) for i in anObject])
948  return anObject
949
950
951 def continued_fraction_expansion(target, terms):
952  """
953  Return continued fraction expansion of a real number.
954
955  >>> continued_fraction_expansion(1.4142, 2)
956  [1, 2, 2]
957
958  The first component is the integer part, and rest is fractional
959  part, whose number of terms is specified by the second argument.
960  """
961  # integer part
962  ipart = math.floor(target)
963  target -= ipart
964  result = [int(ipart)]
965
966  # expansion
967  for i in range(terms):
968  reverse = 1 / target
969  term = math.floor(reverse)
970  target = reverse - term
971  result.append(int(term))
972
973  return result
nzmath.rational.Rational.expand
def expand(self, base, limit)
Definition: rational.py:334
nzmath.rational.Rational.__gt__
def __gt__(self, other)
Definition: rational.py:286
nzmath.bigrange.range
def range(start, stop=None, step=None)
Definition: bigrange.py:19
nzmath.ring
Definition: ring.py:1
nzmath.rational.RationalField.getCharacteristic
def getCharacteristic(self)
Definition: rational.py:547
nzmath.rational.RationalField.issubring
def issubring(self, other)
Definition: rational.py:571
nzmath.rational.Integer.__sub__
def __sub__(self, other)
Definition: rational.py:694
nzmath.rational.IntegerRing.extgcd
def extgcd(self, a, b)
Definition: rational.py:902
nzmath.rational.Integer.__floordiv__
def __floordiv__(self, other)
Definition: rational.py:663
nzmath.rational.Integer.__pow__
def __pow__(self, index, modulo=None)
Definition: rational.py:721
nzmath.rational.Rational._init_by_int_float
def _init_by_int_float(self, numerator, denominator)
Definition: rational.py:484
nzmath.rational.IntegerRing.gcd
def gcd(self, n, m)
Definition: rational.py:888
nzmath.rational.Integer.__pos__
def __pos__(self)
Definition: rational.py:729
nzmath.rational.Rational.__long__
def __long__(self)
Definition: rational.py:305
nzmath.rational.Rational.__str__
def __str__(self)
Definition: rational.py:310
nzmath.rational.Rational.__sub__
def __sub__(self, other)
Definition: rational.py:92
nzmath.rational.IntegerRing.__hash__
def __hash__(self)
Definition: rational.py:836
nzmath.ring.QuotientFieldElement
Definition: ring.py:361
nzmath.rational.Rational.__nonzero__
def __nonzero__(self)
Definition: rational.py:316
nzmath.rational.Rational.__lt__
def __lt__(self, other)
Definition: rational.py:264
nzmath.rational.Integer.__neg__
def __neg__(self)
Definition: rational.py:732
nzmath.rational.Rational.decimalString
def decimalString(self, N)
Definition: rational.py:423
nzmath.rational.Rational.__truediv__
def __truediv__(self, other)
Definition: rational.py:140
nzmath.rational.Integer.__mod__
def __mod__(self, other)
Definition: rational.py:672
nzmath.rational.Rational.__le__
def __le__(self, other)
Definition: rational.py:267
nzmath.gcd
Definition: gcd.py:1
nzmath.rational.Integer.__eq__
def __eq__(self, other)
Definition: rational.py:738
nzmath.rational.RationalField.__repr__
def __repr__(self)
Definition: rational.py:562
nzmath.rational.IntegerRing.createElement
def createElement(self, seed)
Definition: rational.py:823
nzmath.rational.Rational.trim
def trim(self, max_denominator)
Definition: rational.py:370
nzmath.rational.Rational.__eq__
def __eq__(self, other)
Definition: rational.py:270
nzmath.rational.RationalField.classNumber
def classNumber(self)
Definition: rational.py:539
Definition: rational.py:686
nzmath.rational.Rational.__float__
def __float__(self)
Definition: rational.py:417
nzmath.rational.Rational.toFloat
def toFloat(self)
Definition: rational.py:420
nzmath.rational.Rational.__repr__
def __repr__(self)
Definition: rational.py:313
nzmath.ring.CommutativeRing
Definition: ring.py:88
nzmath.rational.Rational.__mul__
def __mul__(self, other)
Definition: rational.py:116
nzmath.rational.Integer.__mul__
def __mul__(self, other)
Definition: rational.py:703
nzmath.rational.Rational.__hash__
def __hash__(self)
Definition: rational.py:322
nzmath.rational.Rational
Definition: rational.py:10
nzmath.rational.Rational.__ne__
def __ne__(self, other)
Definition: rational.py:283
nzmath.rational.Integer.actMultiplicative
def actMultiplicative(self, other)
Definition: rational.py:769
nzmath.rational.Integer.getRing
def getRing(self)
Definition: rational.py:744
nzmath.rational.Rational._init_by_Rational_int
def _init_by_Rational_int(self, numerator, denominator)
Definition: rational.py:493
nzmath.rational.RationalField.getCommonSuperring
def getCommonSuperring(self, other)
Definition: rational.py:608
nzmath.rational.Rational._init_by_float_Rational
def _init_by_float_Rational(self, numerator, denominator)
Definition: rational.py:449
nzmath.rational.RationalField.__contains__
def __contains__(self, element)
Definition: rational.py:526
Definition: rational.py:171
nzmath.rational.Rational._init_by_float_int
def _init_by_float_int(self, numerator, denominator)
Definition: rational.py:500
nzmath.rational.Rational.compare
def compare(self, other)
Definition: rational.py:397
nzmath.rational.IntegerRing
Definition: rational.py:789
nzmath.rational.Rational.denominator
denominator
Definition: rational.py:60
nzmath.rational.Integer.__rdivmod__
def __rdivmod__(self, other)
Definition: rational.py:683
nzmath.rational.IntegerRing.getQuotientField
def getQuotientField(self)
Definition: rational.py:817
nzmath.rational.IntegerRing._getOne
def _getOne(self)
Definition: rational.py:910
nzmath.ring.QuotientField
Definition: ring.py:234
nzmath.rational.Integer.__abs__
def __abs__(self)
Definition: rational.py:735
nzmath.rational.Rational._init_by_float_float
def _init_by_float_float(self, numerator, denominator)
Definition: rational.py:474
nzmath.rational.Rational._reduce
def _reduce(self)
Definition: rational.py:409
nzmath.rational.RationalField._getOne
def _getOne(self)
Definition: rational.py:622
nzmath.rational.Rational._init_by_Rational_float
def _init_by_Rational_float(self, numerator, denominator)
Definition: rational.py:465
nzmath.rational.RationalField.createElement
def createElement(self, numerator, denominator=1)
Definition: rational.py:551
nzmath.compatibility.cmp
cmp
Definition: compatibility.py:20
nzmath.rational.Rational.__init__
def __init__(self, numerator, denominator=1)
Definition: rational.py:15
nzmath.rational.IntegerRing._one
_one
Definition: rational.py:913
nzmath.rational.Rational.__rmul__
def __rmul__(self, other)
Definition: rational.py:209
nzmath.rational.Rational.getRing
def getRing(self)
Definition: rational.py:406
nzmath.ring.CommutativeRingElement
Definition: ring.py:291
nzmath.rational.RationalField._one
_one
Definition: rational.py:625
nzmath.rational.RationalField._getZero
def _getZero(self)
Definition: rational.py:630
nzmath.rational.RationalField.issuperring
def issuperring(self, other)
Definition: rational.py:591
nzmath.plugins
Definition: plugins.py:1
nzmath.rational.IntegerRing._getZero
def _getZero(self)
Definition: rational.py:918
nzmath.rational.Integer.__hash__
def __hash__(self)
Definition: rational.py:741
nzmath.rational.Integer
Definition: rational.py:639
nzmath.rational.Rational.__neg__
def __neg__(self)
Definition: rational.py:299
nzmath.rational.IntegerRing.__str__
def __str__(self)
Definition: rational.py:830
nzmath.rational.RationalField.__eq__
def __eq__(self, other)
Definition: rational.py:533
nzmath.rational.Rational.__pos__
def __pos__(self)
Definition: rational.py:292
nzmath.rational.RationalField.__str__
def __str__(self)
Definition: rational.py:559
nzmath.rational.Rational.numerator
numerator
Definition: rational.py:273
nzmath.rational.continued_fraction_expansion
def continued_fraction_expansion(target, terms)
Definition: rational.py:951
nzmath.rational.IntegerRing.__contains__
def __contains__(self, element)
Definition: rational.py:800
nzmath.rational.IntegerRing.issubring
def issubring(self, other)
Definition: rational.py:848
nzmath.rational.Rational.__abs__
def __abs__(self)
Definition: rational.py:302
nzmath.rational.Integer.__rdiv__
def __rdiv__(self, other)
Definition: rational.py:653
nzmath.rational.Integer.__div__
def __div__(self, other)
Definition: rational.py:647
nzmath.rational.RationalField.getQuotientField
def getQuotientField(self)
Definition: rational.py:543
nzmath.rational.IntegerRing.__repr__
def __repr__(self)
Definition: rational.py:833
nzmath.rational.IntegerRing.getCharacteristic
def getCharacteristic(self)
Definition: rational.py:842
nzmath.rational.RationalField
Definition: rational.py:517
nzmath.rational.IntegerRing._zero
_zero
Definition: rational.py:921
nzmath.rational.IntegerIfIntOrLong
def IntegerIfIntOrLong(anObject)
Definition: rational.py:938
Definition: rational.py:68
nzmath.rational.Rational.__pow__
def __pow__(self, index)
Definition: rational.py:253
nzmath.rational.Rational.__rsub__
def __rsub__(self, other)
Definition: rational.py:190
nzmath.rational.Integer.inverse
def inverse(self)
Definition: rational.py:747
nzmath.rational.Integer.__init__
def __init__(self, value)
Definition: rational.py:644
nzmath.rational.IntegerRing.__eq__
def __eq__(self, other)
Definition: rational.py:811
nzmath.ring.CommutativeRing.properties
properties
Definition: ring.py:103
nzmath.rational.RationalField._zero
_zero
Definition: rational.py:633
nzmath.rational.IntegerRing.__init__
def __init__(self)
Definition: rational.py:795
nzmath.rational.Integer.__rfloordiv__
def __rfloordiv__(self, other)
Definition: rational.py:666
nzmath.rational.IntegerRing.getCommonSuperring
def getCommonSuperring(self, other)
Definition: rational.py:874
nzmath.rational.RationalField.__init__
def __init__(self)
Definition: rational.py:523
nzmath.rational.Integer.__divmod__
def __divmod__(self, other)
Definition: rational.py:680
nzmath.rational.Rational._init_by_int_int
def _init_by_int_int(self, numerator, denominator)
Definition: rational.py:509
nzmath.rational.IntegerRing.issuperring
def issuperring(self, other)
Definition: rational.py:861
nzmath.rational.Rational.__rtruediv__
def __rtruediv__(self, other)
Definition: rational.py:228
nzmath.rational.Integer.__rmul__
def __rmul__(self, other)
Definition: rational.py:714
nzmath.rational.Rational._init_by_Rational_Rational
def _init_by_Rational_Rational(self, numerator, denominator)
Definition: rational.py:442
nzmath.rational.isIntegerObject
def isIntegerObject(anObject)
Definition: rational.py:931
nzmath.rational.Integer.__rsub__
def __rsub__(self, other)
Definition: rational.py:700
nzmath.rational.Rational._init_by_int_Rational
def _init_by_int_Rational(self, numerator, denominator)
Definition: rational.py:458