exercice de complexité: division euclidienne rapide

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

Répondre
parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

exercice de complexité: division euclidienne rapide

Message par parisse » dim. avr. 05, 2020 5:42 pm

Je vous propose de réfléchir à comment vous pourriez présenter et illustrer l'algorithme ci-dessous, dans l'esprit où ce serait un paragraphe d'un texte: cela veut donc dire le présenter en complétant ce qui est volontairement non détaillé ci-dessous (à la fois mathématique et sur la complexité) et en proposant une illustration machine.

On s'intéresse à la division euclidienne de 2 polynomes A et B à coefficients sur un corps fini K où les opérations arithmétiques sont supposés en cout O(1). Le cas le plus défavorable est celui où le degré de B est à peu près la moitié de celui de A. Si A est de degré n, B de degré m avec m proche de n/2, la division naive est alors en O(n^2).

Soit donc

Code : Tout sélectionner

  A=B*Q+R 
avec degre(A)=n, degre(B)=m et degre(R)<m.
On commence par faire le changement de variable x->1/x, et on multiplie par x^n

Code : Tout sélectionner

  x^n*A(1/x)=x^m*B(1/x)*x^(n-m)*Q(1/x)+x^(n-m+1)*x^(m-1)*R(1/x) 
et donc il existe 4 polynomes a, b, q, r dont les coefficients s'expriment simplement en fonction de A, B, Q et R tels que

Code : Tout sélectionner

  a=b*q+x^(n-m+1)*r
On a donc q=a*l'inverse de b modulo x^(n-m+1)

L'algorithme de division rapide consiste à calculer l'inverse de b modulo x^(n-m+1), on en déduit q puis R par des opérations de multiplication qui peuvent etre accélérées.

Pour calculer l'inverse de b modulo x^t, on utilise une suite récurrente b_t de polynomes.
Pour t=1, on prend b_0=inverse(coefficient constant de b).
Soit b_t l'inverse de b modulo x^t, on a donc :

Code : Tout sélectionner

  b*b_t=1+x^t*c
donc :

Code : Tout sélectionner

  b*b_t*(1-x^t*c)=1 mod x^2t
on en déduit

Code : Tout sélectionner

  b_2t=2*b_t-b*b_t^2 mod x^2t

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice de complexité: division euclidienne rapide

Message par megarbane » mer. avr. 08, 2020 8:09 am

On commence par regarder la division euclidienne. Je suis en vocal avec Anthony au fait.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: exercice de complexité: division euclidienne rapide

Message par etuagreg » mer. avr. 08, 2020 8:26 am

Ici on a pris b le polynôme symétrique de B. Donc b et B sont reliés par la relation b = B(1/x) * x^m. Or B est de degré m donc son coefficient de degré m est non nul. Quant on passe aux polynômes symétriques le coefficient de degré m de B devient le coefficient constant de b. Ainsi b ne s'annule pas en 0 et donc b est premier avec x donc premier avec x^n-m+1. Ainsi par le théorème de bézout on trouve un inverse de b modulo x^n-m+1. Donc prendre l'inverse de b modulo x^n-m+1 a bien un sens.

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 8:36 am

Oui. Les polynomes a,b,q et r sont effectivement obtenus en inversant l'ordre des coefficients et ont leur coefficient constant non nul.

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice de complexité: division euclidienne rapide

Message par megarbane » mer. avr. 08, 2020 8:54 am

Petite question concernant la complexité du calcul de c : comme on n'est pas intéressés par tous les coefficients de c (mais seulement ceux de degré 0 à (t-1)), est-ce que l'on garde la méthode naïve de multiplication de polynômes (pour ne calculer que les coefficients intéressants du produit b*b_t) ou alors on a des méthodes rapides qui ne gardent que les coefficients intéressants ?

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: exercice de complexité: division euclidienne rapide

Message par etuagreg » mer. avr. 08, 2020 8:56 am

Dans le calcul de b_t, le polynôme c est bien définit. En effet pour tout t, b est premier avec x^t donc b est inversible modulo x^t et on note b_t son inverse. On trouve donc :
b*b_t = 1 modulo x^t ce qui revient à b*b_t = 1 + x^t*c où c est le polynôme définit dans la relation.

Pour calculer c on se retrouve avec c*x^t = b*b_t - 1. Le coût du calcul revient donc à multiplier b et b_t car la multiplication par x^t est sulement un décalage d'indice donc a un coût très faible. D'autre part on veut seulement les coefficients de degré >= t dans la multiplication de b par b_t. On se retrouve avec min(k+1,t,m+t-k) multiplications pour calculer le coefficient d'ordre k et autant d'additions. Finalement on aura un nombre d'opérations égale à 2*\sum_{k=t}^{m+t-1} (min(k+1,t,m+t-k)) .

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 9:04 am

