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

Le 11/11/2024 à 23:31, efji a écrit :

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

>
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.

Note qu'en changeant simplement integer*8 en integer*16, pour pouvoir monter plus haut en N, je passe de 0.5s à 11.97s pour la même valeur de N. Un joli facteur 24.
La boucle la plus interne est on ne peut plus simple :
         do i=n0,N-1
           j = i*i
           ia = j / n
           ib = mod(j, n)
           if (i .eq. ia + ib) write(*,'(i14,i25)') i,j
         enddo
Une multiplication, une division, un modulo et un test.
Il doit y avoir moyen de se passer des entiers 128 bits qui sont visiblement mal implémentés et de les remplacer par des tableaux d'entiers 64 bits de taille 2. Il faudrait reprogrammer les 4 opérations ci-dessus :
* multiplication : faire comme à l'école primaire mais pour un nombre à 2 "chiffres" de 64 bits, avec retenue.
* n=10^k -> division par n facile
* modulo n facile aussi
* test d'égalité: encore plus facile (test sur le 2eme élément du tableau puis - très rarement - sur le 1er).
Au final il est peu probable que tout cela coûte 24 fois plus cher que les mêmes calculs sur un seul entier.
--
F.J.