## "Fossies" - the Fresh Open Source Software Archive

### Member "NZMATH-1.2.0/nzmath/rational.py" (19 Nov 2012, 31846 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "rational.py" see the Fossies "Dox" file reference documentation.

```    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
10 class Rational (ring.QuotientFieldElement):
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[0])
57                 approx1 = Rational(cfe[1] * cfe[0] + 1, cfe[1])
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[0] * 2 ** dp)
456         self.denominator = denominator.numerator * (2 ** (dp - frexp[1]))
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[1]))
472         self.denominator = numerator.denominator * (frexp[0] * 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[0] * 2 ** (2 * dp - frexp_den[1]))
482         self.denominator = Integer(frexp_den[0] * 2 ** (2 * dp - frexp_num[1]))
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[1])))
491         self.denominator = Integer(frexp_den[0] * 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[0] * 2 ** dp)
507         self.denominator = Integer(2 ** (dp - frexp[1]) * 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
517 class RationalField (ring.QuotientField):
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
639 class Integer(long, ring.CommutativeRingElement):
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
789 class IntegerRing (ring.CommutativeRing):
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
```