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

Le 10/11/2024 à 12:25, Michel Talon a écrit :

 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.

En fait j'avais mal compris la documentation lisp de floor, et oublié qu'il y a une fonction mod, si bien que j'ai réécrit le programme avec ces fonctions et des déclarations appropriées, et j'ai enfin un temps d'exécution correct, tout en étant plus proche de ton programme:
(time
  (let ((i 0)(p 1)(q 10)(m 1)(a 1)(b 1))
    (declare (fixnum i p q m a b)
    (optimize (speed 3)(safety 0)))
    (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))
      (setq a (floor m q))
      (setq b (mod m q))
      (if (and (= n (+ a b))
      (>= a p))
(progn (incf i)
(format t "~d ~d ~d ~%" i n m)))))))

Ce qui donne:

1 9 81
2 45 2025
3 55 3025
4 99 9801
...
44 9372385 87841600588225
45 9999999 99999980000001
Evaluation took:
   0.643 seconds of real time
   0.641880 seconds of total run time (0.641880 user, 0.000000 system)
   99.84% CPU
   961,544,359 processor cycles
   32,736 bytes consed
En particulier il y a infiniment moins de mémoire allouée au calcul (bytes consed ...).
Du coup je suis monté jusqu'à  10^9  le calcul prend 67s.  les derniers résultats sont:
65 94520547 8934133805179209
66 99999999 9999999800000001
67 332999667 110888778222110889
68 432432432 186997808245434624
69 567567568 322132944245434624
70 667000333 444889444222110889
71 765432099 585886298179545801
72 999999999 999999998000000001
Au delà on dépasse la taille d'un fixnum
most-positive-fixnum  -> 4611686018427387903
donc il faut remplacer la déclaration fixnum par integer ce qui permet à lisp de passer aux bigint en cas de besoin, mais avec la perte de performance correspondante.
Ceci illustre qu'on peut typer les variables, le système détecte alors les erreurs de type, et dans ce cas le compilateur peut produire du code proche de C, sinon le système se débrouille pour produire des rationnels, par exemple on peut avoir 3/5
et calculer   (+ 3/10 21/15) -> 17/10 , ce qui suppose des calculs de pgcd, ou bien le résultat peut contenir des nombres gigantesques (big integers) tout ça de façon automatique, mais ça a un prix. Bref il y a le meilleur des deux mondes, à la fois pas de typage du tout, et si on le veut un typage fort.
--
Michel Talon