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:
- Based on Mike_2000_17's suggestion removed overcautious simplify calls and added x variable as Term(1,1) for expression form Polynomials.
- Added
__radd__ = __add__
to enable number in left side of addition with Term (1 + x etc.) - 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.
- 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)
- Removed even the simplify from the end of long division
- Added
__rsub__
and__radd__
(to Polynomial also) - Removed unnecessary
__eq__
from polynomial (list comparisions inherited suffice if sides are reverse sorted) - Unused import of chain removed
- Incorrect <= changed to < in __lt__ of Term (worked because of other != condition, but confusing)