파이썬에서 다항식의 나누기

Question

나는 파이썬에서 다항식의 나눗셈을 고수하고있다. 다음은 수정 한 코드입니다. 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]. 그래서 지금은 몫과 나머지를 반환, 내가 약간의 코드를 수정 한

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

: 는 여기에 내가 오후 2Ring의 답변에 따라, 입력의 경우에 수정 된 코드입니다. ,

#! /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)