Mathématiques et Python - Produit de polynômes en Python : principe du « diviser pour régner »

Un billet blog de Denis Hulo

I. Introduction

On souhaite montrer comment utiliser le principe du « diviser pour régner » afin de développer un produit de petits polynômes avec un minimum d'opérations de multiplication entre termes.

Pour cela, on va d'abord décrire cette méthode à l'aide d'un exemple simple de multiplication de nombre entiers, puis de petits polynômes, pour ensuite l'implémenter en Python.


II. Principe du « diviser pour régner »

Une multiplication entre deux nombres entiers nécessite de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande.

Si ces deux nombres ont n chiffres, cela exige n2 produits. La multiplication 10*10 nécessite ainsi 4 multiplications de chiffre.

On dit que le calcul a une complexité en temps quadratique, ou en O(n2).

Si on prend maintenant le produit de nombres entiers :

p = 10 × 10 × 11 × 11 × 12 × 12 × 13 × 13

En effectuant les calculs de gauche à droite, on obtient successivement :

p = (10×10) × 11 × 11 × 12 × 12 × 13 × 13

La 1re multiplication nécessite donc 4 opérations de multiplication entre chiffres.

En poursuivant les calculs :

p = 100 × 11 × 11 × 12 × 12 × 13 × 13

p = (100 × 11) × 11 × 12 × 12 × 13 × 13

On a ainsi besoin jusque là de 4 + 6 opérations de multiplication.

Puis :

p = (1100 × 11) × 12 × 12 × 13 × 13

Ce qui fait alors au total 4 + 6 + 8 opérations.

etc..

En poursuivant les calculs vers la droite, on obtient finalement 4 + 6 + 8 + 10 + 12 + 14 + 16 = 70 opérations de multiplication en tout pour ce produit.


Considérons maintenant le même produit réarrangé :

p = ((10 × 10) × (11 × 11)) × ((12 × 12) × (13 × 13))

Si on effectue les calculs en respectant la règle de priorité des parenthèses, on peut alors les représenter sur un arbre de produits :

648991

On a donc besoin dans ce cas de seulement 59 opérations de multiplication entre chiffres au lieu de 70 précédemment.

Il s'agit du principe du « diviser pour régner » :

• Diviser : découper un problème initial en sous-problèmes ;
  
• Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
  
• Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
  

On peut également appliquer ce même principe pour la multiplication de petits polynômes :

648992


Important : L'intérêt principal des arbres de produits est en fait de tirer parti des algorithmes de multiplication rapide d'entiers ou de polynômes.

La situation la plus simple est celle où l'on cherche à calculer le produit d'un grand nombre de « petits » entiers ou polynômes.

Dans ce contexte, et pourvu que l'on dispose d'une multiplication rapide, l'algorithme diviser pour régner est plus efficace que la méthode classique.

Dans notre cas, on va déjà montrer ses avantages dans le développement d'un produit de petits polynômes sans parler de multiplication rapide.



III. Implémenter le développement d'un produit de polynômes

On utilise à nouveau notre classe Polynome à laquelle on ajoute un attribut permettant de compter le nombre d'opérations de multiplication entre termes nécessaires pour développer un produit de polynômes :

class Polynome:

def __init__(self, liste_coefs=): # méthode constructeur de la classe

# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
self.coefs = liste_coefs

# on initialise le nombre d'opérations de multiplication entre termes
self.nombre_operations = 0

# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
self.reduire()

...

Le code de la méthode permettant de multiplier deux polynômes devient alors :

class Polynome:

...

def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2

# initialisation de la liste des coefficients qu'avec des zéros
liste_coefs=*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
# multiplication des coefficients d'indices i1 et i2
liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs*other.coefs

poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste

# ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes
poly.compteur_operations = self.compteur_operations + other.compteur_operations + len(self.coefs)*len(other.coefs)

return poly # renvoie le polynôme résultat de la multiplication

Rappel important : les objets Polynome de notre classe sont représentés par une liste de coefficients dont la longueur est égale au degré du polynôme + 1 :

