Python中的多项式的划分

Question

我被python中的多项式除法卡住了。这是我修改的代码。 while循环无法工作。此代码仅将原始L输出为r。如果我删除while循环，只输出第一次分割的余数。我尝试了很多方法来使它工作，但都失败了。任何建议将不胜感激。谢谢！

def GetDegree(poly): 
    while poly and poly[-1] == 0: 
     poly.pop() # normalize 
    return len(poly)-1 

def division(p1,p2): 
    d1 = GetDegree(p1) 
    d2 = GetDegree(p2) 
    if d2 < 0 or d1<0: 
     raise ZeroDivisionError 
    if d1 > d2: 
     S,L = p2,p1#obtain S with lower degree, L with higher degree 
    else: 
     S,L = p1,p2 
    d1 = GetDegree(L) 
    d2 = GetDegree(S) 
    while d1>0: 
      q = [0]*d1 
     d = [0]*(d1 - d2) + S#shift short towards right by d1-d2 
     mult = q[d1 - d2] = L[-1]/float(d[-1])#get the result by dividing the first term of the dividend by the highest term of the divisor 
     d = [coef*mult for coef in d]#multiply the above result by short 
     L = [fabs(coefL - coefd) for coefL, coefd in zip(L, d)]#return a new long by subtracting long with d 
     d1 = GetDegree(L)#return new d1 
    r = L#return new long and keeping looping for there is no variable left and return as remainder 
    return r 

我想输入任何随机多项式进行计算。但是，当我修改它时，结果仍然不正确。这是我跑的测试：num：[2,1,1,1] den：[1,1,2]。打印结果是：报价：[0.25,0.5]，rem：[1.75,0.25]。 下面是我修改了输入的情况下，基于从PM 2Ring答案代码：

def normalize(poly): 
     while poly and poly[-1] == 0: 
      poly.pop() 
     if poly == []: 
      poly.append(0) 


    def poly_divmod(num, den): 
     #Create normalized copies of the args 
     num = num[:] 
     normalize(num) 
     den = den[:] 
     normalize(den) 

     if len(num) >= len(den): 
      #Shift den towards right so it's the same degree as num 
      shiftlen = len(num) - len(den) 
      den = [0] * shiftlen + den 
     else: 
      return [0], num 

     quot = [] 
     divisor = float(den[-1]) 
     for i in range(shiftlen + 1): 
      #Get the next coefficient of the quotient. 
      mult = num[-1]/divisor 
      quot = [mult] + quot 

      #Subtract mult * den from num, but don't bother if mult == 0 
      #Note that when i==0, mult!=0; so quot is automatically normalized. 
      if mult != 0: 
       d = [mult * u for u in den] 
       num = [u - v for u, v in zip(num, d)] 

      num.pop() 
      den.pop(0) 

     normalize(num) 
     return quot, num 


    def test(num, den): 
     print ("%s/%s ->" % (num, den)) 
     q, r = poly_divmod(num, den) 
     print ("quot: %s, rem: %s\n" % (q, r)) 
     return q, r 


    def main(): 
     degree = int(input('Enter the degree of your polynomial 1:')) 
     num = [] 
     for i in range (0,degree+1): 
      coefficient = int(input('Enter the coefficient for x^ %i ? ' %i)) 
      num.append(coefficient) 
     degree = int(input('Enter the degree of your polynomial 2:')) 
     den = [] 
     for i in range (0,degree+1): 
      coefficient = int(input('Enter the coefficient for x^ %i ? ' %i)) 
      den.append(coefficient) 
     test(num, den) 



    if __name__ == '__main__': 
     main() 

Answer 1

我稍加修改你的代码，所以现在它返回商和余数。

FWIW，这将是相当容易的创建一个多项式类，然后你可以做使用标准运算符和函数多项式算法...

#! /usr/bin/env python 

''' Polynomial long division 

From http://stackoverflow.com/questions/26173058/division-of-polynomials-in-python 

A polynomial is represented by a list of its coefficients, eg 
5*x**3 + 4*x**2 + 1 -> [1, 0, 4, 5] 

Modified by PM 2Ring 2014.10.03 
''' 

def normalize(poly): 
    while poly and poly[-1] == 0: 
     poly.pop() 
    if poly == []: 
     poly.append(0) 


def poly_divmod(num, den): 
    #Create normalized copies of the args 
    num = num[:] 
    normalize(num) 
    den = den[:] 
    normalize(den) 

    if len(num) >= len(den): 
     #Shift den towards right so it's the same degree as num 
     shiftlen = len(num) - len(den) 
     den = [0] * shiftlen + den 
    else: 
     return [0], num 

    quot = [] 
    divisor = float(den[-1]) 
    for i in xrange(shiftlen + 1): 
     #Get the next coefficient of the quotient. 
     mult = num[-1]/divisor 
     quot = [mult] + quot 

     #Subtract mult * den from num, but don't bother if mult == 0 
     #Note that when i==0, mult!=0; so quot is automatically normalized. 
     if mult != 0: 
      d = [mult * u for u in den] 
      num = [u - v for u, v in zip(num, d)] 

     num.pop() 
     den.pop(0) 

    normalize(num) 
    return quot, num 


def test(num, den): 
    print "%s/%s ->" % (num, den) 
    q, r = poly_divmod(num, den) 
    print "quot: %s, rem: %s\n" % (q, r) 
    return q, r 


def main(): 
    num = [1, 5, 10, 10, 5, 1] 
    den = [1, 2, 1] 
    test(num, den) 

    num = [5, 16, 10, 22, 7, 11, 1, 3] 
    den = [1, 2, 1, 3] 

    quot = [5, 1, 3, 0, 1] 
    rem = [0, 5] 

    q, r = test(num, den) 
    assert quot == q 
    assert rem == r 


if __name__ == '__main__': 
    main() 

Answer 2

from sympy import Symbol 
from sympy import div 

x = Symbol('x') 

def Poly(p,mod): 
    q,r = div(p,mod,x) #quotient and remainder polynomial division by modulus mod 
    return r.as_poly(x,domain='GF(2)') #Z_2 

m = x**8 + x**4 + x**3 + x + 1 
p = x**6 + x**5 + x + 1 
print Poly(p*p, m)