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

Le 11/11/2024 à 23:13, Michel Talon a écrit :

Le 09/11/2024 à 19:39, Michel Talon a écrit :

Et bien, pour passer de langages récents à un langage très ancien voici une solution avec Common Lisp  (en fait sbcl)  qui lui aussi a l'avantage d'un programme non typé (sauf si on déclare le type des variables) avec gestion automatique de la mémoire, possibilité de programmer pas à pas à la console, comme python ou lua, mais en outre est compilé automatiquement (avec sbcl)
ce qui donne une vitesse d'exécution raisonnable, contrairement à python par exemple.
Voici le programme: .....

 Suite aux discussions voici une version améliorée du même algorithme, qui est plus efficace que celui de Samuel, je crois:
 (defun print-bizarre-squares (N str)
   (let ((k 1) (l 10) (m 1) (p 0))
     (declare (word k l m p)
          (optimize (speed 3) (safety 0)))
     (dotimes (i N 'done)
       (declare (word i))
       (let ((j (* i i)))
     (declare (word j))
     (when (<= l j)
       (incf k)
       (setq l (* 10 l))  ; 10^k
       (if (evenp k) (setq m (* 10 m)))) ; 10^(k/2) for k even
     ;; Here 10^(k-1) <= j < 10^k, j has k digits
     (if (and (evenp k)
          (= i (+ (floor j m) (mod j m))))  ; computed only for k even
         (progn  (incf p)
             (format str  "~4d ~10d ~d ~%" p i j)))))))
  (defparameter N (expt 10 9)) ; 10^9
(with-open-file (str "list-of-bizarre" :direction :output :if- exists :supersede)
   (time (print-bizarre-squares N str)))
  Sans aucune déclaration   il tourne en 0.8s pour N=10^7  comparé aux 8s précédemment indiquées, soit un facteur 10 grâce à l'amélioration de l'usage de floor et mod. Avec les déclarations ci-dessus il tourne en 0.4s J'ai déclaré toutes les variables en type word, c'est à dire (unsigned-int 64), ce qui est sbcl spécifique.
La version sans déclaration tourne quand même  1.7/0.8 soit 2 fois plus vite que la version lua, ce qui est pas mal pour lua, je suppose que python serait beaucoup plus lent (j'ai fait tourner https:// onecompiler.com/lua/42xp2gahe sur ma machine, en 1.7s).
 Du coup j'ai fait tourner le programme avec N=10^9
Ce qui donne:
Evaluation took:
   41.985 seconds of real time
   41.969659 seconds of total run time (41.957832 user, 0.011827 system)
   99.96% CPU
   62,838,884,786 processor cycles
   0 bytes consed

C'est bien.
Mon programme fortran de 15 lignes tourne en 0.50s (0.489 CPU) pour 10^9 :)
Pour aller plus vite il faut faire une boucle sur k=1,9 et une seconde imbriquée entre \sqrt{10}*10^k et 10^{k+1}-1. On gagne automatiquement au moins un facteur 0.684=1-\sqrt{10}/10. Ca remplace le test sur la parité de k et les calculs qui concernent l.

Noter qu'aucun espace mémoire n'a été alloué dynamiquement sur le tas!
Je pense qu'on est là vers des performances proches du C. Peut être ça peut convaincre certains que les très vieux langages, comme Common Lisp (ou Fortran) ont des atouts non négligeables....

En effet.
--
F.J.