Polynomial division algorithm

Question

I'm using sage and was trying to implement univariate polynomial division with the pseudocode given by Wikipedia.

But I think it is stuck looping, for example if I ask div(x^2-1,x-1) it doesn't give the immediate answer. It should return (0,x+1) but it does nothing.

The code:

def div(p,q): if q==0: return("NaN") elif q!=0: l=0 r=p while r!=0 and q.degree()<=r.degree(): t=(r.leading_coefficient())/(q.leading_coefficient()) l=l+t r=r-(t*q) return(l,r)

Edit: I was reading the pseudocode wrong and missed that I was not reducing the degree of my polynomial so clearly it just was doing nothing. I 'fixed it' but now it is giving me some new error but I think it's some coercion error.

Any help is appreciated!

The new code:

def div(p,q): if q==0: return("NaN") elif q!=0: l=0 r=p while r!=0 and q.degree()<=r.degree(): t=r.leading_coefficient()/q.leading_coefficient() m=x^r.degree()/x^q.degree() l=l+t*m r=r-(t*m*q) print(l,r) #To see when the code fails return(l,r)

Edit 2: Upon inspection of "Polynomials in sage" it says that if you divide two polynomials then it coerces it to an element of the fraction field which would give me an error in the r.degree() line. Anyone knows a workaround to this?

Welcome to stackoverflow! Please provide your code in the form of a minimum reproducible example such that we can try it, play with it and be able to give you answer more easily — Jan Stránský, CommentedSep 3, 2020 at 21:15
Hey @JanStránský, upon revision of my code, in my opinion is within the guidelines for minimum reproducible example is there anything you see that is not correct? — Sebastian Cor, CommentedSep 3, 2020 at 21:20
If I copy/paste your code in a .py file and run the .py file, it does nothing (it is just function definition). Please put there an example how you call it, which should reproduce your problem — Jan Stránský, CommentedSep 3, 2020 at 21:32
I think you need to replace 'l' by 'q: l=0 to q=0 and l=l+t to q=q+t. Otherwise the 'q' condition on the while doesn't change. — Peter Ark, CommentedSep 3, 2020 at 21:37

Samuel Lelièvre · Accepted Answer · 2020-09-04 12:49:29Z

In Sage

p / q gives a result in the fraction field
p // q gives the quotient in the ring (dropping any remainder)
p % q gives the remainder
p.quo_rem(q) gives the pair (quotient, remainder) at once

Sebastian Cor · Accepted Answer · 2020-09-04 01:40:39Z

Fixed by casting m into the base ring, m=R(m) I guess this is some sloppy patch I would like to know if there is some smarter way to make this algorithm. The fixed code:

x=var('x') R.<x>=PolynomialRing(QQ) def div(p,q): if q==0: return("NaN") elif q!=0: l=0 r=p while r!=0 and q.degree()<=r.degree(): t=r.leading_coefficient()/q.leading_coefficient() m=x^r.degree()/x^q.degree() m=R(m) l=l+t*m r=r-(t*m*q) print(l,r) return(l,r)

The line x = var('x') is not needed. The next line R.<x> = ... redefines x anyway. — Samuel Lelièvre, CommentedSep 4, 2020 at 12:50

Collectives™ on Stack Overflow

Polynomial division algorithm

2 Answers 2

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Related