tp_17_raw.py

def coeff(L, i):
    #if i >= len(L): return 0
    return L[i]

def izip(L1, L2):
    n = max(len(L1), len(L2))
    return [(coeff(L1,i), coeff(L2,i)) for i in range(n)]
 
def degree(poly):
    while poly and poly[-1] == 0:
        poly.pop()   # normalize
    return len(poly)-1
 
def poly_div(N, D):
    dD = degree(D)
    dN = degree(N)
    if dD < 0: raise ZeroDivisionError
    if dN >= dD:
        q = [0] * dN
        while dN >= dD:
            d = [0]*(dN - dD) + D
            mult = q[dN - dD] = N[-1] / float(d[-1])
            d = [coeff*mult for coeff in d]
            N = [coeffN - coeffd for coeffN, coeffd in izip(N, d)]
            dN = degree(N)
        r = N
    else:
        q = [0]
        r = N
    return q, r

def poly_div_v2(A, B): # A = N et B = D
    assert len(B) > 0, 'divison par zéro?'
    Q = [0]*len(A)
    R = A*1
    while len(R) >= len(B):
        print(R, B)
        T = [0]*(len(R) - len(B)) + B
        mult = Q[len(R) - len(B)] = R[-1] / T[-1]
        T = [coeff*mult for coeff in T]
        R = [coeffN - coeffd for coeffN, coeffd in izip(R, T)]
        while R and R[-1] == 0:
            R.pop()
        print('lel', R)
    return Q, R

def poly_div_v3(A, B): # A = N et B = D
    assert len(B) > 0, 'divison par zéro?'
    Q = [0]*len(A)
    R = A*1
    while len(R) >= len(B):
        print(R, B)
        T = B+[0]*(len(R) - len(B))
        mult = Q[len(R) - len(B)] = R[0] / T[0]
        T = [coeff*mult for coeff in T]
        R = [coeffN - coeffd for coeffN, coeffd in izip(R, T)]
        while R and R[0] == 0:
            R = R[1:]
        print('lel', R)
    return Q, R

def poly_div_re(A, B): # A = N et B = D
    assert len(B) > 0, 'divison par zéro?'
    Q = np.poly1d([0]*len(A))
    R = A*1
    while len(R) >= len(B):
        print(R, B)
        T = np.poly1d([0]*(len(R) - len(B)) + list(B.coeffs))
        print(R.coeffs, len(R), T.coeffs, len(T))
        mult = Q[len(R) - len(B)] = R[len(R)] / T[len(T)]
        T = T*mult
        l = [coeffN - coeffd for coeffN, coeffd in izip(R, T)]
        R = np.poly1d(l)
        print('lel', R)
    return Q, R


def poly_div_re_pete(A, B): # A = N et B = D
    assert len(B) > 0, 'divison par zéro?'
    ACo = list(reversed(A.coeffs))
    BCo = list(reversed(B.coeffs))
    Q = [0]*len(ACo)
    R = ACo*1
    while len(R) >= len(BCo):
        print(R, BCo)
        T = [0]*(len(R) - len(BCo)) + BCo
        mult = Q[len(R) - len(BCo)] = R[-1] / T[-1]
        T = [coeff*mult for coeff in T]
        R = [coeffN - coeffd for coeffN, coeffd in izip(R, T)]
        while R and R[-1] == 0:
            R.pop()
        print('lel', R)
    return np.poly1d(Q), np.poly1d(R)

import numpy as np

print("POLYNOMIAL LONG DIVISION")
N = [-42, 0, -12, 1]
D = [-3, 1, 0, 0]

def rL(l):
    return list(reversed(l))

N1 = np.poly1d(rL(N))
D1 = np.poly1d(rL(D))

N2 = np.poly1d(N)
D2 = np.poly1d(D)

print(N, D)
q, r = poly_div(N, D)
print('quotient', q)
print('remainder', r)

print('==')

q, r = poly_div_v2(N, D)
print('quotient', q)
print('remainder', r)

print('==')

q, r = poly_div_v3(rL(N), rL(D))
print('quotient', q)
print('remainder', r)

print('==')

q, r = poly_div_v2(list(N2.coeffs), list(D2.coeffs))
print('quotient', q)
print('remainder', r)

print('==')

q1, r1 = N1/D1
print(q1.coeffs)
print(r1.coeffs)

# MEMO:
# print(np.poly1d([3, 0, 4, 5, 6])) gives:
#   4     2
#3 x  + 4 x + 5 x + 6

# ALSO: np.poly1d([3, 0, 4, 5, 6]).coeffs gives:
# array([3, 0, 4, 5, 6])

# BUT:
# np.poly1d([3, 0, 4, 5, 6]).coeffs[0] != np.poly1d([3, 0, 4, 5, 6])[0]
# -1 don't exists