Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

1変数多項式の四則演算をpythonで実装する

1変数多項式の四則演算をpythonで実装してみました。
係数は整数の範囲としています。
加算、減算、乗算、剰余を実装します。
剰余では割られる側の最大次数の係数は1のみに限定します。
以下、実装です。

#!/usr/bin/env python3

from fractions import gcd
import operator

class Pol:
    def __init__(self, units):
        self.units = units
        self.normalize()

    def normalize(self):
        l_units = []
        for u in self.units:
            found = False
            for l_u in l_units:
                if u.power == l_u.power:
                    l_u.coef += u.coef
                    found = True
                    break
            if not found:
                l_units.append(u)
        self.units = [x for x in l_units if x.coef != 0]
        self.units.sort(key=operator.attrgetter('power'), reverse=True)

    def highestUnit(self):
        unit = Unit(0, 0) 
        for u in self.units:
            if unit.power < u.power:
                unit = u
        return unit

    def __add__(self, other):
        l_units = self.units
        l_units.extend(other.units)  
        return Pol(l_units)
    
    def __sub__(self, other):
        l_units = self.units
        for i in other.units:
            l_units.append(-i)
        return Pol(l_units)

    def __mul__(self, other):
        l_units = []
        for i in self.units:
            for j in other.units:
                l_units.append(i * j)
        return Pol(l_units)

    def __mod__(self, other):
        o_h = other.highestUnit()
        assert(o_h.coef == 1)
        tmp = self
        while True:
            tmp_h = tmp.highestUnit()
            if tmp_h.power < o_h.power:
                break
            p = Pol([Unit(tmp_h.coef, tmp_h.power - o_h.power)])
            tmp = tmp - p * other  
        return tmp

    def iszero(self):
        return len(self.units) == 0

    def __str__(self):
        if self.iszero():
            return "0"
        s = ""
        for u in self.units:
            s += " + " + str(u)  
        return s.strip(" + ")

class Unit:
    def __init__(self, coef, power): 
        self.coef = coef
        self.power = power

    def __str__(self):
        if self.power == 0:
            return str(self.coef)     
        s = ""
        if self.coef != 1:
            s += str(self.coef) 
        if self.power == 1:
            s += "x"
        else:
            s += "x^"+str(self.power)
        return s

    def __add__(self, other):
        assert(self.power == other.power)
        return Unit(self.coef + other.coef, self.power)

    def __sub__(self, other):
        assert(self.power == other.power)
        return Unit(self.coef - other.coef, self.power)

    def __neg__(self):
        return Unit(- self.coef, self.power) 

    def __mul__(self, other):
        return Unit(self.coef * other.coef, self.power + other.power)

    def __floordiv__(self, other):
        return Unit(self.coef // other.coef, self.power - other.power)

    def iszero(self):
        return self.coef == 0


p = Pol([Unit(-1, 0), Unit(1, 5)])
print("P = " + str(p))

q = Pol([Unit(1, 3), Unit(2, 1), Unit(1, 0)])
print("Q = " + str(q))

r = p * q
print("P * Q = " + str(r))

s = p % q
print("P mod Q = " + str(s))

u = Pol([Unit(1, 8), Unit(2, 6), Unit(1, 5), Unit(-1, 3), Unit(-2, 1), Unit(-1, 0)])
print("U = " + str(u))

v = u % q
print("U mod Q = " + str(v))

実行結果がこちらです。

P = x^5 + -1
Q = x^3 + 2x + 1
P * Q = x^8 + 2x^6 + x^5 + -1x^3 + -2x + -1
P mod Q = -1x^2 + 4x + 1
U = x^8 + 2x^6 + x^5 + -1x^3 + -2x + -1
U mod Q = 0

これで剰余が計算できるようになりましたので、多項式のGCDが実装できそうですが、
私が知りたいのはGCDが1かどうかつまり、2つの多項式が違いに素かどうかです。
一つの多項式がもう一方の多項式で割り切れればGCDが1となります。

    def is_gcd_one(self, other):
        return (self % other).iszero()
P = x^5 + -1
Q = x^3 + 2x + 1
P * Q = x^8 + 2x^6 + x^5 + -1x^3 + -2x + -1
P mod Q = -1x^2 + 4x + 1
U = x^8 + 2x^6 + x^5 + -1x^3 + -2x + -1
U mod Q = 0
U.is_gcd_one(Q) = True
W = x^9
W.is_gcd_one(Q) = False

プライバシーポリシー

お問い合わせ

スポンサーリンク