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

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
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....
Voici le résultat dans list-of-bizarre
    1          9 81
    2         45 2025
    3         55 3025
    4         99 9801
    5        703 494209
    6        999 998001
    7       4950 24502500
    8       5050 25502500
    9       7272 52881984
   10       7777 60481729
   11       9999 99980001
   12      77778 6049417284
   13      82656 6832014336
   14      95121 9048004641
   15      99999 9999800001
   16     318682 101558217124
   17     329967 108878221089
   18     351352 123448227904
   19     356643 127194229449
   20     390313 152344237969
   21     461539 213018248521
   22     466830 217930248900
   23     499500 249500250000
   24     500500 250500250000
   25     533170 284270248900
   26     538461 289940248521
   27     609687 371718237969
   28     643357 413908229449
   29     648648 420744227904
   30     670033 448944221089
   31     681318 464194217124
   32     791505 626480165025
   33     812890 660790152100
   34     818181 669420148761
   35     851851 725650126201
   36     857143 734694122449
   37     961038 923594037444
   38     994708 989444005264
   39     999999 999998000001
   40    4444444 19753082469136
   41    4927941 24284602499481
   42    5072059 25725782499481
   43    5555556 30864202469136
   44    9372385 87841600588225
   45    9999999 99999980000001
   46   36363636 1322314023140496
   47   38883889 1511956823764321
   48   44363341 1968106024682281
   49   44525548 1982524424700304
   50   49995000 2499500025000000
   51   50005000 2500500025000000
   52   55474452 3077414824700304
   53   55636659 3095437824682281
   54   61116111 3735179023764321
   55   63636364 4049586823140496
   56   69115816 4776996021345856
   57   74747475 5587185018875625
   58   75247525 5662190018625625
   59   80226927 6436359815863329
   60   80726977 6516844815558529
   61   83409436 6957134013838096
   62   86358636 7457814011780496
   63   88888888 7901234409876544
   64   91838088 8434234407495744
   65   94520547 8934133805179209
   66   99999999 9999999800000001
   67  332999667 110888778222110889
   68  432432432 186997808245434624
   69  567567568 322132944245434624
   70  667000333 444889444222110889
   71  765432099 585886298179545801
   72  999999999 999999998000000001
--
Michel Talon