DALGLI0/zad2.py

import math

class Polynomial:
	n = 0

	def __init__(self, n):
		self.n = n

	def normalize(self, w):
		while 0 in w: 
			w.remove(0)
		return w

	def multiply(self, f, g):
		result = []
		tmp=0
		for i in range(0, len(f)):
			for j in range(0, len(g)):
				tmp=f[i]*g[j]
				if i+j < len(result):
					tmp = tmp + result[i+j]
					result[i+j] = tmp % self.n
				else:
					while i+j >= len(result):
						result.append(0)
					result[i+j] = tmp % self.n
		return self.normalize(result)

	def multiplyConst(self, f, a):
		result = []
		for i in f:
			result.append((i*a)%self.n)
		return result

	def substract(self, f, g):
		result = []
		for i in range(0, len(f)):
			if i < len(g):
				result.append(math.fmod(f[i]-g[i], self.n))
			else:
				result.append(f[i])
		return result

	def zero(self, a, b):
		i = 0
		while True:
			if (a + (-(b*i))) == 0:
				return i
			i = i + 1 
			

	def divide(self, f, g):
		quotient = []
		reminder = f
		tmpList = []
		a = (len(f) - 1)
		b = (len(g) - 1)

		for i in range(0, a-b+1):
			quotient.append(0)

		q = len(quotient)-1
		tmp = 0

		while a>=b:
			tmp = self.zero(reminder[a], g[b])
			quotient[q] = tmp
			q = q - 1
			tmpList = self.multiplyConst(g, tmp)
			while len(tmpList) <= a:
				tmpList.append(0)
			reminder = self.substract(reminder, tmpList)
			a = a - 1
		return self.normalize(reminder)

	def nwd(self, f, g):
		if len(g)==0:
			return f
		return self.nwd(g, self.divide(f, g))




polynomial = Polynomial(2)
f = [1, 1, 1, 0, 1]
g = [0, 1, 1]
print(polynomial.multiply(f, g))
print(polynomial.divide(f, g))
print(polynomial.nwd(f, g))

polynomial1 = Polynomial(6)
ff = [2, 1, 0, 2, 1, 3]
gg = [1, 0, 0, 5]
print(polynomial1.multiply(ff, gg))
print(polynomial1.divide(ff, gg))
print(polynomial1.nwd(ff, gg))