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:
 (defun print-bizarre-squares (N str)
   (let ((k 1) (l 10))
     (dotimes (i N 'done)
       (let ((j (* i i)))
          (when (<= l j)
            (incf k)
            (setq l (* 10 l)))
         ;; Here 10^(k-1) <= j < 10^k, j has k digits
         (if (evenp k) (test-if-bizarre i j  (expt 10 (/ k 2)) str))))))
 (defun test-if-bizarre (i j l str)
   (multiple-value-bind (a b) (floor (/ j l))
     (if (= i (+ a (* l b))) (format str  " ~7d      ~d ~%" i j))))
 (defparameter N (expt 10 7)) ; 10^7
(with-open-file (str "list-of-bizarre" :direction :output :if- exists :supersede)
   (time (print-bizarre-squares N str)))
 Le résultat est écrit dans "list-of-bizarre"  et le temps d'éxécution est imprimé.
Sur ma machine  (2993.03 BogoMIPS ) assez lente, j'obtiens:
 Evaluation took:
   7.894 seconds of real time
   7.891697 seconds of total run time (7.887671 user, 0.004026 system)
   [ Run times consist of 0.055 seconds GC time, and 7.837 seconds non- GC time. ]
   99.97% CPU
   11,815,133,039 processor cycles
   486,145,312 bytes consed
 Finalement le résultat obtenu est:
        9      81
       45      2025
       55      3025
       99      9801
      703      494209
      999      998001
     4950      24502500
     5050      25502500
     7272      52881984
     7777      60481729
     9999      99980001
    77778      6049417284
    82656      6832014336
    95121      9048004641
    99999      9999800001
   318682      101558217124
   329967      108878221089
   351352      123448227904
   356643      127194229449
   390313      152344237969
   461539      213018248521
   466830      217930248900
   499500      249500250000
   500500      250500250000
   533170      284270248900
   538461      289940248521
   609687      371718237969
   643357      413908229449
   648648      420744227904
   670033      448944221089
   681318      464194217124
   791505      626480165025
   812890      660790152100
   818181      669420148761
   851851      725650126201
   857143      734694122449
   961038      923594037444
   994708      989444005264
   999999      999998000001
  4444444      19753082469136
  4927941      24284602499481
  5072059      25725782499481
  5555556      30864202469136
  9372385      87841600588225
  9999999      99999980000001
 

Michel Talon me met la honte :)
Incrédule je relis le résultat : "7.891697 seconds of total run time", alors qu'il va à un ordre de grandeur plus loin que moi !
Et mon programme prenait presque 7 minutes sur mon Mac M2Max de course...
J'essaye de comprendre le programme lisp qui est une langue étrangère, je m'aide de ChatGPT, et je comprends la buse que je suis :)
Je testais tous les couples (n,p) où n et p sont < 10^7, alors qu'il suffit de tester tous les n<10^7 et de le mettre au carré... Bref, j'avais écrit bêtement un algo de complexité O(n^2) alors que celui de Talon est en O(n).
Une fois réécrit correctement, l'algo me prend 0.05s pour aller à 10^7. Du coup ça rend plus gourmand (le classique effet rebond : quand on optimise un machin, on a envie d'en consommer plus, vrai dans l'algorithmique comme dans la transition énergétique). Voici la suite de la liste (11 heures de calcul) dans laquelle on note plusieurs choses :
* il y en a bien plus entre 10^{2k+1} et 10^{2k+2} qu'entre 10^{2k} et 10^{2k+1}.
* Dans chaque séquence il n'y a rien en dessous 3.16 x 10^{n} car on les a éliminés artificiellement en imposant que le carré ait exactement (2n+2) chiffres, sans "0 muet" devant. Ce n'est peut-être pas nécessaire.
* En plus de ceux déjà repéré : 999 = 10^3-1, 500500, 499500 = 5*10^{2k+1} ± 5*10^k,
on en trouve plein de rigolos :
4444444, 36363636, 38883889, 61116111, 63636364, 74747475, 88888888, 432432432, 567567568, 3888938889, 4132841328, 4756047561, 6111061111, 7979797980, 8888888889, 9090909091, 9132791328, 9756097560, 44444444445, 55555555555, 324324324324, 425925425926, 590909590909, 593554593555, 604247604247, 675675675676, 695156695156, 730769730769, 733414733415, 740774077407, 749749749750, 750249750250, 804843804843, 831683168316, 909090909090, 925925925925, 980518980519 avec presque l'impression que la densité de rigolos augmente quand on monte :)
              9                       81
             45                     2025
             55                     3025
             99                     9801
            703                   494209
            999                   998001
           4950                 24502500
           5050                 25502500
           7272                 52881984
           7777                 60481729
           9999                 99980001
          77778               6049417284
          82656               6832014336
          95121               9048004641
          99999               9999800001
         318682             101558217124
         329967             108878221089
         351352             123448227904
         356643             127194229449
         390313             152344237969
         461539             213018248521
         466830             217930248900
         499500             249500250000
         500500             250500250000
         533170             284270248900
         538461             289940248521
         609687             371718237969
         643357             413908229449
         648648             420744227904
         670033             448944221089
         681318             464194217124
         791505             626480165025
         812890             660790152100
         818181             669420148761
         851851             725650126201
         857143             734694122449
         961038             923594037444
         994708             989444005264
         999999             999998000001
        4444444           19753082469136
        4927941           24284602499481
        5072059           25725782499481
        5555556           30864202469136
        9372385           87841600588225
        9999999           99999980000001
       36363636         1322314023140496
       38883889         1511956823764321
       44363341         1968106024682281
       44525548         1982524424700304
       49995000         2499500025000000
       50005000         2500500025000000
       55474452         3077414824700304
       55636659         3095437824682281
       61116111         3735179023764321
       63636364         4049586823140496
       69115816         4776996021345856
       74747475         5587185018875625
       75247525         5662190018625625
       80226927         6436359815863329
       80726977         6516844815558529
       83409436         6957134013838096
       86358636         7457814011780496
       88888888         7901234409876544
       91838088         8434234407495744
       94520547         8934133805179209
       99999999         9999999800000001
      332999667       110888778222110889
      432432432       186997808245434624
      567567568       322132944245434624
      667000333       444889444222110889
      765432099       585886298179545801
      999999999       999999998000000001
     3846956652     14799075482367049104
     3888938889     15123845682376554321
     4090859091     16735128102417346281
     4132841328     17080377442424803584
     4756047561     22619988402494048721
     4798029798     23021089942495920804
     4958067763     24582435942499824169
     4999950000     24999500002500000000
     5000050000     25000500002500000000
     5041932237     25421080682499824169
     5201970202     27060493982495920804
     5243952439     27499037182494048721
     5867158672     34423550882424803584
     5909140909     34917946282417346281
     6111061111     37345067902376554321
     6153043348     37859942442367049104
     7979797980     63677175801612080400
     8223700419     67629248581460775561
     8888888889     79012345680987654321
     9090909091     82644628100826446281
     9132791328     83407877440792003584
     9334811530     87138706300620940900
     9756097560     95181439600237953600
     9999999999     99999999980000000001
    44444444445   1975308642024691358025
    55555555555   3086419753024691358025
    75861343351   5754943415018311909201
    79694212204   6351167458816182537616
    99999999999   9999999999800000000001
   321678321679 103476942638218201379041
   324324324324 105186267348219138056976
   329037665671 108265785430220771880241
   331683668317 110014055828221669612489
   333299996667 111088887778222211108889
   335016335017 112235944728222780390289
   340659340659 116048786378224610554281
   346638010005 120157909980226480100025
   363473026840 132112641240231360385600
   395752395753 156619958744239132437009
   399086062453 159269685244239816377209
   403111739745 162499074720240612665025
   405757742391 164639345510241118396881
   406445406445 165197868420241247538025
   409090409091 167354962810241735446281
   422592759226 178584640150244008119076
   425925425926 181412468450244512957476
   428571428572 183673469388244897959184
   435930772564 190035638468245895134096
   437547100914 191447465518246099635396
   473160136527 223880514798249279621729
   480519480519 230898971158249620509361
   489995153362 240095250318249899903044
   496666833300 246677943300249988890000
   497354497354 247361496038249993001316
   499999500000 249999500000250000000000
   500000500000 250000500000250000000000
   502645502646 252652501330249993001316
   503333166700 253344276700249988890000
   510004846638 260104943594249899903044
   519480519481 269860010120249620509361
   526839863473 277560241744249279621729
   562452899086 316353263690246099635396
   564069227436 318174093340245895134096
   571428571428 326530612244244897959184
   574074574074 329561616598244512957476
   577407240774 333399121698244008119076
   590909590909 349174144628241735446281
   593554593555 352307055530241247538025
   594242257609 353123860728241118396881
   596888260255 356275595230240612665025
   600913937547 361097560338239816377209
   604247604247 365115167238239132437009
   636526973160 405166587560231360385600
   653361989995 426881889970226480100025
   659340659341 434730105060224610554281
   664983664983 442203274694222780390289
   666700003333 444488894444222211108889
   668316331683 446646719194221669612489
   670962334329 450190454088220771880241
   675675675676 456537618700219138056976
   678321678321 460120299280218201379041
   687797351164 473065196268214732154896
   695156695156 483242830820211913864336
   727436064069 529163227308198272836761
   730769730769 534024399408196745331361
   733414733415 537897171190195517562225
   740774077407 548746233758192027843649
   749749749750 562124687250187625062500
   750249750250 562874687750187375062500
   757609094242 573971539678183637554564
   760255096888 577987812344182267284544
   761871425238 580448068594181423356644
   766584766585 587652204360178932562225
   769230769230 591715976330177514792900
   804843804843 647773550194157070254649
   821678821678 675156085994146522735684
   824323824324 679509767348144814056976
   827657491024 685016922448142640568576
   831683168316 691696892460139986275856
   834329170962 696105165518138224005444
   835016835016 697253114760137763720256
   840658840659 706707286378133951554281
   843992507359 712323352478131669154881
   851164187797 724480474588126683713209
   895752895752 802373250248093379645504
   901731565098 813119815494088611749604
   906444906445 821642368420084802538025
   909090909090 826446280990082644628100
   918066581433 842846247944075220333489
   918566581933 843764565444074802016489
   925238261871 856065841230069172420641
   925925925925 857338820300068587105625
   928571928571 862245826530066326102041
   934901598268 874040998444060860599824
   980518980519 961417471158019101509361
   991024327657 982129218008008895109649
   992640656007 985335471958007305184049
   997353997354 994714996038002639001316
   999999999999 999999999998000000000001
--
F.J.