Class based polynomials with magic methods

Updated TrustyTony 1 Tallied Votes 1K Views Share

There was discussion thread http://www.daniweb.com/software-development/python/threads/424953/polynomial-division for class based implementation for polynomials, and I developed a version utilizing the magic methods to enable operation with normal arithmetic operation. I only inherited sequence structure from list type. Interoperability with scalar types is not implemented to avoid too complicated type checks of the arithmetic operations.

Division will be added when the OP has made his own solution of it ready. Tests are continued to be run and I will update the code with bug fixes if and when I find any. I have done informal tests but not yet exhaustive ones.

Multiplying by scalars is however in TODO list, not yet implemented.

EDITS:
1. Updated comment from Monomials to Terms
2. Removed spacing beside () in str format for polynomial to be more PEP8 style.
3. Moved the current version to reply thread and replaced with new code whose description below.

END OF OLD VERSION
________________________________

VERSION WITH DIVISION AND MULTIPLICATION BY SCALAR

The original poster has not posted for some time and his thread was started three weeks ago, so I consider now proper time to post better version of the code even he did not post his version of division code. I have added appropriate rmul method to handle the multiplication by integer and added the long division routine adapted to computer so that if remainder is of higher order than the divisor, it is redivided by divisor and the result is added to result, leaving finally the real remainder. I found this easier than try to drop down terms from remainder and adding zero coefficient polynomials (which the simplification code eliminates, without extra mode for keeping them).

I found the resultant division routine quite satisfying, hope you like it also. It could be considered quite creative because of this adaption. Another creative aspect is to treat Term as Polynomial of length one by giving it ability to report length of one and iterate itself by giving its value. Quite like in physics a vector of length one is considered same as scalar value. If you find some fault in code which I did not find, please report it. Best present you can give for programmer in addition to kudos is to send him bug reports!

The comparision routine is changed from old cmp style to new style by help of the functools.total_ordering, so now this snippet also serves as example of that.

This new version contains as test cases basically all googled examples of polynomial long division I found from first pages of search results.

Test output:

------------------- SQUARE BY MULTIPLICATION -------------------
(x - 1) * (x - 1) = (x^2 - 2x + 1)

--------------------- POWER AND EVALUATION ---------------------
((-5x^3 + 32x^2 + 6) ** 8)(3) = 408485828788939521

------------------------ SCALAR SCALING ------------------------
(42x^5 + x^2) * 4.3 = (180.6x^5 + 4.3x^2)
4.3 * (42x^5 + x^2) = (180.6x^5 + 4.3x^2)
(42x^5 + x^2) / 4.3 = (9.76744186047x^5 + 0.232558139535x^2)

------------------ ADDING/SUBSTRACTION SCALAR ------------------
(42x^5 + x^2) + 4.3 = (42x^5 + x^2 + 4.3)
4.3 + (42x^5 + x^2) = (42x^5 + x^2 + 4.3)
(42x^5 + x^2) - 4.3 = (42x^5 + x^2 - 4.3)
4.3 - (42x^5 + x^2) = (-42x^5 - x^2 + 4.3)

----------------- LONG DIVISION WITH REMAINDER -----------------
(x^3 - 12x^2 - 42) / (x - 3) = (x^2 - 9x - 27)  * (x - 3) + (-123)

