Calcul et représentation graphique avec TeX, xint et PSTricks
La « suite diatomique de Stern » peut être définie par la récurrence :
pour n>0: a(2n) = a(n), a(2n+1) = a(n) + a(n+1) avec a(0)=0, a(1)=1.
On utilise aussi parfois la notation fusc(n).
Les références sur cette suite sont nombreuses, on peut citer :
et l'article de Jean-Paul Delahaye dans la revue ``Pour la Science'' - n° 420 - Octobre 2012, qu'il met à la disposition des lecteurs :
Jean-François Burnol s'est attaché à développer plusieurs méthodes codées en TeX cherchant à élaborer la plus efficace et la plus rapide.
Afin d'avoir une référence, voici le résultat obtenu en calculant pour $n=2^{13}-1$ avec mathematica avec le code suivant :
start = SessionTime[];
ListPlot[fusc /@ Range[8191], AxesLabel → {n, HoldForm[fusc[n]]}]
Sow[SessionTime[] - start]
500.8 secondes Donc un peu plus de 8 min.
Pour la compilation du fichier, il faut décomposer la durée en fonction des processus.
Sur un Mac à 2.8 Ghz, pour les 6 pages du document :
$ time latex Suite-Stern-PSTricks-xint
real 0m1.054s
user 0m0.934s
sys 0m0.059s
$ time dvips Suite-Stern-PSTricks-xint.dvi
real 0m0.340s
user 0m0.301s
sys 0m0.022s
$ time ps2pdf Suite-Stern-PSTricks-xint.ps
real 0m6.435s
user 0m6.342s
sys 0m0.041s
C'est époustouflant, incroyable n'est-ce pas !
Le document comprend aussi un calcul en postscript, pas aussi rapide que ceux proposés par Jean-François, mais qui n'est pas mal non plus.
Voici schématiquement les 4 méthodes codées en TeX, écrites par Jean-François Burnol et qui feront le bonheur de tous les utilisateurs de TeX, LaTeX, XeLaTeX et des amateurs de programmation en TeX !
1. Calcul avec TeX de base et \numexpr
2. Approche avec xintexpr mais problèmes de saturation de la mémoire de TeX, seconde approche utilisant directement des macros de xinttools pour éviter ce problème.
3. Utilisation de TeX avec un stockage plus rapide des données numériques en utilisant les paramètres \fontdimen d’une police de caractère fictive, méthode 4 fois plus rapide que la première.
4. Utilisation de \listplot avec la nouvelle primitive \expanded : c'est la méthode la plus rapide et peut-être la plus élégante ? En voici le début, vous lirez la suite dans le document.
« On peut engendrer la suite de STERN (après le zéro initial) par blocs de longueurs des puissances de deux : 1(1) engendre 12(1) qui engendre 1323(1) qui engendre 14352534(1), chaque série provenant de la précédente en intercalant les sommes d’entiers successifs, et les « 1 » terminaux sont utilisés pour engendrer, mais oubliés lorsque l’on fait la concaténation, pour obtenir donc ici les valeurs de fusc(n), pour n=1..15 : 112132314352534...
Il est facile de coder ceci avec des \edef mais ceci empêcherait l’expandabilité. La nouvelle primitive \expanded révolutionne le codage expandable en TeX, comme nous allons l’illustrer maintenant en allant jusque fusc(8191). [...] »
Pour terminer, Jean-François donne le code qui calcule en une fraction de seconde les 50000 valeurs de fusc(1) à fusc(50000) puis les exporte dans un fichier.
Les fichiers sont disponibles soit ici :
soit sur le site officiel de xint-ploexpr :
Images extraites de la documentation :
Aucun commentaire:
Enregistrer un commentaire