Двоичные полиномы по модулю Python - PullRequest
Новая
       11

Двоичные полиномы по модулю Python

0 голосов
/ 07 мая 2018

У меня есть двоичные полиномы, которые я представляю как двоичное число. Например 

a = 0b10011 
b = 0b101

а - это х ^ 4 + х + 1, а б - это х ^ 2 + 1. Итак, я хочу, чтобы 

a%b = 2 # 10 as polynomial x

Я хотел бы спросить, как я могу это сделать? Я думаю, что стандартная операция% двух полиномов не будет работать.

1 Ответ

0 голосов
/ 07 мая 2018

Вот простая идея, учитывая обычную процедуру деления полиномов, вы можете создать собственный класс для представления двоичных полиномов, а затем просто переопределить оператор (%), возможно, что-то вроде этого: 

from math import fabs


def poly_div(p1, p2):
    def degree(poly):
        while poly and poly[-1] == 0:
            poly.pop()
        return len(poly)-1

    p2_degree = degree(p2)
    p1_degree = degree(p1)

    if p2_degree < 0:
        raise ZeroDivisionError

    if p1_degree >= p2_degree:
        q = [0] * p1_degree
        while p1_degree >= p2_degree:
            d = [0]*(p1_degree - p2_degree) + p2
            mult = q[p1_degree - p2_degree] = p1[-1] / float(d[-1])
            d = [coeff*mult for coeff in d]
            p1 = [fabs(p1_c - p2_c) for p1_c, p2_c in zip(p1, d)]
            p1_degree = degree(p1)
        r = p1
    else:
        q = [0]
        r = p1

    return q, r


class BinPoly:

    def __init__(self, poly):
        self.poly = [int(bit) for bit in list(poly)]

    def __mod__(self, other):
        return poly_div(self.poly, other.poly)


if __name__ == '__main__':
    a = BinPoly('10011')
    b = BinPoly('101')
    print(a%b)

Как вы можете видеть, вы строите многочлены из строки, настраивая класс на использование двоичных чисел, не должно быть слишком сложным, оставьте читателю в качестве упражнения;)

...