Resolve "Create Lagrange method"

Closes #12 (closed)

reed_solomon.py

@@ -23,35 +23,34 @@ def get_possibilities(l: list):
 	return p
 
 def lagrange_compute(l: list) -> polynome:
-	list_s = [0] * len(l)
-	list_p = [0] * len(l)
-	sum_poly = polynome(list_s)
-	#product_poly = polynome(list_p)
-	first_time = True
-
-	for x_i, y_i in enumerate(l):
-		for x_j, y_j in enumerate(l):
-			if x_j != x_i:
-				list_p[0] = -x_j / (x_i - x_j)
-				list_p[1] =	1 / (x_i - x_j)
-				if first_time:
-					product_poly = polynome(list_p)
-					first_time = False
-				else:					
-					product_poly = product_poly.mul(polynome(list_p))
-		product_poly.show()
-		first_time = True
-		sum_poly = sum_poly.add(product_poly)
-		sum_poly.show()
-		list_p = [0] * len(l)
-	return sum_poly
+	poly = [0] * len(l)
+	for x_i, y_i in l:
+		#Produit des coeffs
+		coeff = [0] * len(l)
+		
+		denominator = 1
+		for j in range(len(l)):
+			if x_i != j:
+				denominator *= x_i - l[j][0]
+		coeff[0] = 1 / denominator #Produit de chaque denominateur
+
+		for k in range(len(l)):
+			new_coeff = [0] * (len(l)+1)
+			if x_i != k:
+				for j in range(k+1 if k<x_i else k, 0, -1):
+					new_coeff[j+1] += coeff[j]
+					new_coeff[j] -= l[k][0] * coeff[j]
+			coeff = new_coeff
+
+		#Somme des coeffs
+		for s in range(len(l)):
+			poly[s] += y_i * coeff[s]
+	return poly
 
 def check_nb_error(l: list, p: polynome) -> int:
 	pass
 
 if __name__ == '__main__':
-	list_ = [1, 2, 3]
-	#print(list_)
+	list_ = [(0, 1), (1, 2), (2, 3)]
 	poly = lagrange_compute(list_)
-	poly.show()
-	#print(poly.evaluate(0))
+	print(poly)