1/4

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

Modérateur : xcasadmin

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

1/4

Message par parisse » mer. mars 25, 2020 11:00 am

Si quelqu'un souhaite préparer un texte et qu'on fasse une séance de questions-réponses comme le 25/3, je propose au choix
https://old.agreg.org/Textes/public2010-C2.pdf
ou
https://old.agreg.org/Textes/pub2008-C2.pdf

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

Re: 1/4

Message par parisse » sam. mars 28, 2020 6:30 am

S'il n'y a pas de volontaires pour un texte, on peut aussi faire quelques exercices de calcul de complexité.
1/ comparer le calcul de p^n pour p et n entiers par algorithme naif pxpx...xp ou une méthode comme pour la puissance rapide (attention pas de modulo ici), en utilisant la multiplication naive ou une multiplication rapide
2/ cout du calcul du n-ième nombre de Fibonacci. Par addition ou en utilisant les flottants multi-précision.
3/ cout du calcul d'un inverse dans GF(p,n), cout du calcul de l'inverse d'une matrice kxk dans GF(p,n)
4/ cout du pgcd de 2 polynomes de degré n dans GF(p,n) en fonction de n

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

Re: 1/4

Message par megarbane » mar. mars 31, 2020 7:30 am

Je pense que c'est une bonne idée de faire des calculs de complexités. Et on pourrait faire une petite séance de révision sur les complexités des algorithmes classiques. Je comptais faire des petites fiches avec les complexités à connaître (et des démonstrations rapides, qui permettent de voir ce que deviennent ces complexités dans des cas particuliers). Initialement, j'avais prévu de faire ça après les écrits... Donc je m'y mets bientôt et je vous tiens au courant.

Là c'est un peu difficile de trouver du temps pour préparer un texte (c'est difficile de trouver 4 heures d'affilées où je peux m'enfermer tranquille en ce moment). Mais si je trouve un créneau j'essaierai de préparer un texte. Et à la manière de ce qu'avait fait Anthony je vous enverrai un petit compte rendu et les algorithmes. Et on pourra faire une séance de questions/réponses sur le forum comme la dernière fois.

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

Re: 1/4

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

Pour la puissance, on veut aussi prendre en considération l'évolution des tailles des entiers (et l'incidence sur les complexités des opérations élémentaires, donc ici la multiplication) ? Ou alors juste le nombre d'opération suffit ?

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:18 am

Oui, il faut prendre en compte l'incidence de la taille des entiers sur le cout de la multiplication.
Ainsi cout de p*p^k est k*ln(p)^2 pour la multiplication naive.

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:27 am

Si vous trouvez le 1 et le 2 trop difficiles, reflechissez au 3 et au 4.

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

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 8:28 am

