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.
Mettre la précision de xcas à 1000 chiffres.
Digits:= 1000;
bitprec = ceil(1000*log(10,2))
R = RealField(bitprec)
Créer la liste de flottants \(a_k=\log(2+k), 0\leq k\leq 3000\).
a := seq(evalf(log(2+k)),k=0..3000);
a = [ R(log(2+k)) for k in [0..3000] ]
Ecrire une fonction f1(a,x) qui évalue \(\sum a_k x^k\).
f1(a,x) := sum(a[k]*x^k, k=0..3000);
def f1(a,x):
return sum( a[k]*x^k for k in [0..3000] )
Mesurer le temps d’exécution de f1(a,evalf(pi)). Essayer d’améliorer
l’algorithme d’évaluation pour avoir la méthode la plus rapide.
On peut éviter de calculer indépendamment les puissances \(x^k\) en écrivant
1 2 3 4 5 6 7 8 9 10 | f2(a,x) := {
local s, k, xk;
s := 0; xk := 1;
for (k := 0; k < length(a); k++)
{
s := s + a[k] * xk;
xk := xk * x;
}
s;
}
|
et même diviser par 2 le nombre de multiplications en adoptant le schéma de Horner
f3(a,x) := {
local s, k;
s := 0;
for (k := length(a) - 1; k >= 0; k--)
{ s := s * x + a[k]; }
s;
}
On peut éviter de calculer indépendamment les puissances \(x^k\) en écrivant
def f2(a,x):
s, xk = 0, 1
for ak in a:
s += ak * xk
xk *= x
return s
et même diviser par 2 le nombre de multiplications en adoptant le schéma de Horner
def f3(a,x):
s = 0
for ak in a[::-1]:
s = s * x + ak
return s
Calculons simplement \(x^n\). Par définition, c’est le produit
faisant intervenir \(n-1\) multiplications. Mais si l’on coupe au milieu, on voit que l’on peut écrire selon la parité de \(n\)
où le terme \(x^k\) ne doit évidemment être calculé qu’une fois.
Écrire une fonction pow_naif(a,n) qui calcule \(a^n\) de manière
récursive naive.
pow_naif(a,n):={
if(n==0) return(1);
return( a*pow_naif(n-1) );
}
def pow_naif(a,n):
if n == 0:
return 1
else:
return a * pow_naif(a, n - 1)
É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).
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);
}
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
Écrire la fonction pow_iter(a,n) qui effectue le même calcul
de manière itérative.
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);
}
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
Exemple à retenir : quel est le coût du calcul des trois derniers chiffres de \(3^{123456789}\) ?
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}\)
de sorte qu’on peut écrire avec seulement 3 multiplications
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.
En appliquant récursivement cette idée, combien de multiplications élémentaires fait-on pour multiplier deux entiers de \(2^n\) chiffres ?
Quelle est la complexité de la multiplication de Karatsuba ?
Pour des entiers de \(n\) bits, on effectue une descente récursive de longueur \(\log_2{n}\), soit \(3^{\log_2 n}\) multiplications élémentaires (et de l’ordre de \(7^{\log_2n}\) additions que l’on négligera), donc la complexité est de \(O(n^{\log_2(3)})=O(n^{1.59})\).
Écrire une fonction fact(n) qui calcule la factorielle de \(n\).
def fact(n):
if n<=1: return 1
return n*fact(n-1)
def fact(n):
return prod( k for k in xrange(1,n) )
Avec une solution récursive
fact(n):= {
if(n==0) return(1);
return(n*fact(n-1));
}
ou bien de manière itérative:
fact(n):= {
local(r:=1);
for(k:=2;k<=n;k++) { r:= r*k; }
return(r);
}
Quelle est sa complexité binaire ?
Implanter la variante suivante, qui consiste à faire uniquement des multiplication entre opérandes de même taille en écrivant
Quelle est la complexité ? Comparer les temps d’exécution pour \(200000!\).
def fact_bin(n2,n1=1):
""" computes recursively n2!/n1! """
if n1 == n2: return n1
mid = (n2+n1)>>1
if mid == n1: return n1*n2
return fact_bin(n2,mid)*fact_bin(mid-1,n1)
On écrit une fonction qui calcule récursivement \(\frac{n_2!}{n_1!}\)
fact_split(n2,n1):= {
if(n2==n1) return(1);
if(n2==n1+1) return(n2);
local(mid:=iquo(n1+n2,2));
return( fact_split(n2,mid)*fact_split(mid,n1) );
}
x := Pi et y := 0.3.y := y * (2 - y * x).
Vers quelle valeur la suite converge-t-elle ?Pour calculer numériquement la racine carrée de \(a\), on définit la suite
É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.
Le nombre de décimales communes à deux nombres est le log en base 10 de leur différence relative.
1 2 3 4 5 6 7 8 9 10 11 12 13 | Digits:=200;
Newton(a) := {
local(b:=1);
local(c:=0);
local(k);
local(n);
for(k:=0;k<5;k++) {
c := b;
b := evalf((b+a/b)/2);
n := floor(1-logb(abs((c-b)/c),10));
if(n>0) print( left(string(c),n) );
};
};
|
Quelle est la vitesse de convergence de la suite ? Combien d’itérations faut-il pour obtenir un million de chiffres de \(\sqrt{5}\) ?
La précision double à chaque itération, la suite converge exponentiellement vite en nombre de chiffres corrects.
Il faut seulement \(\log_2(10^6)\approx20\) itérations pour obtenir un million de décimales de \(\sqrt{5}\).
Quelle est la théorie qui se cache derrière ces deux exemples ?
On considère la suite classique \(f_0=f_1=1\), \(f_{n+1}=f_n+f_{n-1}\).
Programmer le calcul récursif naïf de la suite. Quelle est sa complexité ? Calculer \(f_{34}\).
def fib_naif(n):
if n<2: return 1
return fib_naif(n-1)+fib_naif(n-2)
La complexité du calcul obéit à la même récurrence, si bien que le calcul de \(f_n\) est de complexité \(O(f_n)\), donc exponentielle en \(n\).
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}\).
Il s’agit de conserver à chaque étape les deux dernières valeurs pour ne pas les recalculer.
def fib_glis(n): ff = (1,1) for i in xrange(n-1): ff = (sum(ff),ff[0]) return ff[0] fib_glis(10^5)
À présent la complexité fait intervenir \(n\) additions de taille croissant linéairement vers \(n\), ce qui fait une complexité quadratique \(O(n^2)\).
En écrivant la récurrence linéaire
et l’expression de \(F_n=A^nF_0\), calculer à nouveau \(f_{10^5}\). Quelle est la complexité du calcul, pourquoi ?
def fib_mat(n):
A = matrix(2,2,[1,1,1,0])
F0 = vector([1,1])
return (A^n*F0)[0]
fib_mat(10^4)
fib_mat(n):={ local(A); A := matrix(2,2,[1,1,1,0]); return( (A^n)[0,0] ); };
La complexité est à présent de \(O(\log(n))\) multiplications matricielles \(2\times 2\), d’entiers dont la taille croît en \(O(n)\), d’où une complexité dominée par les derniers produits en \(O(n\log(n)\log\log n)\)
Comparer les temps de calcul de \(f_{2^{25}-1}\) et \(f_{2^{25}}\), commenter.
Calculer la suite des \(x^n \bmod x^2-x-1\). Que trouve-t-on ?
Rappeler comment on obtient l’expression algébrique exacte
et utilisez-la pour calculer \(f_n\).
phi := (1+sqrt(5))/2;
fib_alg(n) := simplify( (phi^(n+1)-(1-phi)^(n+1))/sqrt(5) );
Pour le logiciel, cela revient à effectuer les mêmes calculs qu’avec la matrice.
Quel est le nombre de chiffres de \(f_{f_{f_{f_{f_4}}}}\) ?