I've been looking for a way to work with polynomials using python, did someone already wrote a code to do that?.
Here's what i have until now using dictionaries as polynomials -for example: x^4-6x^2+1 would be {4:1, 2:-6, 0:1}-, someone have any suggestion to make?
def degree(f):
t = sorted(f.keys())
if len(t)!=0:
r = t[len(t)-1]
else:
r=0
return r
def get_sum(r,s,g):
result = {}
while (g>=0):
try:
x = r[g]
except:
x = 0
try:
y = s[g]
except:
y = 0
if( (x+y)!= 0):
result[g] = x+y
g-=1
return result
def add(p,q):
if( degree(p) > degree(q) ):
suma = get_sum(p,q, degree(p))
else:
suma = get_sum(p,q, degree(q))
return suma
def product(p,q):
product_r = {}
if ( degree(p) >= degree(q) ):
t = degree(p)
else:
t = degree(q)
m = t
n = t
while ( m>=0 ):
while( n>= 0 ):
try:
r = p[m]*q[n]
except:
r = 0
try:
s = product_r[m+n]
except:
s = 0
if( (r+s)!= 0 ):
product_r[m+n] = r+s
else:
try:
del product_r[m+n]
except:
pass
n-= 1
n = t
m-=1
return product_r
def degreeiation(p,n):
if n!=0:
t = p
while (n>1):
t = product(t,p)
n-=1
else:
t={0:1}
return t
def division(p,q):
pol = {}
if degree(q)!= 0:
r = p[degree(p)]/q[degree(q)]
pol[degree(p)-degree(q)] = r
n_p = product(product(pol,q),{0:-1})
p = add(p,n_p)
else:
pol = product(p,q[degree(q)])
p = 0
if len(p)== 0:
p[0]=0
return p,pol
def divide(p,q):
cociente = {}
if degree(p)>=degree(q):
while degree(p)>=degree(q):
qt = division(p,q)
p = qt[0]
cociente.update(qt[1])
else:
cociente = {0:0}
return cociente
def remainder(p,q):
if degree(p)>=degree(q):
while degree(p)>=degree(q):
qt=division(p,q)
p = qt[0]
else:
pass
return p
def evaluar(p,x):
s = {0:0}
variables = sorted(p.keys())
for i in variables:
a = {0:p[i]}
b = degreeiation({0:x},i)
c = product(a,b)
s = add(product({0:p[i]},degreeiation({0:x},i)),s)
try:
r= s[0]
except:
r=0
return r
def simplificar(p):
keys_p = sorted(p.keys())
values = []
divisor = []
for i in keys_p:
values.append(p[i])
values = sorted(values)
i = values[-1]
while i>0:
div_temp=[]
for j in keys_p:
r = p[j]%i
if r==0:
div_temp.append(0)
else:
div_temp.append(1)
if 0 in div_temp:
divisor.append(i)
i-=1
values = sorted(values)
result = product(p,{0:Racional(1,values[-1])})
if result[sorted(result.keys())[-1]] < 0:
for i in result.keys():
result[i] = result[i]*(-1)
return Polynomial(result)
def verif(remainder):
try:
if len(remainder.polynomial) == 1:
if remainder.degree() == 0:
test = [False,remainder.polynomial]
else:
test = [True]
else:
test = True
except:
try:
a = remainder.polynomial
test = [True]
except:
test = [False,remainder.polynomial]
return test
class Polynomial(object):
def __init__(self, polynomial):
self.polynomial = polynomial
def __repr__(self):
try:
keys = self.polynomial.keys()
keys.reverse()
pol = ''
for i in keys:
if i!=0:
if self.polynomial[i]>0:
pol+=' '+str(self.polynomial[i])+'X^'+str(i)
else:
pol+=' '+str(self.polynomial[i])+'X^'+str(i)
else:
if self.polynomial[i]>0:
pol+= ' + '+str(self.polynomial[i])
else:
pol=pol+' '+str(self.polynomial[i])
if pol.startswith(' '):
pol = pol[2:]
else:
pass
except:
pol = str(self.polynomial)
return pol
def __add__(self, other):
return Polynomial(add(self.polynomial, other.polynomial))
__radd__ = __add__
def degree(self):
return degree(self.polynomial)
def __mul__(self, other):
return Polynomial(product(self.polynomial, other.polynomial))
__rmul__ = __mul__
def __sub__(self,other):
r_pol = {}
r_o = {}
keys_s = self.polynomial.keys()
keys_s.extend(other.polynomial.keys())
keys_s = list(set(keys_s))
for i in other.polynomial.keys():
r_o[i] = (-1)*other.polynomial[i]
for i in keys_s:
r_pol[i] = self.polynomial[i] + r_o[i]
return r_pol
def __rsub__(self, other):
r_pol = {}
r_o = {}
keys_s = self.polynomial.keys()
keys_s.extend(other.polynomial.keys())
keys_s = list(set(keys_s))
for i in self.polynomial.keys():
r_o[i] = (-1)*self.polynomial[i]
for i in keys_s:
r_pol[i] = other.polynomial[i] + r_o[i]
return r_pol
return result
def __div__(self, other):
return Polynomial(divide(self.polynomial, other.polynomial))
def __pow__(self,n):
return Polynomial(degreeiation(self.polynomial,n))
def __getitem__(self,i):
return Polynomial(evaluar(self.polynomial,i))
def __eq__(self,other):
keys_self = self.polynomial.keys()
keys_other = other.polynomial.keys()
keys_self.extend(keys_other)
l_key = keys_self[-1]
while l_key >= 0:
try:
if self.polynomial[l_key] == other.polynomial[l_key]:
r = True
l_key-=1
else:
r = False
l_key = -1
except:
r = False
l_key = -1
return r
def __ne__(self, other):
if (self==other) == True:
return False
else:
return True
def __mod__(self, other):
return Polynomial(remainder(self.polynomial, other.polynomial))
def mcd(self, other):
divisor = []
remainder_s = []
remainder = self%other
try:
if verif(remainder)[0] == False:
remainder_s.append(verif(remainder)[1])
test = False
except:
test = True
while test :
rmax_exp = int(sorted(remainder.polynomial.keys())[-1])
omax_exp = int(sorted(other.polynomial.keys())[-1])
remainder = simplificar(remainder.polynomial)
if other.polynomial[omax_exp] % int(remainder.polynomial[rmax_exp]) == 0:
remainder_s.append(remainder.polynomial)
remainder = other % remainder
test = verif(remainder)[0]
if test == False:
remainder_s.append(verif(remainder)[1])
print test
else:
print 'hey'
test = False
try:
remainder_f = remainder_s[-1]
if remainder_f[0] == 0:
mcd = remainder_s[-2]
else:
mcd = 1
except:
mcd = other
return remainder_s