Hello to everyone! This is my first post here, I hope you can help me. I'm making a class work in python and I'm a little lost:

I have to use classes to represent monomials and polynomials, and the classes should contain methods to add, substract, multiply and divide them.

So far, I've been able to create the whole monomials class, and almost all the polynomial class, but I can't find a way to code polynomial division.

Surfing the web I've seen some methods based on binary conversion and things like that, but that doesn't seem to work for me because of how the program is made.

here's my code. The variable names are in Spanish, sorry for that :P

As you can see, each monomial has two attributes (coefficient and exponent), and the polynomial class takes as an argument a list of monomial objects.

# -*- coding: cp1252 -*-
import math

class Monomio:
    def __init__(self, coeficiente, exponente):
                if isinstance(coeficiente, int):
            self.coeficiente = float(coeficiente)
        else:
            self.coeficiente = coeficiente
        if isinstance(exponente, int):
            self.exponente = float(exponente)
        else:
            self.exponente = exponente


    def sumar (monomio1, monomio2):
        # adding
        if monomio1.exponente == monomio2.exponente:
            suma = Monomio(monomio1.coeficiente + monomio2.coeficiente, monomio1.exponente )
            return suma

        else:
            return "error"


    def restar (monomio1, monomio2):
        # substracting
        if monomio1.exponente == monomio2.exponente:
            resta = Monomio(monomio1.coeficiente - monomio2.coeficiente, monomio1.exponente)
            return resta

        else:
            return "error"

    def multiplicar (monomio1, monomio2):
        # product
        producto = Monomio(monomio1.coeficiente * monomio2.coeficiente, monomio1.exponente + monomio2.exponente)
        return producto


    def dividir ( monomio1, monomio2):
        # division
        cociente = Monomio(monomio1.coeficiente / monomio2.coeficiente, monomio1.exponente - monomio2.exponente)
        return cociente

    def mostrar (monomio):
        # showing the monomials on screen
        if monomio.coeficiente == math.floor(monomio.coeficiente) and monomio.exponente == math.floor(monomio.exponente):
            print str(int(monomio.coeficiente)) + "x^" + str(int(monomio.exponente))
        elif monomio.coeficiente == math.floor(monomio.coeficiente) and monomio.exponente != math.floor(monomio.exponente):
            print str(int(monomio.coeficiente)) + "x^" + str(monomio.exponente)           
        elif monomio.coeficiente != math.floor(monomio.coeficiente) and monomio.exponente == math.floor(monomio.exponente):
            print str(monomio.coeficiente) + "x^" + str(int(monomio.exponente))
        else:
            print str(monomio.coeficiente) + "x^" + str(monomio.exponente)



class Polinomio:

        def __init__(self, polinomio):
            self.polinomio = polinomio
            self.size = len(polinomio)

        def ordenar(polinomio):
            # sorts the list
            for i in range(1, polinomio.size):
                for j in range(0, polinomio.size-i):
                    if polinomio.polinomio[j].exponente > polinomio.polinomio[j+1].exponente:
                        elemento = polinomio.polinomio[j]
                        polinomio.polinomio[j] = polinomio.polinomio[j+1]
                        polinomio.polinomio[j+1] = elemento
            polinomio.polinomio.reverse()

        def mostrar(polinomio):
            #shows the monomials list on screen
            for i in range(0, polinomio.size):
                polinomio.polinomio[i].mostrar()



        def simplificar(polinomio):
            # simplifies the polynomial by adding all the elements with the same exponent.

            for i in range(1, polinomio.size - 2):
                if polinomio.polinomio[i].exponente == polinomio.polinomio[i+1].exponente:
                    polinomio.polinomio[i] = Monomio.sumar(polinomio.polinomio[i], polinomio.polinomio[i+1])
                    del polinomio.polinomio[i+1]
                    polinomio.size = len(polinomio.polinomio)




        def sumar(poli1,poli2):
        # adding

            suma = []
            for i in range(0,poli1.size):
                suma.append(poli1.polinomio[i])
            for j in range(0,poli2.size):
                suma.append(poli2.polinomio[j])
            polisuma = Polinomio(suma)
            polisuma.ordenar()
            polisuma.simplificar()
            return polisuma

        def restar(poli1,poli2):
        # substracting
            poliresto = Polinomio(poli2.polinomio)
            for a in range (0,poliresto.size):
                poliresto.polinomio[a].coeficiente = 0 - poliresto.polinomio[a].coeficiente
            resta = []
            for i in range(0,poli1.size):
                resta.append(poli1.polinomio[i])
            for j in range(0,poliresto.size):
                resta.append(poliresto.polinomio[j])
            poliresta = Polinomio(resta)
            poliresta.ordenar()
            poliresta.simplificar()
            return poliresta

        def multipilicar(poli1,poli2):
        #product
            multi = []
            for i in range(0,poli1.size):
                for j in range(0,poli2.size):
                    multi.append(Monomio.multiplicar(poli1.polinomio[i],poli2.polinomio[j]))
            polimulti = Polinomio(multi)
            polimulti.ordenar()
            polimulti.simplificar()
            return polimulti

