Complexité, TP

Dans cette séance, on illustre les notions de complexité par quelques calculs simples, qui sont aussi l’occasion d’introduire quelques principes et algorithmes de base.

Éviter de calculer deux fois la même chose

Évaluation de polynômes

1. Mettre la précision de xcas à 300 chiffres.

   solution xcas ⇲ ⇱ solution xcas

   Digits:= 300;
   

2. Créer une liste de 3001 coefficients flottants \(a_k\).

   solution xcas ⇲ ⇱ solution xcas

   Attention, rand(1.) ne renvoie pas de flottants à précision 300, on passe par une fonction transcendante pour obtenir des valeurs ayant vraiment 300 chiffres.

   a := seq(evalf(log(rand(50)+2)),k=0..3000);
   

3. Calculer \(\sum a_k \pi^k\).

   solution xcas ⇲ ⇱ solution xcas

   p := evalf(pi); sum(a[k]*p^k, k=0..3000);
   

4. Essayer d’avoir la méthode la plus rapide.

   solution xcas ⇲ ⇱ solution xcas

   On peut éviter de calculer indépendamment les puissances \(p^k\) en écrivant

   eval2(a,p) := {
     local s, k, pk;
     s := 0; pk := 1;
     for (k := 0; k < length(a); k++)
     {
       s := s + a[k] * pk;
       pk := pk * p;
     }
     s;
   }
   

   et même diviser par 2 le nombre de multiplications en adoptant le schéma de Horner

   \[\sum a_k p^k = a_0+p(a_1+p(a_2+p(a_3+\dots)))\]

   eval3(a,p) := {
     local s, k;
     s := 0;
     for (k := length(a) - 1; k >= 0; k--)
       { s := s * p + a[k]; }
     s;
   }
   

Exponentiation rapide

Calculons simplement \(x^n\). Par définition, c’est le produit

\[x\times x^{n-1} = x\times x\times x\times\dots x\]

faisant intervenir \(n-1\) multiplications. Mais si l’on coupe au milieu, on voit que l’on peut écrire selon la parité de \(n\)

\[\begin{split}x^n = \begin{cases} (x^k)^2 &\text{ si }n=2k\text{ est pair}\\ x\times(x^k)^2 &\text{ si }n=2k+1\text{ est impair} \end{cases}\end{split}\]

où le terme \(x^k\) ne doit évidemment être calculé qu’une fois.

1. Écrire une fonction pow_naif(a,n) qui calcule \(a^n\) de manière récursive naive.

   solution xcas ⇲ ⇱ solution xcas

   pow_naif(a,n):={
     if(n==0) return(1);
     return( a*pow_naif(n-1) );
     }
   