Par exemple, le polynôme X3 + 2 = 2 + 0.X + 0.X2 + X3 sera représenté par la liste de coefficients [2, 0, 0, 1].

Par conséquent, le développement du produit (X3 + 2)(X3 + 2) nécessite en fait 4*4 = 16 multiplications entre termes.


III-A. Méthode classique

Testons maintenant l'opérateur de multiplication entre polynômes avec la méthode classique :

# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])

# produit de polynômes
p = p1*p1*p2*p2*p3*p3*p4*p4

print("produit = ({0})*({0})*({1})*({1})*({2})*({2})*({3})*({3})".format(p1,p2,p3,p4))
print()

print("produit développé = " + str(p))
print()

print("nombre d'opérations = " + str(p.nombre_operations))


Le code affiche :

produit = (1 + X)*(1 + X)*(2 + X)*(2 + X)*(3 + X)*(3 + X)*(4 + X)*(4 + X)

produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8

nombre d'opérations = 70


III-B. Principe du « diviser pour régner »

On peut également, comme on l'a vu précédemment, regrouper les sous-produits sur un arbre de produits.

On obtient ainsi la fonction récursive basée sur le principe du « diviser pour régner » :

def produit_polynomes(*polynomes):

# test si le tuple polynomes contient plus de 1 élément
if len(polynomes)>1:
i=len(polynomes)//2 # valeur du milieu
# appels récursifs
return produit_polynomes(*polynomes[:i])*produit_polynomes(*polynomes[i:])
else: # sinon
# renvoie l'unique polynôme du tuple
return polynomes

Libre à chacun ensuite d'optimiser ce code.

Testons notre fonction avec ces quelques lignes :

# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])

# p = ((p1*p1)*(p2*p2))*((p3*p3)*(p4*p4))
p = produit_polynomes(p1,p1,p2,p2,p3,p3,p4,p4)

print("produit = ((({0})*({0}))*(({1})*({1})))*((({2})*({2}))*(({3})*({3})))".format(p1,p2,p3,p4))
print()

print("produit développé = " + str(p))
print()

print("nombre d'opérations = " + str(p.nombre_operations))

Le code affiche :

produit = (((1 + X)*(1 + X))*((2 + X)*(2 + X)))*(((3 + X)*(3 + X))*((4 + X)*(4 + X)))

produit développé = 576 + 2400.X + 4180.X^2 + 3980.X^3 + 2273.X^4 + 800.X^5 + 170.X^6 + 20.X^7 + X^8

nombre d'opérations = 59


IV. Module complet

On donne pour finir le contenu du module complet :

class Polynome:

def __init__(self, liste_coefs=): # méthode constructeur de la classe

# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
self.coefs = liste_coefs

# on initialise le nombre d'opérations de multiplication entre termes
self.nombre_operations = 0

# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
self.reduire()

def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2
s="" # initialisation de la chaîne de caractères
# on vérifie d’abord si le degré du polynôme est nul
if (len(self.coefs)-1==0):
return str(self.coefs)
else: # sinon
if self.coefs!=0:
s=str(self.coefs) + " + "
for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an]
if self.coefs!=0: # si le coefficient de degré i n'est pas nul
if self.coefs!=1: # si le coefficient de degré i est différent de 1
s+="{}.X^{} + ".format(self.coefs,i)
else: s+="X^{} + ".format(i)

# élimination des caractères en trop
s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X")
if s[-2:]=="^1": s = s[:-2]
if s[:3]=="1.X": s = s[3:]

return s # on retourne l'expression du polynôme


def degre(self): # retourne le degré du polynôme
return (len(self.coefs)-1)


def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...

for i in range(n): # parcours des indices de liste_coefs
liste_coefs = self.coefs + other.coefs # addition des coefficients de degré i

return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition


def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...

for i in range(n): # parcours des indices de liste_coefs
liste_coefs = self.coefs - other.coefs # addition des coefficients de degré i

return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition


def reduire(self):
# tant que le dernier élément de la liste est nul
while round(self.coefs[-1],12) == 0 and len(self.coefs)>1:
self.coefs.pop() # supprimer le dernier élément

