# funzione che elimina gli zero "in coda" al polinomio
def zeri(polinomio):
	n = len(polinomio) - 1
	temp = []
	for i in range(n,-1,-1):
		if polinomio[i] != 0:
			temp = polinomio[:(i+1)]
			break
	return temp

# funzione che controlla se un polinomio e' il polinomio nullo
# affinche' la funzione lavori correttamente, al polinomio
# in input deve essere stata preventivamente applicata la funzione zeri()
def is_not_zero(polinomio):
	if len(polinomio) == 0:
		return False
	else:
		return True

# funzione che effettua l'algoritmo di riduzione su f e g
# restituendo una lista con quoziente e resto		
def riduzione(f,g):
	if len(f) < len(g): # si considera inizialmente il caso in cui g abbia grado maggiore di f
		q = []
		r = f[:]
	else: # se f ha grado maggiore od uguale a g si effettua la riduzione
		q = [0 for i in range(len(f) - len(g) + 1)]  # il quoziente avra' grado pari alla differenza dei gradi di f e g
		r = f[:]
		m = len(g)
		while (is_not_zero(r) and len(r) >= len(g)):
			n = len(r)
			d = n - m
			q[d] = float(r[n-1]) / float(g[m-1])
			for i in range(m):
				r[i + d] = r[i + d] - (float(r[n-1]) / float(g[m-1])) * g[i]
			r = zeri(r)
	return [q,r]
	
f = [2,3,1,2] # polinomio di prova, f = 2x^3 + x^2 + 3x + 2
g = [2,1] # polinomio di prova, g = x + 2
# si suppone che i due precedenti polinomi siano stati immessi senza zeri "in coda"
# altrimenti e' sufficiente applicare la funzion zeri() sia ad f che a g

if is_not_zero(g):
	risultato = riduzione(f,g)
else:
	print "Il polinomio g e' il polinomio nullo!"