2. Écrire une fonction pow_rec(a,n) qui calcule \(a^n\) par exponentiation rapide de manière récursive. La tester en calculant pow_rec(a,19).

   solution xcas ⇲ ⇱ solution xcas

   Il y a deux solutions à ce problème, selon l’endroit où l’on prend le carré:

   pow_rec(a,n):= {
     if(n==0) return 1;
     if(irem(n,2)) return a*pow_rec(a,iquo(n,2))^2;
     return pow_rec(a,n/2)^2;
   }
   

   ou bien:

   pow_rec(a,n):= {
     if(n==0) return 1;
     if(irem(n,2)) return a*pow_rec(a^2,iquo(n,2));
     return pow_rec(a^2,n/2);
   }
   

   solution sage ⇲ ⇱ solution sage

   Il y a deux solutions à ce problème, selon l’endroit où l’on prend le carré:

   def pow_rec(a,n):
     if n==0: return 1
     r = pow_rec(a^2,n//2)
     if n%2:
       return r*a
     else:
       return r
   

   ou bien:

   def pow_rec(a,n):
     if n==0: return 1
     r = pow_rec(a,n//2)^2
     if n%2:
       return r*a
     else:
       return r
   

3. Écrire la fonction pow_iter(a,n) qui effectue le même calcul de manière itérative.

   solution xcas ⇲ ⇱ solution xcas

   pow_iter(a,n):= {
     local(r:=1);
     while(n>0) {
       if (n%2==1) {r := r*a};
       a := a^2;
       n := iquo(n,2);
     };
     return(r);
   }
   

   solution sage ⇲ ⇱ solution sage

   Si l’on ne veut pas calculer a priori la décomposition binaire de \(n\), la solution la plus simple correspond au premier algorithme récursif.

   def pow_iter(a,n):
     r = 1
     while n>0:
       if n%2:
         r *= a
       a = a^2
       n = n//2
     return r
   

4. Exemple à retenir : quel est le coût du calcul des trois derniers chiffres de \(3^{123456789}\) ?

   solution xcas ⇲ ⇱ solution xcas

   Pour obtenir les trois derniers chiffres, il faut prendre le reste modulo 1000. Et puisque la projection \(\Z\to \Z/1000\Z\) est un morphisme d’anneaux, il faut surtout effectuer tout le calcul modulo 1000 en écrivant:

   pow_rec(3%1000,123456789)
   

   et non pas prendre le reste à la fin, ce qui demande de calculer un nombre gigantesque (ce que Xcas ne peut pas faire):

   pow_rec(3,123456789) % 1000
   

Note

à retenir

Pour tout entier \(n\geq 1\), on peut calculer \(a^n\) avec au plus \(2r\) multiplications où \(r=\floor{\log_2(n)+1}\)

Reformuler

multiplication de Karatsuba

\[\begin{split}(ax+b)(cx+d) &= acx^2 + (ad + bc)x + bd\\ (a-b)(c-d) &= ac + bd - (ad + bc)\end{split}\]

de sorte qu’on peut écrire avec seulement 3 multiplications

\[(ax+b)(cx+d) = acx^2 + (ac+bd-(a-b)(c-d))x + bd\]

1. En examinant la croissance des temps de calcul, essayez de voir si la multiplication de grands entiers est programmée de manière naïve ou avec Karatsuba dans xcas.
2. En appliquant récursivement cette idée, combien de multiplications élémentaires fait-on pour multiplier deux entiers de \(2^n\) chiffres ?
3. Quelle est la complexité de la multiplication de Karatsuba ?

Choisir l’ordre des étapes

calcul de \(n!\)

1. Écrire une fonction fact(n) qui calcule la factorielle de \(n\).

2. Quelle est sa complexité binaire ?

3. Implanter la variante suivante, qui consiste à faire uniquement des multiplication entre opérandes de même taille en écrivant

   \[n! = \bigl(1\times 2\times\cdots \floor{\frac{n}2}\bigr) \bigl(\floor{\frac{n}2+1}\times \cdots (n-1) \times n\bigr)\]

   Quelle est la complexité ? Comparer les temps d’exécution pour \(200000!\).

Faire des maths

1. Combien de termes faut-il sommer pour calculer \(\exp(2017)\) par la série usuelle avec une précision de \(2017\) chiffres ?
2. Et pour \(\exp(-2017)\) ?
3. Évaluer la complexité du calcul de \(e^{-x}\) par sommation de série ou par inversion de \(e^{x}\). Conclusion ?

Se ramener à ce qu’on sait bien faire

Inversion

1. Régler xcas pour faire des calculs avec 300 chiffres.
2. Poser x := Pi et y := 0.3.
3. Calculer quelques termes de l’itération y := y * (2 - y * x). Vers quelle valeur la suite converge-t-elle ?
4. Combien d’itérations faut-il pour avoir un résultat exact ? Quelle est la vitesse de convergence ?

Racine

1. Pour calculer numériquement la racine carrée de \(a\), on définit la suite

   \[x_0 = 1, x_{n+1} = \frac{x_n+a/x_n}2\]

2. Écrire une procédure rac(a) qui effectue dix itérations de cette suite, et affiche à chaque étape \(n\) les décimales communes à \(x_n\) et \(x_{n-1}\). On fera le calcul en précision 200.

3. Quelle est la vitesse de convergence de la suite ? Combien d’itérations faut-il pour obtenir un million de chiffres de \(\sqrt{5}\) ?

4. Quelle est la théorie qui se cache derrière ces deux exemples ?

Fibonacci

On considère la suite classique \(f_0=f_1=1\), \(f_{n+1}=f_n+f_{n-1}\).

1. Programmer le calcul récursif naïf de la suite. Quelle est sa complexité ? Calculer \(f_{34}\).

2. Programmer le calcul des \(f_n\) à l’aide d’une fenêtre glissante (on conserve les deux derniers termes en mémoire). Quelle est la complexité ? Calculer \(f_{10^5}\).

3. En écrivant la récurrence linéaire

   \[\begin{split}F_n = A F_{n-1}, \text{ où } A = \left(\begin{array}{cc}1 & 1 \\ 1 & 0\end{array}\right) \text{ et } F_n = \left(\begin{array}{c}f_{n+1}\\f_{n}\end{array}\right)\end{split}\]

   et l’expression de \(F_n=A^nF_0\), calculer à nouveau \(f_{10^5}\). Quelle est la complexité du calcul, pourquoi ?

4. Comparer les temps de calcul de \(f_{2^{25}-1}\) et \(f_{2^{25}}\), commenter.

5. Calculer la suite des \(x^n \bmod x^2-x-1\). Que trouve-t-on ?

6. Rappeler comment on obtient l’expression algébrique exacte

   \[f_n = \frac{\phi^{n+1}-(1-\phi)^{n+1}}{\sqrt{5}}, \phi = \frac{1+\sqrt{5}}2\]

   et utilisez-la pour calculer \(f_n\).

7. Quel est le nombre de chiffres de \(f_{f_{f_{f_{f_4}}}}\) ?