Principes algorithmiques¶
Quelques idées à garder en tête, illustrées ici avec des exemples simples qui sont aussi prétexte à travailler un peu avec Pari/GP.
Ne pas recalculer¶
évaluation de polynôme (version 1)¶
On évalue \(P(x)=\sum v_k x^k\)
\p200 default(timer, 1) v = vector(3000,k,random(1.)); x = .9
sum(k=1,3000,v[k]*x^k)
on passe son temps à recalculer les \(x^k\), on ferait mieux de calculer de proche en proche \(x^k=x^{k-1}x\)
xk=1;sum(k=1,3000,xk*=x;v[k]*xk)
exponentiation modulaire¶
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 !
d’où l’écriture suivante
pow(x,n) = if(n==0,1,if(n%2,x,1)*pow(x,n\2)^2)
Remarquons que l’on peut aussi mettre le carré à l’intérieur, ce qui donne une autre formule (qui correspond à la version itérative classique)
pow(x,n) = if(n==0,1,if(n%2,x,1)*pow(x^2,n\2))
Reformuler¶
évaluation de Hörner¶
On reprend l’exemple précédent
\p200 v = vector(3000,k,random(1.)); x = .9
s = v[3000]; for(k=1,3000-1,s = x*s+v[3000-k]); s*x
multiplication de Karatsuba¶
de sorte qu’on peut écrire avec seulement 3 multiplications
Partons d’une multiplications entre grands nombres
default(timer, 1) x = random(10^100000); y = random(10^100000); x*y;
avec des nombres qui ont 2 fois plus de chiffres, on devrait mettre 4 fois plus de temps. On constate que ce n’est pas le cas
x = random(10^200000); y = random(10^200000); x*y;
Choisir l’ordre des étapes¶
calcul de \(n!\)¶
p(a,b)=prod(k=a,b,k) p(1,20000);
p(1,10000)*p(10001,20000);
p(1,5000)*p(5001,10000)*p(10001,15000)*p(15001,20000);
On peut continuer, récursivement
p(a,b)=if(b-a<20,prod(k=a,b,k),p(a,(a+b)\2)*p((a+b)\2+1,b)) p(1,20000);
Faire des mathématiques¶
exp(-x) via exp(x)¶
x = -20*Pi x^250/250! sum(k=0,250,x^k/k!)
x = 20*Pi 1/sum(k=0,200,x^k/k!)
exp(-20*Pi)
on peut toujours gagner en réutilisant les termes
x = 20*Pi xk=1;1/(1+sum(k=1,200,xk*=x/k;xk))
et même faire du Hörner, mais ici ça ne gagne rien
s=1;for(k=0,199,s=1+x/(200-k)*s);1/s
changer de formule¶
Exemple, la série d’Eisenstein \(G_4(τ)\)
\(G_2(τ) = \sum_{c,d}\frac1{(cτ+d)^2}\)
\(G_2(τ) = 2ζ(2)+\sum_{c,d}\frac1{(cτ+d)^2(cτ+d+1)}\)
\(G_2(τ) = 2ζ(2)-8π^2\sum_n \sigma(n)q^n\), \(q=e^{2iπτ}\)
\(\frac{\d}{\dτ}\log(\eta(τ)) = \frac{iπ}{24\zeta(2)} G_2(τ)\) pour \(\eta(τ)=q^{1/24}\prod(1-q^n)\)
inverser l’AGM : \(G_2\to τ\)
Se ramener à des problèmes classiques¶
diviser via des multiplications¶
default(timer, 0) \p 75 1/Pi
On part d’une approximation grossière du résultat
x = .3
et on répète plusieurs fois l’itération suivante
x = x*(2-x*Pi)
équations¶
Note
Combien de carreaux ?
Un roi vivait dans un palais magnifique, dont la cour carrée était entièrement pavée de carreaux d’or. Il avait 991 fils, et fit construire pour chacun d’eux un palais semblable au sien, mais plus petit.
Au moment de mourir, il légua à chacun le même nombre de carreaux, ce qui permit à chacun de paver exactement la cour de son palais. Il ne resta plus qu’un carreau d’or, que le roi laissa à son épouse en souvenir de lui.
e = quadunit(4*991)
norm(e)
379516400906811930638014896080^2 - 991 * 12055735790331359447442538767^2