My problem, as I said, is that I have no idea about how to even start coding the polynomial division. Any ideas?

Why don't you code the long division like you would do on paper? You must consider handling of remainder also.

Usually you should stick to using self as instance referencing parameter. You could use magic methods add etc to extend normal operations to polynomial class.

Edited 4 Years Ago by pyTony

Well, the thing is precisely that I know how to divide polynomials, but just not formally. In other words, I honestly don't know how to translate the method into an algorithm, and without that, programming the method is impossible.

Also, I don't know how should the output be like. I mean, when adding/subtracting/multiplying, the method returns a polynomial object, but in this case there's a remainder, as you said, so returning a list doesn't seem right...

It could return pair of polynomials: the result and the remainder like divmod.

Division of polynomials is simple in that you only need to consider the highest term from both dividend and divisors, order of result is difference of powers of x and how many times it goes, is just division of coefficients. Each time you must add one term from the dividend more and substract the last result times the divisor from that polynomial. You finish when highest exponent of divisor is of higher order than next polynomial to divide (difference is negative).

You should raise error not return string 'error'.

Edited 4 Years Ago by pyTony

Hi again. Thanks for your help, I think I understood you, I've managed to code something but I'm receiving a weird error I don't understand.

Here's the new code:

def dividir(poli1,poli2):
            dividendo = poli1
            divisor = poli2
            cociente = Polinomio([])
            listarestando = []

            while dividendo.polinomio[0].exponente >= divisor.polinomio[0].exponente:
                cociente.polinomio.append(Monomio.dividir(dividendo.polinomio[0],divisor.polinomio[0]))
                resultado = Monomio(cociente.polinomio[cociente.size - 1].coeficiente, cociente.polinomio[cociente.size - 1].exponente)
                for i in range(0, dividendo.size):
                    listarestando.append(Monomio.multiplicar(resultado, dividendo.polinomio[i]))
                restando = Polinomio([listarestando])
                restando.ordenar()
                restando.simplificar()
                dividendo = Polinomio.restar(dividendo, restando)
            cociente.ordenar()
            cociente.simplificar()
            resto.ordenar()
            resto.simplificar()
            return cociente, dividendo

however, when I run said code it gives me this error:

Traceback (most recent call last):
  File "<pyshell#19>", line 1, in <module>
    Polinomio.dividir(poldiv1,poldiv2)
  File "C:/Users/Carlos/Desktop/clases/monomio.py", line 151, in dividir
    dividendo = Polinomio.restar(dividendo, restando)
  File "C:/Users/Carlos/Desktop/clases/monomio.py", line 116, in restar
    poli2.polinomio[a].coeficiente = 0 - poli2.polinomio[a].coeficiente
AttributeError: 'list' object has no attribute 'coeficiente'

The weird thing is, the error appears to be in restar (the method which substracts polynomials) but when I use that method manually, it works.

(The restar method is already posted in my former post, if you need to see it)

What did I do wrong?

I will post my code using magic methods starting from your code as code snippet thread, when you get your division working I will add it to my snippet (I did not implement it yet myself). You have somehow put list instead of Monomio type element in the Polinomio.

Thanks. The error appeared because of

> restando = Polinomio([listarestando])

it should be

   restando = Polinomio(listarestando)

as listarestando was already a list.

It doesn't work yet, anyway. I'll keep fixing it and I'll post it when (if) I manage to get it to work.

I did my own division, be sure to test this one:

(X^4 - 1) / (x - 1) = (X^3 + X^2 + x + 1) 

Another test usefull is

 (X^3 - 2X^2 + 3x + 1) / (-4X^2 + 7x + 12) = (-0.25x + 0.0625)  + (5.5625x + 0.25) / (-4X^2 + 7x + 12)

Which yields coefficients that are not integers even the original coefficients are. Found a bug in my own code when tried this.

Edited 4 Years Ago by pyTony

This article has been dead for over six months. Start a new discussion instead.