megarbane a écrit :
mer. avr. 08, 2020 8:54 am
Petite question concernant la complexité du calcul de c : comme on n'est pas intéressés par tous les coefficients de c (mais seulement ceux de degré 0 à (t-1)), est-ce que l'on garde la méthode naïve de multiplication de polynômes (pour ne calculer que les coefficients intéressants du produit b*b_t) ou alors on a des méthodes rapides qui ne gardent que les coefficients intéressants ?
On peut bien sur faire la multiplication naive et ne conserver que les coefficients de degre plus petits que t, mais quand t approche de n-m+1 qui est proche de n/2, cela devient beaucoup moins efficace que Karatsuba ou la FFT.
La FFT est en O(n*ln(n)) on peut difficilement faire mieux, tant pis pour les coefficients qui ne servent pas.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: exercice de complexité: division euclidienne rapide

Message par etuagreg » mer. avr. 08, 2020 9:06 am

En multipliant la première égalité par 1-x^t*c on obtient exactement la deuxième égalité. On remarque dans cette deuxième égalité que l'on trouve l'inverse de b modulo x^2t donc on identifie b_t*(1-x^t*c) à b_2t par unicité de l'inverse modulo x^2t. Il apparait que l'on doit calculer c modulo x^t pour trouver b_2t en fonction de b_t.

Anthony

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 9:08 am

etuagreg a écrit :
mer. avr. 08, 2020 8:56 am
Dans le calcul de b_t, le polynôme c est bien définit. En effet pour tout t, b est premier avec x^t donc b est inversible modulo x^t et on note b_t son inverse. On trouve donc :
b*b_t = 1 modulo x^t ce qui revient à b*b_t = 1 + x^t*c où c est le polynôme définit dans la relation.

Pour calculer c on se retrouve avec c*x^t = b*b_t - 1. Le coût du calcul revient donc à multiplier b et b_t car la multiplication par x^t est sulement un décalage d'indice donc a un coût très faible. D'autre part on veut seulement les coefficients de degré >= t dans la multiplication de b par b_t. On se retrouve avec min(k+1,t,m+t-k) multiplications pour calculer le coefficient d'ordre k et autant d'additions. Finalement on aura un nombre d'opérations égale à 2*\sum_{k=t}^{m+t-1} (min(k+1,t,m+t-k)) .

Anthony
En fait, c'est aussi simple d'appliquer la récurrence b_2t=2*b_t-b*b_t^2 mod x^2t. Le calcul de complexité par une multiplication naive n'est pas très intéressant ici, l'algorithme n'a d'intéret que si on utilise une multiplication rapide de polynomes (sinon il vaut mieux faire la division euclidienne naive sans se poser de questions)
Il y a donc au pire 2 multiplications avec des arguments de degrés plus petits que 2t (on peut tronquer).

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 9:10 am

Ensuite il faut sommer sur les valeurs de t que l'on utilise dans l'algorithme (t=1 puis t=2 puis t=4 etc. jusqu'à atteindre n-m+1 qui est d'ordre n).

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: exercice de complexité: division euclidienne rapide

Message par etuagreg » mer. avr. 08, 2020 9:20 am

Oui c'est e que j'allais faire ensuite. Le mieux est de calculer par la dernière formule qui s'obtient en remplaçant c par sa valeur donnée par la première expression. On se retrouve avec une multiplication de trois polynômes qui donne une complexité t*log(t) + 2t*log(2t) qui équivaut à une complexité en 3t*log(t). Et on calcule de manière récurrente nos b_2t donc on somme 3t*log(t) pour t variant dans les puissances de 2 jusqu'à être plus grand que l'inverse recherché.

Anthony

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice de complexité: division euclidienne rapide

Message par megarbane » mer. avr. 08, 2020 9:24 am

Tu préfères qu'on fasse des illustrations sur Xcas de la méthode de division euclidienne, ou plutôt de passer aux racines de polynômes ?

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 9:33 am

Peut-etre qu'il vaut mieux finir la division euclidienne maintenant, donc donner l'estimation de la complexité (en utilisant le produit par FFT) et proposer un programme de calcul d'inverse modulo x^t. Au cas où vous séchez, j'ai mis une session de correction ici: viewforum.php?f=28. J'y ai aussi mis une session pour les racines de polynomes, mais je vous conseille de ne pas la regarder avant d'avoir cherché!

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 10:02 am

Une majoration grossière de la complexité nous donne à chaque étape t*ln(t)<=n*ln(n) et il y a au plus ln(n) étapes, donc n*ln(n)^2. Mais en fait c'est mieux, la complexité est la somme des 2^k*ln(2^k) pour les puissances successives de 2 jusqu'à ce que 2^k>n-m+1.
Comme sum(2^k*k,k,0,N) == -2^(N+1+1)+2^(N+1)*(N+1)+2 (calcul fait avec Xcas), on a une complexité en n*ln(n) pour calculer q, donc Q donc R puisque Q=A-B*Q fait intervenir des opérations en O(n) et O(n*ln(n)).

parisse
Messages : 5346
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice de complexité: division euclidienne rapide

Message par parisse » mer. avr. 08, 2020 10:04 am

Un exemple de session d'illustration
session Xcas

Répondre