Voici le Pb sur lequel je suis tombé.
En explorant les tutoriaux je suis tombé sur [TUTO]-Calcul des nombres premier par flaith
Comme j’ai voulu l’optimiser j’ai eu la surprise de voir des temps différents suivant l’ordre dans lequel on exécute les subroutines.
L’optimisation porte sur deux remarques :
1) il n’est pas nécessaire de tester les diviseurs sur toute l’étendu mais de le limiter à sqr(nombre_total) c'est-à-dire à la racine carré
du max de l’étendu.
2) il n’est pas nécessaire aussi de tester les nombres pairs ne testons que les nombres impairs en ajoutant à la liste 1 et 2 qui sont premiers.
Voici les trois subroutines :
1) La sub1 l ’originale.
2) La sub2 limitant les diviseurs à la racine carré de nombre_total.
3) La sub3 qui en plus de la sub2 ne teste que les nombres impairs.
QUESTION ;
La sub3 la plus optimisée prend dans certain ordre plus de temps que la sub2.
Pourquoi l’ordre d’ exécution des subroutines donne pour chacune des subroutines des temps différents ?
Code : Tout sélectionner
; Note: le débogueur doit être activé
; Affiche la liste des nombres premier allant de 1 à 'nombre_total'
ProcedureDLL.q nbcs()
!RDTSC
ProcedureReturn
EndProcedure
nbprem1=0
nombre_total=1000
nblim=Sqr(nombre_total)
Gosub sub1
Gosub sub2
Gosub sub3
Debug "************** résultat ordre sub1 sub2 sub3"
Gosub subtot
; ***** en inversant l'exécution de sub2 et sub3 on obtient des résutats différents
Gosub sub1
Gosub sub3
Gosub sub2
Debug "************** résultat ordre sub1 sub3 sub2"
Gosub subtot
Gosub sub3
Gosub sub2
Gosub sub1
Debug "************** résultat ordre sub3 sub2 sub1"
Gosub subtot
; ***** en ne prenant que sub2 et sub3
Gosub sub3
Gosub sub2
Debug "************** résultat ordre sub3 sub2"
Gosub subtot
Gosub sub2
Gosub sub3
Debug "************** résultat ordre sub2 sub3"
Gosub subtot
End
; *************************************************** SUB1 *******************************************************************
sub1:
nbprem1=0
d1.q=nbcs()
E1.q=ElapsedMilliseconds()
; *************** algo d'origine trouvé sur les tutoriaux ****************
Debug "Liste des nombres premier allant de 1 à "+Str(nombre_total)+" algo 1"
For nbprem=1 To nombre_total
nb_division=0
For x=1 To nombre_total
If nbprem%x=0 ;Résultat du reste de la division (modulo) = 0
nb_division+1 ;ajoute 1 au nombre de division actuel
EndIf
Next
If nb_division=2 ;Divisible par 1 et par lui même (donc 2 fois)
Debug Str(nbprem) ;Alors c'est un nombre premier
nbprem1+1
EndIf
Next
r1.q=nbcs()-d1
Re1=ElapsedMilliseconds()-E1
Return
;**************************************************** SUB3 ********************************************************************
sub3:
; *************** algo en limitant la recherche des diviseurs à sqr(nombre_total) en sautant de 2 en 2 ****************
Debug "Liste des nombres premier allant de 1 à "+Str(nombre_total)+" algo 3"
Debug 1
Debug 2
nbprem3=2
E3.q=ElapsedMilliseconds()
D3.Q=nbcs()
For nbprem=3 To nombre_total Step 2
nb_division=0
For x=1 To nblim
If nbprem%x=0 ;Résultat du reste de la division (modulo) = 0
nb_division+1 ;ajoute 1 au nombre de division actuel
EndIf
Next
If nb_division=2 And nbprem<nblim ;Divisible par 1 et par lui même (donc 2 fois)
Debug Str(nbprem) ;Alors c'est un nombre premier
nbprem3+1
ElseIf nb_division=1 ;Divisible par 1 et c'est tout (donc 1 fois)
Debug Str(nbprem) ;Alors c'est un nombre premier
nbprem3+1
EndIf
Next
r3.q=nbcs()-d3
re3.q=ElapsedMilliseconds()-E3
Return
; ******************************************************* SUB2 ***************************************************************
sub2:
;*******************************************************************************************************************************
; *************** algo en limitant la recherche des diviseurs à sqr(nombre_total) ****************
nbprem2=0
E2.q=ElapsedMilliseconds()
D2.Q=nbcs()
Debug "Liste des nombres premier allant de 1 à "+Str(nombre_total)+" algo 2"
For nbprem=1 To nombre_total
nb_division=0
For x=1 To nblim
If nbprem%x=0 ;Résultat du reste de la division (modulo) = 0
nb_division+1 ;ajoute 1 au nombre de division actuel
EndIf
Next
If nb_division=2 And nbprem<nblim ;Divisible par 1 et par lui même (donc 2 fois)
Debug Str(nbprem) ;Alors c'est un nombre premier
nbprem2+1
ElseIf nb_division=1 ;Divisible par 1 et c'est tout (donc 1 fois)
Debug Str(nbprem) ;Alors c'est un nombre premier
nbprem2+1
EndIf
Next
r2.q=nbcs()-d2
re2.q=ElapsedMilliseconds()-E2
Return
;**************************************** sub tot ***************************************************************************************
subtot:
Debug "T1="+Str(r1)
Debug "nbprem1="+Str(nbprem1)
Debug "T2="+Str(r2)
Debug "nbprem2="+Str(nbprem2)
Debug "T3="+Str(r3)
Debug "nbprem3="+Str(nbprem3)
Debug "re1="+Str(re1)
Debug "re2="+Str(re2)
Debug "re3="+Str(re3)
Debug "diff T1-T2="+Str(r1-R2)
Debug "diff T2-T3="+Str(r2-R3)
Return