Si on ne tient pas compte de l'évolution des complexités en fonction de la taille des entiers considérés, on obtient alors :
- pour la naïve : n multiplication à faire, donc une complexité de n ;
- pour une méthode rapide (en utilisant l'écriture en base 2 de n) : log_2(n) + nombre de 1 en base 2 dans l'écriture de n multiplications.

En tenant compte de la taille des entiers pour le coût de la multiplication, on fait le détail des méthodes.

Pour la méthode naïve :
- pour passer de p à p^2 : coût de ln(p)^2 ;
- pour passer de p^2 à p^3 : coût de 2*ln(p)^2 ;
(et ainsi de suite)
- pour passer de p^{n-1} à p^n : coût de (n-1)*ln(p)^2.
Donc un coût total de : (n*(n-1))/2 * ln(p)^2

Pour la méthode intelligente (avec l'écriture de n en base 2) :
- si n est impair : on passe de p^[n/2] à p^n en faisant : p^n = p*p^[n/2]*p^[n/2]
- la première multiplication a un coût de (n/2)*ln(p)^2 ;
- la seconde a un coût de (n/2)*(n/2+1)*ln(p)^2.
et donc un coût total de : ln(p)^2*(n/2)*(n/2+2)
- si n est pair : on passe de p^(n/2) à p^n avec une seule multiplication dont le coût est : (n/2)^2 * ln(p)^2
On peut regarder ce qui se passe dans le pire des cas (si n n'a que des 1 dans son écriture en base 2) ou au meilleur des cas (si n est une puissance de 2) :
- pire des cas : on écrit n=sum_{k=0}^N 2^k, avec donc N=log_2(n+1)-1
on a N opérations du premier type à réaliser ; à l'opération d'indice M, on a un coût de m*(m+2)*ln(p)^2 où m=sum_{k=0}^{M-1} 2^k = 2^M-1
et donc un coût total de : ln(p)^2 *sum_{M=1}^N (2^M-1)*(2^M+1)
On développe, et on reconnaît une somme géométrique, ce qui donne un coût total dans le pire des cas de :
ln(p)^2 * [ (4/3)*(4^N-1) - N ]
(je pense que c'est bon avec ces corrections sur les indices)
Dernière modification par megarbane le mer. avr. 01, 2020 8:53 am, modifié 2 fois.

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

Re: 1/4

Message par etuagreg » mer. avr. 01, 2020 8:32 am

1/ comparer le calcul de p^n pour p et n entiers par algorithme naif pxpx...xp ou une méthode comme pour la puissance rapide (attention pas de modulo ici), en utilisant la multiplication naive

Algorithme naïf : px(px(...x(pxp))...)
Coût(p*(p^k))=k*ln(p)^2.
Ainsi : Coût(px...xp, k fois)=sum_{j=1}^k k*ln(p)^2= ln(p)^2*n(n+1)/2

Romain

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:34 am

D'accord pour la méthode p*p*...*p.
Pour cette méthode, on ne peut pas appliquer Karatsuba globalement, car les opérandes de p^k et p ne sont pas de meme taille. Si p est grand, on peut appliquer Karatsuba en décomposant p^k en tranches de taille ln(p), avec un cout en k*ln(p)^(ln(3)/ln(2)), donc un cout total Karatsuba en k^2*ln(p)^(ln(3)/ln(2))
Meme chose pour la multiplication par FFT, qui peut s'appliquer par tranche si p est grand, avec un cout en k^2*ln(p)*ln(ln(p)) (en négligeant les termes logarithmiques d'ordre supérieur)

@Thomas: Pour la méthode qui mime la puissance rapide, il faut ajouter le cout de calcul de p^[n/2].

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

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 8:49 am

Pour le cas idéal, on écrit n=2^N (avec donc N=log_2(n)). On a toujours N étapes. Et à l'étape M le coût est : m^2*ln(p)^2 avec m=2^{M-1}.
On somme de la même manière (en reconnaissant une série géométrique) et on a finalement une complexité totale de :
ln(p)^2 * (1/3) *(4^N-1)

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

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 8:51 am

(j'ai des petites erreurs sur les indices dans le cas le moins favorable que je vais corriger).

Et j'avais une question par rapport au cas non favorable : est-ce que l'on pourrait aller plus vite en calculant p^{n+1} puis en divisant par p ?

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:52 am

Ci-dessous mes calculs pour le 1/ en utilisant la meme méthode que la puissance rapide.
Je propose qu'on passe au 3 et au 4 avant de revenir au 2.

Méthode p^n=(p^(n/2))^2 si n est pair, et =p*p^((n-1)/2)^2 si n est impair.
Notons C(n) le cout.

Prenons le cas où n est une puissance de 2, on a alors
C(n)=C(n/2)+cout de la multiplication de p^(n/2) par lui-meme
par multiplication naive en faisant une étape de récursion,
C(n)=C(n/2)+(n/2*ln(p))^2
Donc
C(n)=C(n/4)+(n/4*ln(p))^2+(n/2*ln(p))^2
=...=n^2*ln(p)^2*(1/2^2+1/4^2+...+1/(2^log2(n))^2)
<= n^2*ln(p)^2*1/3
Le cout est donc comparable a la 1ere méthode (multiplication naive), avec une constante un peu meilleure (pi^2/24=0.41) dans le cas où n est une puissance de 2. Mais ici, on peut pleinement utiliser Karatsuba ou FFT car les multiplications ont des arguments de meme taille. Par exemple par FFT, on obtient O(n*ln(p)*ln(n*ln(p))) (en négligeant les termes logarithmiques d'ordre supérieur).

L'autre cas extreme est obtenu pour n=une puissance de 2 moins 1, dans ce cas les récursions se font toujours avec n impair, il faut ajouter le cout de la multiplication de p par p^(n-1), de p par p^((n-1)/2-1) etc., cout qui se majore (multiplication naive) par ln(p)^2*(n+n/2+n/4+...)=ln(p)^2*2*n, négligeable devant n^2*ln(p)^2* 1/3.

Observation:
dépendance en ln(p):
k:=1000; p:=10^k:; n:=1000; time(p^n); (->0.00689s sur mon ordi)
k:=2000; p:=10^k:; n:=1000; time(p^n); (->0.014s)
k:=4000; p:=10^k:; n:=1000; time(p^n); (->0.034s)
quand k est multiplie par 2, j'observe un temps de calcul multiplié par un facteur proche de 2.2, compatible avec O(n*ln(p)*ln(n*ln(p)))

dépendance en n:
n:=1000; p:=10^10000; time(p^n); (-> 0.1s)
n:=2000; p:=10^10000; time(p^n); (-> 0.21s)
n:=4000; p:=10^10000; time(p^n); (-> 0.49s)
quand n est multiplié par 2, j'observe aussi un temps de calcul multiplié par un facteur proche de 2.2, compatible avec O(n*ln(p)*ln(n*ln(p)))

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:53 am

megarbane a écrit :
mer. avr. 01, 2020 8:51 am
Et j'avais une question par rapport au cas non favorable : est-ce que l'on pourrait aller plus vite en calculant p^{n+1} puis en divisant par p ?
Oui, si n=2^k-1, je pense qu'on va plus vite en calculant p^(2^k)/p. Mais c'est très particulier!

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

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 8:56 am

Petite question pour 3 et 4 : on considère que le corps fini GF(p,n) est représenté à l'aide d'un polynôme irréductible de degré n sur F_p ?
Si c'est le cas on devrait donc traiter en même temps les deux questions (et ça vaut même le coup de faire la 4 avant, non ?).

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

Re: 1/4

Message par parisse » mer. avr. 01, 2020 8:59 am

Si n et p sont grands, on ne peut pas utiliser autre chose qu'une représentation par des polynomes.
Sinon, tu as raison pour la série de complexité du 1/, c'est une suite géométrique, je vais corriger ci-dessus.

Répondre