Bonjour,


Voilà je cherche à comparer le temps d'execution pour comparer 2 méthodes qui recherchent le pgcd de 2 nombres.

J'ai décidé d'utiliser la fonction clock (), je sais que cette fonction donne une valeur du temps approximative mais vu que je cherche le pgcd de int_max et int_max - 1 le temps d'exécution est important (environ 30 secondes pour la première méthode).

Le problème est le suivant :

PGCD = 1 duree methode 1 : 30839000000 ns
PGCD = 1 duree methode 2 : 0 ns

Process returned 0 (0x0) execution time : 30.886 s
Press any key to continue.

le temps d'execution de la 2ème méthode est nulle, et j'arrive pas à savoir si c'est parceque :

- la deuxième méthode est tellement rapide que clock arrive pas à calculer son temps d'éxecution.
- Il y a un souci au niveau du code.




Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* --------------------------------------------------------------------------
   Fonction : Comparer la complexite temporelle de 2 methode de calcul pour le
              PGCD
   -------------------------------------------------------------------------- */
 
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>
 
/* --------------------------------------------------------------------------
   permuter ()
   --------------------------------------------------------------------------
   Role : Permute 2 nombre (long)
   -------------------------------------------------------------------------- */
void permuter (long *x, long *y)
{
   long tmp = *x;
   *x = *y;
   *y = tmp;
}
 
/* --------------------------------------------------------------------------
   trouver_pgcd_methode_1 ()
   --------------------------------------------------------------------------
   Role : Retourne le PGCD de 2 nombres par la méthode de decrementation
   -------------------------------------------------------------------------- */
long trouver_pgcd_methode_1 (long x, long y)
{
   long pgcd;
 
   if (x < y)
   {
      permuter (&x, &y);
   }
 
   if (y == 0)
   {
      pgcd = x;
   }
   else
   {
      pgcd = y;
      while (x % pgcd != 0 || y % pgcd != 0)
      {
         pgcd--;
      }
   }
 
   return pgcd;
}
 
/* --------------------------------------------------------------------------
   trouver_pgcd_methode_2 ()
   --------------------------------------------------------------------------
   Role : retourne le PGCD de 2 nombre par la formule mathematique
   -------------------------------------------------------------------------- */
long trouver_pgcd_methode_2 (long x, long y)
{
   long tmp;
 
   if (x < y)
   {
      permuter (&x, &y);
   }
 
   while (y != 0)
   {
      tmp = x;
      x = y;
      y = tmp % x;
   }
 
   return x;
}
 
/* --------------------------------------------------------------------------
   comparer_complexite_temporelle ()
   --------------------------------------------------------------------------
   Role : Comparer la complextité temporelle des 2 methodes
   -------------------------------------------------------------------------- */
void comparer_complexite_temporelle (long x, long y)
{
   clock_t temps_initial_methode;
   clock_t temps_final_methode;
   clock_t duree_methode_1;
   clock_t duree_methode_2;
   long pgcd1;
   long pgcd2;
 
   temps_initial_methode = clock ();
   pgcd1 = trouver_pgcd_methode_1 (x, y - 1);
   temps_final_methode = clock ();
   duree_methode_1 = temps_final_methode - temps_initial_methode;
 
   temps_initial_methode = clock ();
   pgcd2 = trouver_pgcd_methode_2 (x, y - 1);
   temps_final_methode = clock ();
   duree_methode_2 =  temps_final_methode - temps_initial_methode;
 
   printf ("PGCD = %ld duree methode 1 : %10.0lf ns\n", pgcd1, (double) duree_methode_1 /
                                              CLOCKS_PER_SEC * 1000000000.0);
   printf ("PGCD = %ld duree methode 2 : %10.0lf ns\n", pgcd2, (double) duree_methode_2 /
                                              CLOCKS_PER_SEC * 1000000000.0);
}
 
int main (int argc, char **argv)
{
   comparer_complexite_temporelle (INT_MAX, INT_MAX - 1);
 
   return EXIT_SUCCESS;
}

Merci.