This page is located in archive.

Homework 07 - Division Algorithm


Implement the algorithm of polynomial division for more than one divisor (the examples and pseudo-algorithm of polynomial division can be found in lab slides from week 8 and lecture slides from week 9 and 10. )

Create a function poly_div(f, divs, mo) for dividing the polynomial f by the list of polynomials divs using the specified monomial ordering mo.

Input/Output specifications for poly_div:

  1. f : Poly object
  2. divs : list of Poly objects
  3. mo : String. It can take the following values (according to SymPy documentation):
    1. “lex” - lexicographic order
    2. “grlex” - graded lexicographic order
    3. “grevlex” - graded reversed lexicographic order
  4. Return value : dictionary with 2 keys “q” and “r”, whose values are the list of quotient polynomials (list of Poly objects) and the remainder of the division (Poly object), respectively. That is,

$$ f = \sum_{i}q[i]\cdot divs[i] + r, \quad \mathrm{LT}(r) \text{ is not divisible by any of } \mathrm{LT}(divs[i]) \;\text{ or }\; r = 0. $$

For the explanation of how to work with Poly objects see Sympy documentation. You can use only Sympy library. It is not allowed to use the method reduced from Sympy library.


Upload a zip archive hw07.zip (via the course ware) containing the following files:

  1. hw07.py - python script containing the implemented function poly_div
courses/pro/labs/hw07.txt · Last modified: 2021/11/15 12:39 by korotvik