Inexact repr:
(x^2 - 1.73205080757) / (1.41421356237x^2 + 1) = (0.707106781187)  * (1.41421356237x^2 + 1) + (-2.43915758876)
(x^3 + 2x^2 - 25x - 50) / (x + 5) = (x^2 - 3x - 10) 
(6x^3 - 8x + 5) / (2x - 4) = (3x^2 + 6x + 8)  * (2x - 4) + (37)
(3x^3 - x^2 + x - 2) / (x + 2) = (3x^2 - 7x + 15)  * (x + 2) + (-32)
(x^4 - 1) / (x - 1) = (x^3 + x^2 + x + 1) 
(x^3 - 2x^2 + 3x + 1) / (-4x^2 + 7x + 12) = (-0.25x + 0.0625)  * (-4x^2 + 7x + 12) + (5.5625x + 0.25)
(x^6 + 2x^4 + 6x - 9) / (x^3 + 3) = (x^3 + 2x - 3) 
(2x^5 - 5x^4 + 7x^3 + 4x^2 - 10x + 11) / (x^3 + 2) = (2x^2 - 5x + 7)  * (x^3 + 2) + (-3)
(6x^2 - 17x + 12) / (3x - 4) = (2x - 3) 
(10x^5 + x^3 + 5x^2 - 2x - 2) / (5x^2 - 2) = (2x^3 + x + 1) 
(2x^3 - x^2 - 13x + 9) / (x - 2) = (2x^2 + 3x - 7)  * (x - 2) + (-5)
(5x^3 + 3x^2 + 8x - 8) / (5x - 2) = (x^2 + x + 2)  * (5x - 2) + (-4)
(6x^3 - 13x^2 - 4x + 35) / (3x + 4) = (2x^2 - 7x + 8)  * (3x + 4) + (3)
(5x^4 - 13x^3 + 21x^2 + x + 10) / (5x - 3) = (x^3 - 2x^2 + 3x + 2)  * (5x - 3) + (16)
(6x^4 + 11x^3 - 7x^2 - 15x - 50) / (3x + 7) = (2x^3 - x^2 - 5)  * (3x + 7) + (-15)
(x^2 + 2x - 15) / (x + 5) = (x - 3) 
(5x^3 - x^2 + 6) / (x - 4) = (5x^2 + 19x + 76)  * (x - 4) + (310)
(2x^3 - 3x - 5) / (x + 2) = (2x^2 - 4x + 5)  * (x + 2) + (-15)
(4x^4 - 10x^2 + 1) / (x - 6) = (4x^3 + 24x^2 + 134x + 804)  * (x - 6) + (4825)
(3x^3 - 2x^2 + 4x - 3) / (x^2 + 3x + 3) = (3x - 11)  * (x^2 + 3x + 3) + (28x + 30)
(x^3 - 1) / (x + 2) = (x^2 - 2x + 4)  * (x + 2) + (-9)
----------------- REMAINDER AND FLOOR DIVISION -----------------
(x^3 - 1) % (x + 2) = (-9)
(x^3 - 1) // (x + 2) = (x^2 - 2x + 4)

EDIT:

  1. Based on Mike_2000_17's suggestion removed overcautious simplify calls and added x variable as Term(1,1) for expression form Polynomials.
  2. Added __radd__ = __add__ to enable number in left side of addition with Term (1 + x etc.)
  3. Moved sorting out of simplify to Polynomial.__init__ and changed to heapq.merge in division and addition, removed inexact comparision for checking of repr to get more proper total ordering.
  4. Also put multiplication to use merge procedúre form, changed substraction of Term to use addition and negation (probably it will be slower than repeating the code, but should not be so bad, used this way in Polynomial class allready)
  5. Removed even the simplify from the end of long division
  6. Added __rsub__ and __radd__ (to Polynomial also)
  7. Removed unnecessary __eq__ from polynomial (list comparisions inherited suffice if sides are reverse sorted)
  8. Unused import of chain removed
  9. Incorrect <= changed to < in __lt__ of Term (worked because of other != condition, but confusing)
mike_2000_17 commented: clean and simple, nice! +13
# To run without assert tests run with -O command line option!

from functools import total_ordering
from heapq import merge

exp_sign = '^'

