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)

(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
462 Views
``````# 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

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

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, (Polynomial, list)):
args = args
elif not isinstance(args, Term):
args=Polynomial(Term(args))

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.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))

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

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 / other
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)

def __floordiv__(self, other):
return divmod(self, other)

# 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),
(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)``````

IT Pro doing Eng-Fin-Eng translations

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

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, Polynomial):
args=args
elif not isinstance(args, Term):
args=Polynomial(Term(args))

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))

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)
``````

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

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.

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

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.

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.

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.

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.

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.

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)