Report Sessions 3 and 4

Report Sessions 3 and 4#

Your goal is to « recreate » a very basic version of polynomials (over \(\mathbb{Q}\)) in Sage

We provide a basic structure for representing dense polynomials in poly.py

You need to implement the different methods following the algorithms seen in class.

from poly import PolyDense

Basic methods#

Start by implementing the __init__ methods which takes an optionnal list of coefficients

P = PolyDense()

P = PolyDense([1])

# This should not work because pi is not rational
P = PolyDense([pi])

Implement all these basic methods of PolyDense. See the expected results in the examples in the documentation of each method

coeff

PolyDense().coeff(0)

P = PolyDense([0, 1, 0, 2/3, 0])
[P.coeff(i) for i in range(10)]

degre

PolyDense().degre()

PolyDense([1]).degre()

PolyDense([0, 1]).degre()

PolyDense([0, 1, 0]).degre()

PolyDense([0, 1, 0, 2/3, 0]).degre() # should be 3, not 4 !

Question: how to deal with 0 values in the coef list? Where should the test be? What should be stored?

your answer

bool

bool(PolyDense())

bool(PolyDense([0]))

bool(PolyDense([1]))

bool(PolyDense([0, 1]))

monomials

PolyDense().monomials()

PolyDense([1]).monomials()

PolyDense([0, 1]).monomials()

PolyDense([0, 1, 0, 2/3]).monomials()

In PolyCommon, we have written a __repr__ method to print polynomials. Now it should work!

PolyDense()

PolyDense([1])

PolyDense([0, 1, 0, 2/3])

Two polynomials are equal if they have the same coefficients. Implement the __eq__ method

PolyDense() == PolyDense()

PolyDense([0, 1]) == PolyDense([0, 1])

PolyDense([0, 1]) == PolyDense()

Creation of polynomial, basic operation#

We have implemented an X method to get the polynomial \(X\) of degree 1

X = PolyDense.X()
X

To be able to easily create a polynomial using a natural mathematical notation, we need to implement basic operations

Implement the set_coeff and __add__ methods

P = PolyDense() 
P.set_coeff(2, 3/2)
P

P = PolyDense([0, 1, 0, 2/3])
P.set_coeff(2, -5/3)
P

P.set_coeff(8, -1/8)
P

If we send a negative degree, this should raise an exception

P.set_coeff(-1,2)

PolyDense([0, 1, 3]) + PolyDense([0, 1, 0, 3/2])

PolyDense([0, 1, 3]) + PolyDense([0, -1, -3])

You should be able to add an element of PolyDense with a element of the base ring

PolyDense([0, 1]) + 2

Be carreful to normalize the result of the addition, this should be 0

PolyDense([0, 1]) + PolyDense([0, -1])

Implement the method naive_mul and then the method __mul__ which delegates to naive_mul

PolyDense([0, 1, 2]).naive_mul(PolyDense([2]))

PolyDense().naive_mul(PolyDense([0, 1, 2]))

PolyDense([1]).naive_mul(PolyDense([0, 1, 2]))

PolyDense([1, -2]).naive_mul(PolyDense([0, 1, 2]))

PolyDense()*PolyDense([0, 1, 2])

PolyDense([1])*PolyDense([0, 1, 2])

PolyDense([1, -2])*PolyDense([0, 1, 2])

You should be able to multiply with an element of the base ring

PolyDense([0, 1, 2])*2

Implement the __pow__ method in PolyCommon, make it so that the complexity is logarithmic.

PolyDense([0,1])^5

PolyDense([1,1])^3

PolyDense([0,1])^100

Now we can create polynomials in a natural way (almost)

X = PolyDense.X()

X^2 + 3

X^5 * (5/2) + X^2 + 3

(X + 1) * (X - 1)

Horner’s algorithm#

Implement the __call__ method (evaluation) using Horner’s algorithm

PolyDense([1, 1])(3/2)

PolyDense([1, -2, 3])(2)

X = PolyDense.X()
P = X^5 + X^4*4 + X^3 - X^2 +5

P(1)

P

P(2)

Karatsuba algorithm#

Implement the method karatsuba_mul to multiply two polynomials of degre > 1 using the Karatsuba algorithm.

Then change the __mul__ method so that the naive algo is used for polynomials of degres <= 1 and Karatsuba for higher degree polynomials.

PolyDense([1, -2]).karatsuba_mul(PolyDense([0, 1, 2]))

X = PolyDense.X()
P = X^3 * 3 - X^2 + 1
Q = X^2 * 2 + X + 5
P*Q # 6X^5 + X^4 + 14X^3 - 3X^2 + X + 5

Who is faster?#

The following function return a random polynomial of a given degree.

Below, you see an example testing the time needed for a naive multiplication.

def random_poly(degree):
    r"""
    Return a polynomial of given degree whose coefficients are random integers between 0 and 10
    """
    return PolyDense([randint(0,10) for i in range(degree)] + [randint(1,10)])

P = random_poly(10)
P

Q = random_poly(10)
Q

time P.naive_mul(Q)

Compute the time needed using Karatsuba, is it faster?

Compare again with polynomials of degree 100, 1000 and 3000

# Write your code here

# Write your code here

# Write your code here

# Write your code here

# Write your code here

# Write your code here

# Write your code here

Optimize the __mul__ method so that it uses the most efficient algorithm depending on the degree of the polynomial. See what time it takes to compute products and how far you can go.

Going further#

You can improve your implementation with:

  • Euclidian division

  • Polynomial interpolation

  • sparse polynomials

  • …

If you have done any of those, put examples below:

Tests and code check#

Check that the Sage tests are passing here

!sage -t poly.py

# printing code correction
PolyDense.__call__??

PolyDense.naive_mul??

PolyDense.karatsuba_mul??

PolyDense.__mul__??