多项式除法算法

Question

我正在使用 sage 并尝试使用 Wikipedia 给出的伪代码来实现单变量多项式除法。

但我认为它卡在循环中，例如，如果我问 div(x^2-1,x-1) 它不会立即给出答案。它应该 return (0,x+1) 但它什么也没做。

代码：

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)

编辑： 我读错了伪代码，错过了我没有减少多项式的次数，所以很明显它什么都不做。我 'fixed it' 但现在它给了我一些新的错误，但我认为这是一些强制错误。

感谢任何帮助！

新密码：

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)

编辑 2： 在检查 "Polynomials in sage" 时它说如果你将两个多项式相除然后它将它强制转换为分数字段的一个元素这将给我一个r.degree() 行中的错误。有人知道解决这个问题的方法吗？

Answer 1

通过将 m 铸造到基环中来修复，m=R(m) 我想这是一些草率的补丁我想知道是否有一些更聪明的方法来制作这个算法。固定码：

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)

Answer 2

在圣人中

p / q在分数字段中给出结果
p // q 给出环中的商（去掉任何余数）
p % q 给出余数
p.quo_rem(q) 立即给出 (quotient, remainder) 对

多项式除法算法

Polynomial division algorithm

python

sage