#use decorator to define other comparisions from __eq__ and __lt__
@total_ordering
class Term(object):
    """ Primitive term of single variable x,
        contains coeficient and exponent slots.
        Exponent must be positive integer.
        There are many zero values as each zero
        coeficient value is zero in value.

    """
    __slots__ = 'coeficient', 'exponent'
    def __init__(self, coeficient=0, exponent=0):
        self.coeficient = coeficient

        if isinstance(exponent, int):
            self.exponent = exponent
        else:
            raise ValueError('Exponent must be integer!')

    def __nonzero__(self):
        return bool(self.coeficient)

    # allow single term to used in place of Polynomial
    # by treating it single value iterable
    def __iter__(self):
        yield self

    def __len__(self):
        return 1

    # mathematical operations to enable the use of normal operators
    def __neg__(self):
        return Term(-self.coeficient, self.exponent)

    def __abs__(self):
        return -self if self.coeficient < 0 else self

    def __add__(self, other):
        if hasattr(other, 'exponent') and self.exponent == other.exponent:
            return Term(self.coeficient + other.coeficient, self.exponent )
        else:
            return Polynomial(self) + Polynomial(other)

    # to enable number + Term() expressions
    __radd__ = __add__

    def __sub__(self, other):
        return self + -other

    __rsub__ = __sub__

    def __mul__(self, other):
        if not self or not other:
            # zero (empty) polynomial
            r = Polynomial()
        elif hasattr(other, 'exponent'):
            r = Term(self.coeficient * other.coeficient,
                     self.exponent + other.exponent)
        # scalar multiplication
        elif not isinstance(other, (Term, Polynomial)):
            r = self * Term(other)
        else:
            r = Polynomial(other) * self
        return r

    # to handle 3.4 * Term(1,1) kind of expressions, we need __rmul__ also, simple assignement is enough
    __rmul__ = __mul__

    def __div__(self, other):
        """ division considering the possibility that
            coeficients do not divide exactly
            and changing to floats in this case

        """
        if not hasattr(other, 'exponent'):
            other = Term(other)
        if other.exponent > self.exponent:
            message = "divisor of higher degree than dividend: %s vs %s"
            raise ValueError(message % (self, other))
        return Term((float(self.coeficient)
                     if self.coeficient % other.coeficient
                     else self.coeficient) / other.coeficient,
                    self.exponent - other.exponent)

    def __pow__(self, n):
        return Term(self.coeficient**n, self.exponent*n)

    def __str__(self):
        """ 1 as coeficient shown only for exponent 0 (constant),
            exponent 1 not shown

        """
        return ((str(self.coeficient)
                 if self.coeficient != 1 or self.exponent == 0
                 else '') +
                ((("x%s%i" % (exp_sign, self.exponent))
                  if self.exponent and self.coeficient else '')
                 if self.exponent != 1  else 'x'))

    def __repr__(self):
        """Show all zero coefficient Terms as Terms() except True zero"""
        return ('Term(%s, %i)' % (self.coeficient, self.exponent)
                if self.coeficient or self.exponent==0 else 'Term()')
    # Comparison
    def __lt__(self, other):
        """ Used in conjunction to functools.totalordering and __eq__

        """
        if not isinstance(other, Term):
            other = Term(other)

        return  self.exponent < other.exponent if self.exponent != other.exponent else self.coeficient < other.coeficient

    def __eq__(self, other):
        return ((self.exponent == other.exponent) and
                (self.coeficient == other.coeficient))

