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.
  2. Créer une liste de 3001 coefficients flottants \(a_k\).
  3. Calculer \(\sum a_k \pi^k\).
  4. Essayer d’avoir la méthode la plus rapide.

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.
  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).
  3. Écrire la fonction pow_iter(a,n) qui effectue le même calcul de manière itérative.
  4. Exemple à retenir : quel est le coût du calcul des trois derniers chiffres de \(3^{123456789}\) ?

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}}}}\) ?