Re: Le calcul de la racine carré... pour des nuls :)

Le 10/11/2024 à 03:40, Samuel Devulder a écrit :

----8<-------------------------------------
i = 0
n = 1
p = 1
q = 10
repeat
   n = n + 1
   if n>=q then
     p = q
     q = q*10
   end
   m = n*n
   a = math.floor(m / q)
   b = math.floor(m % q)
   if a+b==n and a>=p then
     i = i + 1
     print(i, n, m)
   end
until n > 1E7
----8<-------------------------------------

Très intéressant. La version lisp du même programme , avec les mêmes variables,
(il s'exécute dans le même temps que ma version), est:
(let ((i 0)(p 1)(q 10) m )
   (do ((n 2 (incf n))) ((> n (expt 10 7)) 'DONE)
     (if (>= n q)
(progn (setq p q)
       (setq q (* 10 q))))
     (setq m (* n n))
     (multiple-value-bind (a b) (floor (/ m q))
       (if (and (= n (+ a (* q b))) (>= a p))
  (progn (incf i)
(format t "~d ~d ~d ~%" i n m))))))
La seule différence est que, à ma connaissance, on ne dispose pas
de m%q si bien qu'on doit utiliser (floor (/ m q)) qui produit le
quotient plus le reste, donc on doit utiliser multiple-value-bind
pour récupérer les deux valeurs et remultiplier le reste par q
pour obtenir m%q.  Or en lisp il y a des tas de types de données,
integer, rational, float, etc et floor s'adapte à tous ces types.
La documentation dit que:
"
All of these functions perform type conversion operations on
numbers.
The remainder is an integer if both x and y are integers, is a
rational if both x and y are rationals, and is a float if either
x or y is a float.
"
Autrement dit floor est une fonction très compliquée qui prend
beaucoup de temps à l'exécution. De fait utilisant le profiler de
lisp on voit que presque tout le temps d'exécution est à cet
endroit.  Clairement lua est beaucoup plus efficace ici, et doit
utiliser des fonctions spécifiques pour les entiers. De plus ta
version de lua doit utiliser lua-jit pour tourner aussi vite.
J'ai essayé de spécifier le type des variables et de demander une
optimisation maximale au compilateur, ça ne change rien. En fait
ça ne marche pas très bien avec les entiers, par contre ça marche
aisément avec des floats, et on obtient facilement des
performances proches de celles du C.
En ce qui concerne la lisibilité, je suis bien d'accord avec toi,
la syntaxe type python ou, ce qui est à peu prés pareil lua, est
ce qu'il y a de mieux. Néanmoins, si tu compares les programmes
lisp et lua tu vois que c'est extrêmement similaire, aux
parenthèses prés. Avec un peu d'habitude, on ne voit presque plus
ces parenthèses. L'autre grande différence est la notation
préfixe, ou l'opération apparaît en premier après la parenthèse
ouvrante, (/ m q) au lieu de m/q
(>= a p) au lieu de a >= p, etc.
Ca rend l'interprétation du code extrêmement simple pour lisp.
Devant une "forme" (A B C) on doit d'abord évaluer B et C puis
appliquer l'opérateur A à ces résultats, et ceci récursivement,
bien sûr.
(> n (expt 10 7))
on évalue n, on évalue (expt 10 7), 10 -> 10
7 -> 7 on applique expt -> 10^7 et enfin on évalue >, est-ce que
n > 10^7 ?  Avec les parenthèses on a une uniformité parfaite,
aucun cas particulier, aucune ambiguité.  Si on fait un
copier-coller, aucun problème de Tab et Space etc.
Finalement comme tu sais la grande spécificité de lisp est
l'existence des macros, qui fait qu'il n'y a pas rééllement de
syntaxe, à part les choses les plus basiques, puisqu'on peut
créer sa propre syntaxe à volonté.  Par exemple ton repeat
...until est ici la boucle do
(do ((n 2 (incf n))) ((> n (expt 10 7)) 'DONE) ....  Ceci est en
fait une macro: dans laquelle ((n 2 (incf n))) est une liste de
variables à initialiser et incrémenter, on pourrait avoir ((n
1 (incf n))(m 2 (incf m))), la parenthèse extérieure sert à
grouper ces déclarations et aussi au mécanisme de macro de
repérer son premier argument, d'ailleurs heureusement que
l'expansion de macros se fait sans évaluation, sinon
(n 1 (incf n))
poserait problème , n n'étant pas une fonction. Le deuxième
argument de la macro do est la condition de terminaison
((> n (expt 10 7)) 'DONE)
qui est en fait un liste de cette condition
et de la valeur à retourner, ici, une fantaisie, le symbole
'DONE, où le ' empêche l'évaluation. En bref ceci pour expliquer
l'utilité fondamentale des parenthèses.
Finalement la déclaration des variables par let etc. n'est pas
forcément une mauvaise chose, ça permet de s'assurer que ce ne
sont pas des variables globales comme le N de (defparameter N)
donc le compilateur les traite avec plus d'efficacité, elles ont
une visibilité purement lexicale et sont allouées sur la pile, le
compilateur sait exactement ce qui les modifie, et optimise en
conséquence.  On a la même idée dans le langage rust.
--
Michel Talon