class Polynomial(list):
    """ representation of Polynomial as sum of Terms
        simplify method adds same degree Terms and
        eliminates zero terms

    """

    def __init__(self, *args):
        if len(args) == 1:
            if isinstance(args[0], (Polynomial, list)):
                args = args[0]
            elif not isinstance(args[0], Term):
                args=Polynomial(Term(args[0]))

        self[:] = args
        self.sort(reverse=True)
        self.simplify()

    #output formats
    def __str__(self):
        """ shows the Term list on screen """
        r = '('
        for v in self:
            # separate sign for use as minus between Terms except for first term
            r +=  ('%s%s' % ( (' - ' if r != '(' else '-') if v.coeficient < 0
                               else (' + ' if r != '(' else ''),
                               # do not show + 0 for Terms with Zero coeficient
                               abs(v)) if v.coeficient else ''
                   )
        return r + ')'

    #evaluable string to produce same Polynomial
    def __repr__(self):
        return 'Polynomial(%s)' % ', '.join(repr(v) for v in self)

    @property
    def degree(self):
        return 0 if not self else self[0].exponent

    def simplify(self):
        """ Assumes sorted self,
            combines equal exponents and removes zero coeficient terms

        """
        i = 0
        while i <= len(self) - 1:
            # while so that the result of combining of exponents is pruned if zero coeficient
            # and to avoid problem in changing the sequence of self
            if i < len(self) - 1 and self[i].exponent == self[i+1].exponent:
                self[i] =  self[i] + self[i+1]
                del self[i+1]
            elif not self[i].coeficient:
                del self[i]
            else:
                i += 1
        # self is changed, but might be usefull to be able to use as function instead of returning None
        return self

    def horner(self, x):
        """ A function that implements the Horner Scheme
            for evaluating a polynomial
            http://en.wikipedia.org/wiki/Horner_scheme

            adapted to the sparse format of Polynomial class

        """
        m = iter(self)
        p = next(m)
        result = 0
        try:
            for n in reversed(range(self.degree+1)):
                if p.exponent == n:
                    result = result * x + p.coeficient
                    p = next(m)
                else:
                    result *= x
        except StopIteration:
            # missing lowest powers
            return result * x ** n
        else:
            return result

    # enable the polynomial to be used as function by
    # defining __call__ method
    __call__ = evaluate = horner

    def __neg__(self):
        return Polynomial(*(-v for v in self))

    def __add__(self, other):
        if  not hasattr(other, '__len__'):
            # handle integer or float other
            other = Term(other)
        r = Polynomial(list(merge(self, other)))
        return r

    __radd__ = __add__
        
    def __sub__(self,other):
        return self + -other

    def __rsub__(self, other):
        return -self + other


    def __pow__(self, n):
        """ recursive binary power algorithm

            x ** n = (x ** (n//2)) ** 2 if n even, else
            same but multiply result with x
        """
        if n != int(n) or n < 0:
            raise ValueError('Invalid power exponent: %s' % n)
        elif n == 0:
            return Polynomial(Term(1))
        elif n == 1:
            return self
        else:
            r = (self**(n//2))
            r *= r
            if n & 1:
                r *= self
            return r
        
    def __mul__(self, other):
        if not isinstance(other, (Term, Polynomial)):
            other = Term(other)
        return Polynomial(list(merge(*([a * b for a in self] for b in other))))
    
    __rmul__ = __mul__
    
    def __div__(self, other):
        if not isinstance(other, (Term, Polynomial)):
            return self * (1./other)
        else:
            print('%s vs. %s' % (self, other))
            raise ValueError('Division only by scalar, use divmod!')

    def __divmod__(self, other):
        if not isinstance(other, (Term, Polynomial)):
            return self * (1./other)
        remainder = Polynomial(self)
        result = Polynomial()
        for drop in self:
            try:
                n = remainder[0] / other[0]
            except ValueError:
                # negative exponent
                break
            else:
                remainder -= n * other
                result.append(n)
                if not remainder:
                    break
        else:
            # deal with higher degree left overs from subresults
            if remainder.degree >= other.degree:
                extra, remainder = divmod(remainder, other)
                # http://www.daniweb.com/software-development/python/code/325235/merge-sorted-iterables#post1389338
                result = Polynomial(*merge(extra, result))

        assert result * other + remainder == self
        return result, remainder

    def __mod__(self, other):
        return divmod(self, other)[1]

    def __floordiv__(self, other):
        return divmod(self, other)[0]
    
# using expression syntax to build terms to polynomial by defining x as 1*x**1
# thanks to mike_2000_17
x = Term(1,1)

if __name__ == '__main__':
    line_width = 64

    # tests for variaty of forms of initializing Term and Polynomial classes
    m = Term(5,2)
    p = m + Term(4,2) + Term(4) + Polynomial(Term(23, 2), Term(2,0), Term(-5, 3))
    x1 = Polynomial(Term(1,1), Term(-1))
    t, f = Polynomial(Term(42,5), Term(1,2)), 4.3

    print ' SQUARE BY MULTIPLICATION '.center(line_width, '-')
    print '%s * %s = %s' % (x1,x1, x1 * x1)
    print
    print ' POWER AND EVALUATION '.center(line_width, '-')
    print '(%s ** %i)(3) = %s' % (p, 8, (p ** 8).evaluate(3))
    print
    print ' SCALAR SCALING '.center(line_width, '-')
    print '%s * %s = %s' % (t, f, t * f)
    print '%s * %s = %s' % (f, t, f * t)
    print '%s / %s = %s' % (t, f, t / f)
    print
    print ' ADDING/SUBSTRACTION SCALAR '.center(line_width, '-')
    print '%s + %s = %s' % (t, f, t + f)
    print '%s + %s = %s' % (f, t, f + t)
    print '%s - %s = %s' % (t, f, t - f)
    print '%s - %s = %s' % (f, t, f - t)
    print
    print ' LONG DIVISION WITH REMAINDER '.center(line_width, '-')

    for m, d in (
         # example of using x variable for building polynomial from expression
         ((x ** 3 - 12 * x ** 2 - 42) , x - 3),
         ((x ** 2 - 3 ** 0.5), 2 ** 0.5 * x ** 2 + 1),
         # http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut36_longdiv.htm
         (Polynomial(Term(1, 3), Term(2,2), Term(-25, 1), Term(-50)), Polynomial(Term(1,1), Term(5))),
         (Polynomial(Term(6,3), Term(-8,1), Term(5)), Polynomial(Term(2,1), Term(-4))),
         (Polynomial(Term(3,3), Term(-1, 2), Term(1,1), Term(-2)), Polynomial(Term(1,1), Term(2))),
         (Polynomial(Term(1,4), Term(-1)), Polynomial(Term(1,1), Term(-1))),
         (Polynomial(Term(1,3), Term(-2,2), Term(3,1), Term(1)), Polynomial(Term(-4, 2), Term(7,1), Term(12))),
         (Polynomial(Term(1, 6), Term(2, 4), Term(6, 1), Term(-9)), Polynomial(Term(1, 3), Term(3))),
         # http://www.mathopolis.com/questions/q.php?id=353
         (Polynomial(Term(2, 5), Term(-5, 4), Term(7, 3), Term(4,2), Term(-10, 1), Term(11)), Polynomial(Term(1,3), Term(2))),
         (Polynomial(Term(6,2), Term(-17, 1), Term(12)), Polynomial(Term(3, 1), Term(-4))),
         (Polynomial(Term(10, 5), Term(1, 3), Term(5, 2), Term(-2, 1), Term(-2)), Polynomial(Term(5, 2), Term(-2))),
         (Polynomial(Term(2, 3), Term(-1, 2), Term(-13, 1), Term(9)), Polynomial(Term(1, 1), Term(-2))),
         (Polynomial(Term(5, 3), Term(3, 2), Term(8, 1), Term(-8)), Polynomial(Term(5,1), Term(-2))),
         (Polynomial(Term(6, 3), Term(-13, 2), Term(-4, 1), Term(35)), Polynomial(Term(3, 1), Term(4))),
         (Polynomial(Term(5, 4), Term(-13,3), Term(21, 2), Term(1, 1), Term(10)), Polynomial(Term(5,1), Term(-3))),
         (Polynomial(Term(6, 4), Term(11, 3), Term(-7, 2), Term(-15, 1), Term(-50)), Polynomial(Term(3,1), Term(7))),
         (Polynomial(Term(1,2), Term(2, 1), Term(-15)), Polynomial(Term(1,1), Term(5))),
         (Polynomial(Term(5, 3), Term(-1, 2), Term(6)), Polynomial(Term(1,1), Term(-4))),
         (Polynomial(Term(2,3), Term(-3,1), Term(-5)), Polynomial(Term(1, 1), Term(2))),
         (4 * x ** 4 - 10 * x ** 2 + 1, x - 6),
         ((3 * x ** 3 - 2 * x ** 2 + 4 * x -3), (x ** 2 + 3 * x + 3)),
         ((x ** 3 - 1), x + 2)
        ):
        if Polynomial(eval(repr(m))) != m:
            print('\nInexact repr:')
        res, rem = divmod(m, d)
        print '%s / %s = %s' % (m, d, res), ' * %s + %s' % (d, rem) if rem else ''

    print ' REMAINDER AND FLOOR DIVISION '.center(line_width, '-')
    print '%s %% %s = %s' % (m, d, m % d)
    print '%s // %s = %s' % (m, d, m // d)
TrustyTony 888 pyMod Team Colleague Featured Poster

Here the earlier version one, without division for record. I update the original for the new version.

# -*- coding: cp1252 -*-
from itertools import chain

class Term(object):
    __slots__ = 'coeficient', 'exponent'
    def __init__(self, coeficient=1.0, exponent=0):
        self.coeficient = coeficient

        if isinstance(exponent, int):
            self.exponent = exponent
        else:
            raise ValueError('Exponent must be integer!')

    def __nonzero__(self):
        return self.coeficient

    def __iter__(self):
        yield self

    def __len__(self):
        return 1

    def __neg__(self):
        return Term(-self.coeficient, self.exponent)

    def __abs__(self):
        return -self if self.coeficient < 0 else self

    def __add__(self, other):
        if hasattr(other, 'exponent') and self.exponent == other.exponent:
            return Term(self.coeficient + other.coeficient, self.exponent )
        else:
            return Polynomial(self) + Polynomial(other)

    def __sub__(self, other):
        if hasattr(other, 'exponent') and self.exponent == other.exponent:
            r = (Term(self.coeficient - other.coeficient, self.exponent) if self.coeficient != other.coeficient else Term(0))
        else:
            r = Polynomial(self) - Polynomial(other)
            r.simplify()

        return r

    def __mul__(self, other):
        if hasattr(other, 'exponent'):
            r = Term(self.coeficient * other.coeficient, self.exponent + other.exponent)
        else:
            print self, other, type(other)
            r = Polynomial(self) * Polynomial(other)
            r.simplify()
        return r


    def __div__(self, other):
        return Term(self.coeficient / other.coeficient, self.exponent - other.exponent)

    def __cmp__(self, other):
        if not isinstance(other, Term):
            other = Term(other)

        if self.exponent == other.exponent:
            if self.coeficient < other.coeficient:
                return -1
            elif self.coeficient > other.coeficient:
                return 1
            else:
                return 0

        elif self.exponent < other.exponent:
            return -1
        elif self.exponent > other.exponent:
            return 1
        else:
            return 0

    def __str__(self):
        """ 1 as coeficient shown only for exponent 0 (constant), exponent 1 not shown """
        return ((str(self.coeficient) if self.coeficient != 1 or self.exponent == 0 else '') +
                ((("X^%i" % self.exponent) if self.exponent and self.coeficient else '')
                 if self.exponent != 1  else 'x'))

    def __repr__(self):
        """Show all zero coefficient Terms as Terms() except True zero"""
        return 'Term(%s, %i)' % (self.coeficient, self.exponent) if self.coeficient or self.exponent==0 else 'Term()'


class Polynomial(list):

    def __init__(self, *args):
        if len(args) == 1:
            if args and isinstance(args[0], Polynomial):
                args=args[0]
            elif not isinstance(args[0], Term):
                args=Polynomial(Term(args[0]))

        self[:] = args 
        self.simplify()

    def __str__(self):
        #shows the Term list on screen
        r = '('
        for v in self:
             # separate sign for use as minus between Terms except for first term
             r +=  ('%s%s' % ( (' - ' if r != '(' else '-') if v.coeficient < 0
                               else (' + ' if r != '(' else ''),
                               # do not show + 0 for Terms with Zero coeficient
                               abs(v)) if v.coeficient else ''  
                   )
        return r + ')'

    def __repr__(self):
        return 'Polynomial(%s)' % ', '.join(repr(v) for v in self)

    def simplify(self):
        assert all(isinstance(item, Term) for item in self), 'Not all items are Terms: %s' % list(self)
        if len(self)<=1:
            return
        self.sort(reverse=True)
        i = 0
        while i <= len(self) - 1:
            if i < len(self) - 1 and self[i].exponent == self[i+1].exponent:
                self[i] =  self[i] + self[i+1]
                del self[i+1]
            elif not self[i].coeficient:
                del self[i] 
            else:
                i += 1
        return self

    def __neg__(self):
        return Polynomial(*(-v for v in self))

    def __add__(self, other):
        r = Polynomial(*chain(self, other))
        r.simplify()
        return r

    def __sub__(self,other):
        return self + -other

    def __pow__(self, n):
        if n != int(n) or n < 0:
            raise ValueError('Invalid power exponent: %s' % n)
        elif n == 0:
            return Term(1)
        else:
            r = self
            for c in range(n-1):
                r *= self
            return r

    def __mul__(self, other):
        p = sum((a * b for a in self for b in other), Term(0))
        p.simplify()
        return p

m = Term(5,2)
print m + Term(4,2) + Term(4) + Polynomial(Term(23, 2), Term(2,0), Term(-5, 3))
x1 = Polynomial(Term(1,1), Term(-1))

print '%s * %s = %s' % (x1,x1, x1 * x1)
print '%s ** %i = %s' % (x1, 2, x1 ** 2)
rubik-pypol 0 Newbie Poster

Very interesting. Can you post it somewhere too, so that I can copy-paste it and try it?
As a gist, for example:
https://gist.github.com

TrustyTony 888 pyMod Team Colleague Featured Poster

You just double click the post and copy/paste, no need to put it external site, where it could be removed and the link broken.

TrustyTony 888 pyMod Team Colleague Featured Poster

Seeing your previous posts on http://pypol.altervista.org/index.html I am avaiting your response with interest. Maybe you can point some loopholes in my code to improve my chances in the code snippet competition

mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster

Of course, my C++-brain cringes at the sight of all the blantant inefficiencies in the code, but if I adopt the Python mindset, then your code snippet is quite nice! Lots of demonstrations of Python-kung-fu in there.

A few comments:

I think you are not protective enough of your invariants, and you suffer from constantly breaking and repairing them. By invariants, I mean the fact that a Polynomial is always a list of terms, in a sorted order, with unique exponents only. Basically, what the "simplify" function enforces. Many of your operations on the Polynomial, like addition, substraction, multiplication, power, etc. can all be performed entirely without breaking the invariants. For example, your addition function chains the two lists of terms, which creates a "polynomial" list whose invariants are broken, and then you repair it with "simplify". You are not taking advantage of the fact that your two input Polynomials contain sorted unique-exponent terms. You could "merge" the two Polynomials very easily, resulting in another Polynomial with valid invariants, without having the "simplify" it afterwards. The whole point of having invariants in a class and protecting them through encapsulation is to be able to avoid having to constantly check or repair the invariants, and to be able to simplify operations by relying on the invariants being respected on the operands. Consider that in the future.

It would have been a lot nicer if your test program was written in easier terms by using the DSEL that you just created (DSEL: Domain-Specific Embedded Language). I see no reason why you couldn't simply construct polynomials like this:

x = Polynomial(Term(1,1))

p1 = 2 * x**2 + 4 * x + 6
p2 = 6 * x**6 + 3 * x**5 + 10 * x**3 + 23 * x**2
p3 = (x + 1) * (x**2 + 3*x + 1)

Or is there a reason why the above wouldn't be possible? If not, I think this is a much nicer way to use this Polynomial class, it is much nicer syntax than those horrible-looking expressions like Polynomial(Term(1,3), Term(-12,2), Term(-42)) instead of simply x**3 - 12 * x**2 - 42. Of course, the latter is very inefficient compared to the first, but that's not a result of the syntax, it's a result of the first problem I mentioned, which is easy to fix.

I think it would also be a nice addition to be able to parse string expressions of the same format as the to-string conversion.

TrustyTony 888 pyMod Team Colleague Featured Poster

I should look into it if it is possible to do quick operation to do merging and combining the same time the equal powers. But simplification also takes care of droping the 0 multiplier terms and it uses the C-speed sorting (minus the penalty of comparision operations defined in user class) which I would expect to not cause much penalty with typically less than 100 term polynomials case. Maybe there could be internal _simplify method wich expects the powers to be in order, only combining same order terms and dropping null terms. It could be much non-DRY code compared with simplify method and slow down by extra comparisions needed. Probably I would end up to use that inside the simplify by only moving after sorting part to this new function. That would of course hit performance of all operations by one more function call.

The idea of using not performance critical place the normal expression with x = Polynomial(Term(1,1)) but using x = Term(1,1) should be more efficient as power of Monomial is very simple compared to the binary recursive implementation of Polynomial power. That would also make it simple to do safe evaluation (see my other code snippet MathExpression) with the x variable defined only in the eval. I would do that as fallback if arguments are not of Polynomial or Term type by try...except.

I probably have also unnecessary simplify in add operation, I must recheck it (as Polynomial creation allready does simplification as terms for creation of Polynomial) I will recheck it when I get to my own computer.

This code should also be run with -O option to avoid executing the assert statements to or asserts should be commented out, if used in real world usage.

Also I do not find the expressions of polynomials to be so hard to read with regular representation expressions. But maybe it is just the old Lispers opinion.

I will try to do some reasonable profiling with non-simplifying __add__ and post the results of the timing.

mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster

I should look into it if it is possible to do quick operation to do merging and combining the same time the equal powers. But simplification also takes care of droping the 0 multiplier terms and it uses the C-speed sorting (minus the penalty of comparision operations defined in user class) which I would expect to not cause much penalty with typically less than 100 term polynomials case.

It is the same operation as you do when doing merge-sort, plus the "remove zeros" and "fuse equal exponent terms" parts which can be trivially inserted into the merge operation. My Python skills are too shameful to demonstrate it, but if something is trivial (<10 lines) in C/C++, I would presume it is even simpler in Python.

Currently, your "simplify" function has the following complexity. Assume the polynomial has N terms, the sorting takes O(NlogN) while your pruning+fusion of terms takes O(N^2) (because of the inefficient use of random-accesses in a sequential container), but of course, of implemented correctly, the pruning-fusion would have O(N) complexity. So, if A is the cost of comparing/swapping elements, and B is the cost of checking the pruning condition, then you time consumption is A * N * logN + B * N + O(1). If you use a merge-while-pruning approach, the overall time consumption will be (A + B) * N + O(1). If N is 100, you would roughly get 700 * A + 100 * B for the "simplify" approach, and about 100* (A + B) for the merge-while-pruning approach, leading to a benefit of about 600 * A, in other words, the "simplify" approach is likely to be several times slower in such a case, regardless of how fast your "C-speed" sorting is. And, this analysis also disregards the additional overhead coming from the sort method (in addition to the compare-swap cost A), and, the fact that at such small N values, most standard implementations revert back to an insertion-sort algorithm (at least, GCC does) with O(N^2) complexity but less overhead.

The point is, when you are merging two sorted arrays, you should use an algorithm for merging two sorted arrays. In fact, one of the classic coding mistakes that you see all the time is people abusing sorting algorithms by using them for everything. Sorting algorithms are much less useful than people think, because you rarely have a situation where you start with a completely scrambled array and want to sort it entirely. Usually, you want to keep track of the min/max elements (use a "heap" for that), or you only need to merge or insert elements into an already sorted list (use a "merge" for that, or keep a BST), or you only need specific partitions of the list (use a quick-select algorithm for that), or you want the first K minimum/maximum elements of a list (again, with quick-select), etc... Sorting is only for when you start with a complete and unordered list, and want an ordered list at the end, just about every other case can be handled more efficiently otherwise, and yes, it does make a difference, empirically and theoretically.

It could be much non-DRY code compared with simplify method

I guess "DRY = Don't Repeat Yourself". That's the core of the issue. Don't repeat yourself doesn't necessarily mean reuse as much as possible. The "simplify" function does a lot more than what the "add" function needs, hence the performance penalty. The DRY rule might be analogous to saying that if you have a car that you use to do your grocery shopping, you can also use it go to the mall, i.e., that you don't need to buy another car for that other purpose. However, DRY doesn't mean that if you happen to own a tank, that you should take it to the mall. You can, but it's overkill and wasteful (and it will scare people sh1tless!). DRY means that you should use the same function for "add" and "sub" because the need is essentially the same. So, to me, the "simplify" method is non-DRY code already, and a merge-while-pruning approach would fix that.

Probably I would end up to use that inside the simplify by only moving after sorting part to this new function. That would of course hit performance of all operations by one more function call.

One hint on improving your implementation: You could easily do without the "simplify" function altogether. You are already calling it in places you don't need to call it, and most of the operations can be done without it or with a merge-while-pruning or similar strategy. You can ponder on that for a while.

TrustyTony 888 pyMod Team Colleague Featured Poster

I produced version using the heapq.merge instead of mixing the sorting order. I have not tested performance compared to earlier version, but probably bigger improvement have come of removing the epsilon equality test for Term. I also used simplification only from the Polynomial initialization and moved out the sorting part from the simplify function.

TrustyTony 888 pyMod Team Colleague Featured Poster

I guess "DRY = Don't Repeat Yourself". That's the core of the issue.

Should we call non-DRY WET = Write Everything Twice ;)

I used the negation trick for substraction for Polynomial (later also Term, but I think I coded it to repeat the logic for showing doing it both ways) and not using references to coeficient and exponent but using Term addition to do slower way in the simplify, as I feel it very ugly to reimplement the Term addition in Polynomial class, even we loose benefit of knowledge that the Terms are of same order for sure and only coefficients need to be added.

Practically the code is repeated like in implementation of fractions module.

    def _add(a, b):
        """a + b"""
        return Fraction(a.numerator * b.denominator +
                        b.numerator * a.denominator,
                        a.denominator * b.denominator)

    __add__, __radd__ = _operator_fallbacks(_add, operator.add)

    def _sub(a, b):
        """a - b"""
        return Fraction(a.numerator * b.denominator -
                        b.numerator * a.denominator,
                        a.denominator * b.denominator)

    __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.