"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/poly/univar.py" (19 Nov 2012, 26253 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 "univar.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 Univariate Polynomials
    3 
    4 The polynomials are immutable data types, under the public API.  If
    5 one tries to manipulate its underlying data attributes, immutability
    6 will be able to be broken.
    7 """
    8 
    9 from __future__ import division
   10 import warnings
   11 import nzmath.ring as _ring
   12 import nzmath.poly.formalsum as formalsum
   13 
   14 
   15 class PolynomialInterface(formalsum.FormalSumContainerInterface):
   16     """
   17     Base class for all univariate polynomials.
   18     """
   19     def __init__(self, coefficients, **kwds):
   20         """
   21         For any descendants of PolynomialInterface, `coefficients'
   22         have to be given.  Other arguments, if necessary, should be
   23         passed as keyword arguments.  Note that in this __init__
   24         method, no actual initialization happens.
   25         """
   26         formalsum.FormalSumContainerInterface.__init__(self)
   27         self.number_of_variables = 1
   28 
   29     def __eq__(self, other):
   30         """
   31         self == other
   32         """
   33         if not isinstance(other, PolynomialInterface):
   34             warnings.warn("comparison falls back to that of formal sum.")
   35             return formalsum.FormalSumContainerInterface.__eq__(self, other)
   36         sterms = [t for t in self.iterterms() if t[1]]
   37         sterms.sort()
   38         oterms = [t for t in other.iterterms() if t[1]]
   39         oterms.sort()
   40         return sterms == oterms
   41 
   42     def __hash__(self):
   43        val = sum([hash(t) for t in self.iterterms() if t[1]])
   44        return val
   45 
   46     def __pow__(self, index):
   47         """
   48         self ** index
   49         """
   50         raise NotImplementedError("should be overridden")
   51 
   52     def ring_mul(self, other):
   53         """
   54         Multiplication of two polynomials in the same ring.
   55         """
   56         mul_coeff = {}
   57         for ds, cs in self:
   58             for do, co in other:
   59                 term_degree = ds + do
   60                 if term_degree in mul_coeff:
   61                     mul_coeff[term_degree] += cs*co
   62                 else:
   63                     mul_coeff[term_degree] = cs*co
   64         return self.construct_with_default(sorted([(d, c) for (d, c) in mul_coeff.iteritems() if c]))
   65 
   66     def scalar_mul(self, scale):
   67         """
   68         Return the result of scalar multiplication.
   69         """
   70         return self.construct_with_default([(d, c * scale) for (d, c) in self if c])
   71 
   72     def term_mul(self, term):
   73         """
   74         Return the result of multiplication with the given term.
   75         The term can be given as a tuple (degree, coeff) or as a
   76         Polynomial instance.
   77         """
   78         if isinstance(term, PolynomialInterface):
   79             degree, coeff = iter(term).next()
   80         else:
   81             degree, coeff = term
   82         return self.construct_with_default([(d + degree, c * coeff) for (d, c) in self])
   83 
   84     def square(self):
   85         """
   86         Return square of this polynomial.
   87         """
   88         raise NotImplementedError("should be overridden")
   89 
   90     def differentiate(self):
   91         """
   92         Return the formal differentiation of self.
   93         """
   94         result = {}
   95         for d, c in self:
   96             if d > 0:
   97                 dc = d * c
   98                 if dc:
   99                     result[d - 1] = dc
  100         return self.construct_with_default(result)
  101 
  102     def upshift_degree(self, slide):
  103         """
  104         Return the polynomial obtained by shifting upward all terms
  105         with degrees of 'slide'.
  106 
  107         f.upshift_degree(slide) is equivalent to
  108         f.term_mul((slide, 1)).
  109         """
  110         return self.bases_map(lambda x: x + slide)
  111 
  112     def downshift_degree(self, slide):
  113         """
  114         Return the polynomial obtained by shifting downward all terms
  115         with degrees of 'slide'.
  116 
  117         Be careful that if the least degree term has the degree less
  118         than 'slide' then the result is not mathematically a
  119         polynomial.  Even in such a case, the method does not raise an
  120         exception.
  121 
  122         f.downshift_degree(slide) is equivalent to
  123         f.upshift_degree(-slide).
  124         """
  125         return self.bases_map(lambda x: x - slide)
  126 
  127     def terms_map(self, func):
  128         """
  129         Create a new formal sum container by applying func to each
  130         term.  func must be a function taking 2 arguments.
  131         """
  132         terms = []
  133         for t in self:
  134             b, c = func(*t)
  135             if c:
  136                 terms.append((b, c))
  137         return self.construct_with_default(terms)
  138 
  139     def construct_with_default(self, terms):
  140         """
  141         Create a new univariate polynomial of the same class with
  142         self, with given only the terms and use copy of self's data if
  143         necessary.
  144         """
  145         return self.__class__(terms, **self._init_kwds)
  146 
  147 
  148 class BasicPolynomial(PolynomialInterface):
  149     """
  150     Basic polynomial data type ignoring a variable name and the ring.
  151     """
  152     def __init__(self, coefficients, **kwds):
  153         """
  154         BasicPolynomial(coefficients)
  155 
  156         coefficients can be any dict initial values.
  157         """
  158         PolynomialInterface.__init__(self, coefficients, **kwds)
  159         self._coefficients = dict(coefficients)
  160         self._init_kwds = kwds
  161 
  162     def __add__(self, other):
  163         """
  164         self + other
  165         """
  166         sum_coeff = dict(iter(self))
  167         for term, coeff in other:
  168             if term in sum_coeff:
  169                 sum_coeff[term] += coeff
  170             else:
  171                 sum_coeff[term] = coeff
  172         return self.construct_with_default([(d, c) for (d, c) in sum_coeff.iteritems() if c])
  173 
  174     def __sub__(self, other):
  175         """
  176         self - other
  177         """
  178         dif_coeff = dict(iter(self))
  179         for term, coeff in other:
  180             if term in dif_coeff:
  181                 dif_coeff[term] -= coeff
  182             else:
  183                 dif_coeff[term] = -coeff
  184         return self.construct_with_default([(d, c) for (d, c) in dif_coeff.iteritems() if c])
  185 
  186     def __mul__(self, other):
  187         """
  188         self * other
  189 
  190         If type of other is Polynomial, do multiplication in ring.
  191         Otherwise, do scalar multiplication.
  192         """
  193         if isinstance(other, PolynomialInterface):
  194             return self.ring_mul(other)
  195         else:
  196             try:
  197                 return self.scalar_mul(other)
  198             except TypeError:
  199                 return NotImplemented
  200 
  201     def __rmul__(self, other):
  202         """
  203         other * self
  204 
  205         If type of other does not support multiplication with self
  206         from left, this method is called.  In the context, it is only
  207         posiible that other be a scalar.
  208         """
  209         try:
  210             return self.scalar_mul(other)
  211         except TypeError:
  212             return NotImplemented
  213 
  214     def __neg__(self):
  215         """
  216         -self
  217         """
  218         return self.construct_with_default([(d, -c) for (d, c) in self])
  219 
  220     def __pos__(self):
  221         """
  222         +self
  223         """
  224         return self.construct_with_default(self._coefficients)
  225 
  226     def square(self):
  227         """
  228         Return the square of self.
  229         """
  230         # zero
  231         if not self:
  232             return self
  233         data_length = len(self._coefficients)
  234         # monomial
  235         if data_length == 1:
  236             return self.construct_with_default([(d*2, c**2) for (d, c) in self])
  237         # binomial
  238         if data_length == 2:
  239             (d1, c1), (d2, c2) = self.terms()
  240             return self.construct_with_default({d1*2:c1**2, d1+d2:c1*c2*2, d2*2:c2**2})
  241         # general (inefficient)
  242         items = self._coefficients.items()
  243         fst, snd = {}, {}
  244         if data_length & 1:
  245             b, c = items.pop()
  246             fst[b] = c
  247         while items:
  248             b, c = items.pop()
  249             fst[b] = c
  250             b, c = items.pop()
  251             snd[b] = c
  252         fst = self.__class__(fst, **self._init_kwds)
  253         snd = self.__class__(snd, **self._init_kwds)
  254         mid = fst.ring_mul(snd.scalar_mul(2))
  255         return fst.square() + mid + snd.square()
  256 
  257     def __pow__(self, index):
  258         """
  259         self ** index
  260         """
  261         # special indices
  262         if index < 0:
  263             raise ValueError("negative index is not allowed.")
  264         elif index == 0:
  265             for c in self.itercoefficients():
  266                 if c:
  267                     one = _ring.getRing(c).one
  268                     break
  269             else:
  270                 one = 1
  271             return self.construct_with_default({0: one})
  272         elif index == 1:
  273             return self
  274         elif index == 2:
  275             return self.square()
  276         # special polynomials
  277         if not self:
  278             return self
  279         elif len(self._coefficients) == 1:
  280             return self.construct_with_default([(d*index, c**index) for (d, c) in self])
  281         # general
  282         power_product = self.construct_with_default({0: 1})
  283         power_of_2 = self
  284         while index:
  285             if index & 1:
  286                 power_product *= power_of_2
  287             index //= 2
  288             if index:
  289                 power_of_2 = power_of_2.square()
  290         return power_product
  291 
  292     def __call__(self, val):
  293         """
  294         substitution
  295         """
  296         items = self._coefficients.items()
  297         if not items:
  298             return 0*val
  299         d, c = items.pop()
  300         result = c * val**d
  301         for d, c in items:
  302             result += c * val**d
  303         return result
  304 
  305     def iterterms(self):
  306         """
  307         iterator for (degree, coefficient) pairs.
  308         The iterator is equivalent to
  309           zip(self.iterbases(), self.itercoefficients())
  310         """
  311         return self._coefficients.iteritems()
  312 
  313     def itercoefficients(self):
  314         """
  315         iterator for coefficients.
  316         """
  317         return self._coefficients.itervalues()
  318 
  319     def iterbases(self):
  320         """
  321         iterator for degrees.
  322         """
  323         return self._coefficients.iterkeys()
  324 
  325     def __getitem__(self, degree):
  326         """
  327         Return the coefficient of specified degree.
  328         If there is no term of degree, return 0.
  329         """
  330         return self._coefficients.get(degree, 0)
  331 
  332     def __contains__(self, degree):
  333         """
  334         Return True if there is a term of specified degree.
  335         False otherwise.
  336         """
  337         return degree in self._coefficients
  338 
  339     def __len__(self):
  340         """
  341         Return the number of data entries.
  342         """
  343         return len(self._coefficients)
  344 
  345     def __eq__(self, other):
  346         """
  347         self == other
  348         """
  349         if self is other:
  350             return True
  351         return PolynomialInterface.__eq__(self, other)
  352 
  353     def __hash__(self):
  354         return PolynomialInterface.__hash__(self)
  355 
  356     def __repr__(self): # for debug
  357         return "%s(%s)" % (self.__class__.__name__, repr(self._coefficients))
  358 
  359 
  360 class SortedPolynomial (PolynomialInterface):
  361     """
  362     SortedPolynomial stores terms of a polynomial in sorted manner.
  363     All methods and operations keep it sorted.
  364     """
  365     def __init__(self, coefficients, _sorted=False, **kwds):
  366         """
  367         SortedPolynomial(coefficients)
  368 
  369         'coefficients' can be any dict initial values.
  370         Optionally '_sorted' can be True if the coefficients is
  371         already sorted.
  372         """
  373         PolynomialInterface.__init__(self, coefficients, **kwds)
  374         self.sorted = []
  375         if not _sorted or isinstance(coefficients, dict):
  376             for t in dict(coefficients).iteritems():
  377                 self._insort(t)
  378         else:
  379             self.sorted = list(coefficients)
  380         self._init_kwds = kwds
  381         self._init_kwds['_sorted'] = True
  382 
  383     def _insort(self, term):
  384         """
  385         Insert the term into self.seorted list, and keep it sorted.
  386 
  387         - This method is destructive.
  388         - This method is not in a part of the API.
  389         """
  390         self.sorted.insert(self._bisect(term[0]), term)
  391 
  392     def _bisect(self, degree):
  393         """
  394         Return the index where to insert term of degree.
  395 
  396         - This method is not in a part of the API.
  397         - The code is just adapting bisect.bisect_right to the
  398           context.
  399         """
  400         lo, hi = 0, len(self.sorted)
  401         while lo < hi:
  402             mid = (lo + hi) >> 1
  403             if degree < self.sorted[mid][0]:
  404                 hi = mid
  405             else:
  406                 lo = mid + 1
  407         return lo
  408 
  409     def __pos__(self):
  410         """
  411         +self
  412         """
  413         return self.construct_with_default(self.sorted)
  414 
  415     def __neg__(self):
  416         """
  417         -self
  418         """
  419         return self.construct_with_default([(d, -c) for (d, c) in self])
  420 
  421     def __add__(self, other):
  422         """
  423         self + other
  424         """
  425         if self.sorted:
  426             iter_self = iter(self.sorted)
  427             self_term = iter_self.next()
  428         else:
  429             self_term = None
  430         if other.sorted:
  431             iter_other = iter(other.sorted)
  432             other_term = iter_other.next()
  433         else:
  434             other_term = None
  435         sorted = []
  436         while self_term and other_term:
  437             compared = cmp(self_term[0], other_term[0])
  438             if compared < 0:
  439                 sorted.append(self_term)
  440                 try:
  441                     self_term = iter_self.next()
  442                 except StopIteration:
  443                     self_term = None
  444                     break
  445             elif compared == 0:
  446                 c = self_term[1] + other_term[1]
  447                 if c:
  448                     sorted.append((self_term[0], c))
  449                 try:
  450                     self_term = iter_self.next()
  451                 except StopIteration:
  452                     self_term = None
  453                 try:
  454                     other_term = iter_other.next()
  455                 except StopIteration:
  456                     other_term = None
  457                 if self_term is None or other_term is None:
  458                     break
  459             else:
  460                 sorted.append(other_term)
  461                 try:
  462                     other_term = iter_other.next()
  463                 except StopIteration:
  464                     other_term = None
  465                     break
  466         if other_term is None and self_term:
  467             sorted.append(self_term)
  468             for term in iter_self:
  469                 sorted.append(term)
  470         elif self_term is None and other_term:
  471             sorted.append(other_term)
  472             for term in iter_other:
  473                 sorted.append(term)
  474         return self.construct_with_default(sorted)
  475 
  476     def __sub__(self, other):
  477         """
  478         self - other
  479 
  480         It is something like merge sort.
  481         """
  482         if self.sorted:
  483             iter_self = iter(self.sorted)
  484             self_term = iter_self.next()
  485         else:
  486             self_term = None
  487         if other.sorted:
  488             iter_other = iter(other.sorted)
  489             other_term = iter_other.next()
  490         else:
  491             other_term = None
  492         sorted = []
  493         while self_term and other_term:
  494             compared = cmp(self_term[0], other_term[0])
  495             if compared < 0:
  496                 sorted.append(self_term)
  497                 try:
  498                     self_term = iter_self.next()
  499                 except StopIteration:
  500                     self_term = None
  501                     break
  502             elif compared == 0:
  503                 c = self_term[1] - other_term[1]
  504                 if c:
  505                     sorted.append((self_term[0], c))
  506                 try:
  507                     self_term = iter_self.next()
  508                 except StopIteration:
  509                     self_term = None
  510                 try:
  511                     other_term = iter_other.next()
  512                 except StopIteration:
  513                     other_term = None
  514                 if self_term is None or other_term is None:
  515                     break
  516             else:
  517                 sorted.append((other_term[0], -other_term[1]))
  518                 try:
  519                     other_term = iter_other.next()
  520                 except StopIteration:
  521                     other_term = None
  522                     break
  523         if other_term is None and self_term:
  524             sorted.append(self_term)
  525             for term in iter_self:
  526                 sorted.append(term)
  527         elif self_term is None and other_term:
  528             sorted.append((other_term[0], -other_term[1]))
  529             for term in iter_other:
  530                 sorted.append((term[0], -term[1]))
  531         return self.construct_with_default(sorted)
  532 
  533     def __mul__(self, other):
  534         """
  535         self * other
  536 
  537         If type of other is SortedPolynomial, do multiplication
  538         in ring.  Otherwise, do scalar multiplication.
  539         """
  540         if isinstance(other, PolynomialInterface):
  541             return self.ring_mul(other)
  542         else:
  543             try:
  544                 return self.scalar_mul(other)
  545             except TypeError:
  546                 return NotImplemented
  547 
  548     def __rmul__(self, other):
  549         """
  550         other * self
  551 
  552         If type of other does not support multiplication with self
  553         from left, this method is called.  In the context, it is only
  554         posiible that other be a scalar.
  555         """
  556         try:
  557             return self.scalar_mul(other)
  558         except TypeError:
  559             return NotImplemented
  560 
  561     def ring_mul_karatsuba(self, other):
  562         """
  563         Multiplication of two polynomials in the same ring.
  564 
  565         Computation is carried out by Karatsuba method.
  566         """
  567         polynomial = self.construct_with_default
  568         # zero
  569         if not self or not other:
  570             return polynomial(())
  571         # monomial
  572         if len(self.sorted) == 1:
  573             return other.term_mul(self)
  574         if len(other.sorted) == 1:
  575             return self.term_mul(other)
  576         # binomial
  577         if len(self.sorted) == 2:
  578             p, q = [other.term_mul(term) for term in self]
  579             return p + q
  580         if len(other.sorted) == 2:
  581             p, q = [self.term_mul(term) for term in other]
  582             return p + q
  583         # suppose self is black and other is red.
  584         black_left_degree, black_right_degree = self.sorted[0][0], self.sorted[-1][0]
  585         red_left_degree, red_right_degree = other.sorted[0][0], other.sorted[-1][0]
  586         left_degree = min(black_left_degree, red_left_degree)
  587         right_degree = max(black_right_degree, red_right_degree)
  588         # we assert here that order is of ascending. (is it correct?)
  589         assert left_degree < right_degree
  590         half_degree = (left_degree + right_degree) >> 1
  591         black_half_index = self._bisect(half_degree)
  592         red_half_index = other._bisect(half_degree)
  593         if not black_half_index:
  594             return (self.downshift_degree(black_left_degree).ring_mul_karatsuba(other)).upshift_degree(black_left_degree)
  595         if not red_half_index:
  596             return (self.ring_mul_karatsuba(other.downshift_degree(red_left_degree))).upshift_degree(red_left_degree)
  597         club = polynomial([(d - left_degree, c) for (d, c) in self.sorted[:black_half_index]])
  598         spade = polynomial([(d - half_degree, c) for (d, c) in self.sorted[black_half_index:]])
  599         dia = polynomial([(d - left_degree, c) for (d, c) in other.sorted[:red_half_index]])
  600         heart = polynomial([(d - half_degree, c) for (d, c) in other.sorted[red_half_index:]])
  601         weaker = club.ring_mul_karatsuba(dia)
  602         stronger = spade.ring_mul_karatsuba(heart)
  603         karatsuba = (club + spade).ring_mul_karatsuba(dia + heart) - weaker - stronger
  604         if left_degree:
  605             return (weaker.upshift_degree(left_degree * 2) +
  606                     karatsuba.upshift_degree(left_degree + half_degree) +
  607                     stronger.upshift_degree(half_degree * 2))
  608         else:
  609             return (weaker +
  610                     karatsuba.upshift_degree(half_degree) +
  611                     stronger.upshift_degree(half_degree * 2))
  612 
  613     def scalar_mul(self, scale):
  614         """
  615         Return the result of scalar multiplication.
  616         """
  617         keep_ring = True
  618         if "coeffring" in self._init_kwds:
  619             new_coeff = []
  620             coeffring = self._init_kwds["coeffring"]
  621             for d, c in self:
  622                 if c:
  623                     scaled = c * scale
  624                     if keep_ring and scaled not in coeffring:
  625                         coeffring = coeffring.getCommonSuperring(_ring.getRing(scaled))
  626                     new_coeff.append((d, scaled))
  627             self._init_kwds["coeffring"] = coeffring
  628         else:
  629             new_coeff = [(d, c * scale) for (d, c) in self if c]
  630         return self.construct_with_default(new_coeff)
  631 
  632     def square(self):
  633         """
  634         Return the square of self.
  635         """
  636         # zero
  637         if not self:
  638             return self
  639 
  640         polynomial = self.construct_with_default
  641         data_length = len(self.sorted)
  642         # monomial
  643         if data_length == 1:
  644             d, c = self.sorted[0]
  645             if d:
  646                 return polynomial([(d*2, c**2)])
  647             else:
  648                 return polynomial([(0, c**2)])
  649         # binomial
  650         if data_length == 2:
  651             (d1, c1), (d2, c2) = [(d, c) for (d, c) in self]
  652             return polynomial({d1*2:c1**2, d1+d2:c1*c2*2, d2*2:c2**2})
  653         # general (Karatsuba)
  654         right_degree = self.sorted[-1][0]
  655         left_degree = self.sorted[0][0]
  656         half_degree = (right_degree + left_degree) >> 1
  657         half_index = self._bisect(half_degree)
  658         fst = polynomial([(d - left_degree, c) for (d, c) in self.sorted[:half_index]])
  659         snd = polynomial([(d - half_degree, c) for (d, c) in self.sorted[half_index:]])
  660         fst_squared = fst.square()
  661         snd_squared = snd.square()
  662         karatsuba = (fst + snd).square() - fst_squared - snd_squared
  663         if left_degree:
  664             return (fst_squared.upshift_degree(left_degree * 2) +
  665                     karatsuba.upshift_degree(left_degree + half_degree) +
  666                     snd_squared.upshift_degree(half_degree * 2))
  667         else:
  668             return (fst_squared +
  669                     karatsuba.upshift_degree(half_degree) +
  670                     snd_squared.upshift_degree(half_degree * 2))
  671 
  672     def __pow__(self, index):
  673         """
  674         self ** index
  675 
  676         No ternary powering is defined here, because there is no
  677         modulus operator defined.
  678         """
  679         # special indices
  680         if index < 0:
  681             raise ValueError("negative index is not allowed.")
  682         elif index == 0:
  683             for c in self.itercoefficients():
  684                 if c:
  685                     one = _ring.getRing(c).one
  686                     break
  687             else:
  688                 one = 1
  689             return self.construct_with_default([(0, one)])
  690         elif index == 1:
  691             return self
  692         elif index == 2:
  693             return self.square()
  694         # special polynomials
  695         if not self:
  696             return self
  697         elif len(self.sorted) == 1:
  698             return self.construct_with_default([(d*index, c**index) for (d, c) in self])
  699         # general
  700         power_product = self.construct_with_default([(0, 1)])
  701         power_of_2 = self
  702         while index:
  703             if index & 1:
  704                 power_product *= power_of_2
  705             index //= 2
  706             if index:
  707                 power_of_2 = power_of_2.square()
  708         return power_product
  709 
  710     def degree(self):
  711         """
  712         Return the degree of self
  713         """
  714         assert self.sorted == sorted(self.sorted)
  715         for d, c in self.sorted[::-1]:
  716             if c:
  717                 return d
  718         return -1
  719 
  720     def leading_coefficient(self):
  721         """
  722         Return the leading coefficient
  723         """
  724         assert self.sorted == sorted(self.sorted)
  725         for d, c in self.sorted[::-1]:
  726             if c:
  727                 return c
  728         return 0
  729 
  730     def leading_term(self):
  731         """
  732         Return the leading term as a tuple (degree, coefficient).
  733         """
  734         assert self.sorted == sorted(self.sorted)
  735         for d, c in self.sorted[::-1]:
  736             if c:
  737                 return (d, c)
  738         return (-1, 0)
  739 
  740     def iterterms(self):
  741         """
  742         iterator for (base, coefficient) pairs.
  743         The iterator is equivalent to
  744           zip(self.iterbases(), self.itercoefficients())
  745         """
  746         return iter(self.sorted)
  747 
  748     def iterbases(self):
  749         """
  750         iterator for bases.
  751         """
  752         for term in self.sorted:
  753             yield term[0]
  754 
  755     def itercoefficients(self):
  756         """
  757         iterator for coefficients.
  758         """
  759         for term in self.sorted:
  760             yield term[1]
  761 
  762     def __getitem__(self, degree):
  763         """
  764         Return the coefficient of specified degree.
  765         If there is no term of degree, return 0.
  766         """
  767         if self.sorted:
  768             rindex = self._bisect(degree)
  769             if self.sorted[rindex - 1][0] == degree:
  770                 return self.sorted[rindex - 1][1]
  771         return 0
  772 
  773     def __contains__(self, degree):
  774         """
  775         Return True if there is a term of specified degree.
  776         False otherwise.
  777         """
  778         rindex = self._bisect(degree)
  779         if self.sorted[rindex - 1][0] == degree:
  780             return True
  781         return False
  782 
  783     def __len__(self):
  784         """
  785         Return the number of data entries.
  786         """
  787         return len(self.sorted)
  788 
  789     def __eq__(self, other):
  790         """
  791         self == other
  792         """
  793         if self is other:
  794             return True
  795         if not isinstance(other, SortedPolynomial):
  796             return PolynomialInterface.__eq__(self, other)
  797         if [t for t in self if t[1]] == [t for t in other if t[1]]:
  798             return True
  799         return False
  800 
  801     def __hash__(self):
  802         val = sum([hash(t) for t in self if t[1]])
  803         return val
  804 
  805     def __call__(self, val):
  806         """
  807         substitution
  808         """
  809         items = list(self.sorted)
  810         if not items:
  811             return 0 * val
  812         val_pow = {1:val}
  813         d, c = items.pop()
  814         result = c
  815         while len(items) > 0:
  816             (e, f) = items.pop()
  817             result = result * val_pow.setdefault(d - e, val ** (d - e)) + f
  818             d = e
  819         if d:
  820             return result * val_pow.get(d, val ** d)
  821         else:
  822             return result
  823 
  824     def __repr__(self): # debug
  825         return repr(self.sorted)