Programmation en Lua dans LaTeX : affichage de triplets pythagoriciens
par Damien Mégy latex lua lualatex maths pdftoppm poppler pdf png tikz pgf pgfplot csv
Table des matières
Introduction et objectif
Cet article est une étude de cas sur une utilisation concrète de Lua à l'intérieur d'un document LaTeX, à l'aide du moteur de rendu LuaTex au lieu de PdfTex.
L'objectif est d'obtenir l'image suivante. Dans cette image, chaque point est un triplet pythagoricien : un point de coordonnées (x,y) est noirci si $x^2+y^2$ est un carré. Par exemple, le point (3,4) est noirci, de même que (6,8) ou (5,12).
Motivation pour utiliser lua
- On programme directement en Lua, ce qui est plus simple et lisible qu’avec les macros TeX classiques.
- L'exécution est beaucoup plus rapide pour des calculs intensifs.
Structure du code Lua
- définition des constantes (jusqu'où tester les entiers x et y, échelle de l'image etc)
- boucle sur x et y, test pour savoir si $x^2+y^2$ est un carré parfait, si oui insertion dans un tableau contenant les triplets pythagoriciens.
- enfin, impression dans latex avec
tex.print. Il est conseillé de ne pas imprimer au fur et à mesure dans la boucle, ça fait partie des bonnes pratiques, pour séparer le calcul mathématique avec Lua de l'affichage avec LaTeX. - remarque : le test pour savoir si un couple (x,y) est le début d'un triplet pythagoricien se fait à l'aide d'une fonction
is_square(n)qui renvoie un booléen. L'implémentation de cette fonction peut varier, mais dans une première version, on vérifie si $\sqrt{x^2+y^2}$ est un entier en comparant ce réel à sa partie entière.
Première implémentation
Le code complet
\documentclass[tikz]{standalone}
\usepackage{luacode}
\begin{document}
\begin{tikzpicture}
\begin{luacode*}
local N = 1500
local M = 4000
local scale = 0.004
local POINT_RADIUS = 0.025
local function is_square(n)
local r = math.sqrt(n)
if r ~= math.floor(r) then return false end
return true
end
local function draw_point(x,y)
return string.format(
"\\fill[black] (%.4f,%.4f) circle (%.4f);",
x,y,POINT_RADIUS
)
end
local linesToPrint = {}
for x = 1, M do
for y = 1, N do
if is_square(x*x + y*y) then
table.insert(linesToPrint, draw_point(x*scale, y*scale))
end
end
end
tex.print(table.concat(linesToPrint," "))
\end{luacode*}
\end{tikzpicture}
\end{document}
Analyse du code : terminaison
L'algorithme termine puisqu'il s'agit de deux boucles for imbriquées : pas de while, pas de goto.
Analyse du code : correction
Le pseudo-code est correct. On peut toutefois se poser la question de la correction en pratique : les entiers et les flottants ne se comportent parfois pas comme prévu, et la fonction is_square() devrait au moins provoquer une petite méfiance. Serait-il posible qu'elle renvoie un résultat incorrect, par exemple si l'entier est trop grand, ou que la racine carrée est mal arrondie ?
On pourrait avoir envie de coder une version numériquement plus stable du test de carré :
local function is_square(n)
local r = math.floor(math.sqrt(n) + 0.5)
return r*r == n
end
Cela dit, notre code ne s'approche absolument pas des bornes où il pourrait y avoir des problèmes de représentation de grands entiers. De toute façon, nous allons par la suite optimiser bien plus cette étape.
Analyse du code : complexité
Le test de carré est appelé dans chaque tour de boucle. Même si l'on suppose que son coût est en O(1), la complexité sera en O(N+M).
Mesure du temps de calcul
Au début du script :
start = os.clock()
À la fin du calcul des triplets, un premier affichage du temps dans la console:
texio.write("Triplets calculés. Temps écoulé : " .. (os.clock() - start))
Et même chose à la fin du fichier tex, pour mesurer le temps qu'a mis tikz à tracer le dessin.
Bilan : c'est le dessin des points avec TikZ qui prend du temps, mais l'algorithme de calcul des triplets pythagoriciens pourrait sans doute être amélioré. On utilise math.sqrt et math.floor MxN fois, donc des millions de fois. On constate aussi que certains entiers sont testés plusieurs fois.
Deuxième implémentation : optimisation en précalculant les carrés
\documentclass[tikz]{standalone}
\usepackage{luacode}
\begin{document}
\begin{tikzpicture}
\begin{luacode*}
local N = 1500
local M = 4000
local scale = 0.004
local POINT_RADIUS = 0.025
local squares = {}
local max = math.floor(math.sqrt(M*M + N*N))
for i = 1,max do
squares[i*i] = true
end
local function draw_point(x,y)
return string.format(
"\\fill[black] (%.4f,%.4f) circle (%.4f);",
x,y,POINT_RADIUS
)
end
local linesToPrint = {}
for x = 1, M do
for y = 1, N do
local s = x*x + y*y
if squares[s] then
table.insert(linesToPrint,draw_point(x*scale,y*scale))
end
end
end
tex.print(table.concat(linesToPrint," "))
\end{luacode*}
\end{tikzpicture}
\end{document}
Bilan : les triplets sont calculés et la table linesToPrint est construite deux fois plus vite.
On pourrait optimiser encore plus cette étape, en utilisant la symétrie en x et y, mais l'étape la plus lente reste toutefois le dessin des points avec Tikz. Elle prend de l'ordre de dix fois plus de temps que le calcul des triplets.
Troisième impémentation : accélération du dessin avec pgfplots
Le précalcul des carrés permet donc de réduire le calcul, mais la compilation reste lente à cause de Tikz qui doit dessiner et remplir des milliers de points.
Plutôt que de dessiner les points avec tikz, on peut utiliser pgfplots. On peut aussi enregistrer les triplets pythagoriciens dans un fichier externe, puis l'importer avec pgfplots, ça permet d'avoir le fichier avec les triplets, ce qui peut toujours servir.
Le package pgfplot accélère de 50% le tracé de la figure.
\documentclass{standalone}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{luacode}
\begin{document}
\begin{luacode*}
local N = 4000
local M = 3000
local squares = {}
local max = math.floor(math.sqrt(M*M + N*N))
for i = 1,max do
squares[i*i] = true
end
local file = io.open("points.dat", "w")
for x = 1, M do
for y = 1, N do
local s = x*x + y*y
if squares[s] then
file:write(string.format("%d %d\n", x, y))
end
end
end
file:close()
\end{luacode*}
\begin{tikzpicture}
\begin{axis}[only marks,width=12cm,height=16cm]
\addplot[black, mark=*, mark size=.5] file {points.dat};
\end{axis}
\end{tikzpicture}
\end{document}
Remarque : utiliser mark=square* (sans pluriel) permet de gagner un peu, tikz dessinant plus vite un rectangle qu'un cercle... Ceci dessinera donc des pixels carrés.
Annexe : conversion du pdf en png (en ligne de commande)
Dans le terminal, on peut faire par exemple :
pdftoppm -png input.pdf output
(Il faut installer les outils Poppler pour cela. Il y a aussi d'autres utilitaires, et un simple export avec l'application Aperçu sur macOS peut suffire.)