for i in range(len(self.coefs)):
self.coefs = round(self.coefs,12)


def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2

# initialisation de la liste des coefficients qu'avec des zéros
liste_coefs=*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
# multiplication des coefficients d'indices i1 et i2
liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs*other.coefs

poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste

# ajout du nombre d'opérations de multiplication entre termes effectuées lors de la multiplication entre polynômes
poly.nombre_operations = self.nombre_operations + other.nombre_operations + len(self.coefs)*len(other.coefs)

return poly # renvoie le polynôme résultat de la multiplication


def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n
# on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes
poly = Polynome()

for i in range(n): # on multiplie n fois poly par self à l'aide de l'opérateur *
poly = poly*self # équivalent à : poly = poly.__mul__(self)

return poly # renvoie le polynôme résultat de l'opération (self ** n)


def __eq__(poly1, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes

return (poly1.coefs==other.coefs) # renvoie True si les 2 listes de coefficients sont égales


def eval(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
# intialisation des variables
valeur_polynome = self.coefs # valeur_polynome = a0
power=1

for coef in self.coefs[1:]: # parcours des coefficients du polynôme à partir de a1 : a1, a2, ..., an
power = power*x # calcul de la puissance de x pour ai : power = x^i
valeur_polynome += coef*power # valeur_polynome = valeur_polynome + ai*x^i

return valeur_polynome # renvoie la valeur du polynôme

def eval_horner(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
# intialisation de la variable
valeur_polynome = self.coefs[-1] # valeur_polynome = an

for coef in reversed(self.coefs[:-1]): # parcours des coefficients du polynôme à partir de an-1 : an-1, ..., a1, a0
valeur_polynome = valeur_polynome*x + coef # valeur_polynome = valeur_polynome*x + ai

return valeur_polynome # renvoie la valeur du polynôme


def produit_polynomes(*polynomes):

# test si le tuple polynomes contient plus de 1 élément
if len(polynomes)>1:
i=len(polynomes)//2 # valeur du milieu
# appels récursifs
return produit_polynomes(*polynomes[:i])*produit_polynomes(*polynomes[i:])
else: # sinon
# renvoie l'unique polynôme du tuple
return polynomes


print()
print("I. Produit de polynômes : méthode classique")
print()

# création des polynômes p1 = X + 1; p2 = X + 2; p3 = X + 3; p4 = X + 4
p1 = Polynome([1,1]); p2 = Polynome([2,1]); p3 = Polynome([3,1]); p4 = Polynome([4,1])

# produit de polynômes
p = p1*p1*p2*p2*p3*p3*p4*p4

print("produit = ({0})*({0})*({1})*({1})*({2})*({2})*({3})*({3})".format(p1,p2,p3,p4))
print()

print("produit développé = " + str(p))
print()

print("nombre d'opérations = " + str(p.nombre_operations))

print()
print()
print("II. Produit de polynômes : principe du diviser pour régner")
print()

# produit de polynômes
# p = (p1*p1*p1)*(p2*p2*p2)
# p = ((p1*p1)*(p2*p2))*((p3*p3)*(p4*p4))
p = produit_polynomes(p1,p1,p2,p2,p3,p3,p4,p4)

print("produit = ((({0})*({0}))*(({1})*({1})))*((({2})*({2}))*(({3})*({3})))".format(p1,p2,p3,p4))
print()

print("produit développé = " + str(p))
print()

print("nombre d'opérations = " + str(p.nombre_operations))


V. Conclusion

Nous avons donc pu montrer les avantages du « diviser pour régner » dans le calcul du produit de nombres entiers, puis dans le développement du produit de petits polynômes, pour enfin le vérifier en Python à l'aide de la classe Polynome.


Sources :

https://fr.wikipedia.org/wiki/Algorithme_de_multiplication_d%27entiers
https://fr.wikipedia.org/wiki/Diviser_pour_r%C3%A9gner_(informatique)
https://fr.wikipedia.org/wiki/Arbre_de_produits
https://fr.wikipedia.org/wiki/Tri_fusion