Discussion :

[Invité]

Bonjours à tous, alors voilà j'ai un code que je trouve déjà assez optimisé, que je voudrais accélérer encore plus !
Je ne pensais pas ça possible, mais on m'as dit qu'ici vous saviez tout faire, alors voilà je le présente à vos yeux ébahis (ou presque...) !

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
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char *argv[])
{
  unsigned long x,i,s,s2;
  for (x=strtol (argv[1], NULL, 10);x<=strtol (argv[2], NULL, 10);x++)
  {
   s=0;
   for (i=2;i<=sqrt(x);i++)if (x%i==0)s=s+i+x/i;               
   s++;
   s2=0;
   for (i=2;i<=sqrt(s);i++)if (s%i==0)s2=s2+i+s/i;               
   s2++;
   if (s2==x)printf("%d - %d\n",s,x);
  }
  printf ("Appuyez sur une touche pour contiunuer...\n");
  getchar ();
  return 0;
}

Oui alors, c'est cracra y'as aucun contrôle sur les valeurs entrées, mais c'est pas grave :p

Merci d'avance :p

[Gui13]

Tu savais que les commentaires ne sont pas interprétés?
Ils ne nuisent pas à la vitesse de ton programme, par contre ils accélerent grandement NOTRE compréhension du code

Il fait quoi ton programme? Explique un peu, c'est souvent en améliorant les algos qu'on peut accélerer un programme!

EDIT: et d'ailleurs la mise en page non plus ne ralentit pas le programme

[zooro]

+1 pour les commentaires et l'indentation

Sinon, ton programme se terminerait beaucoup plus vite sans le getchar à la fin

[droggo]

Lin,

+1 sur Gui13 et zooro

+ : optimiser le code, ce n'est pas rendre le source le plus compact possible.

Par exemple, une optimisation carrément loupée est:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

   for (i=2;i<=sqrt(x);i++)if (x%i==0)s=s+i+x/i;

A chaque tour de boucle, pour faire le test de sortie i<=sqrt(x), sqrt(x) sera calculée !
or, x n'est pas modifié dans la boucle.
Donc, une variable pour stocker sqrt(x) avant d'entrer dans la boucle...

Oui alors, c'est cracra y'as aucun contrôle sur les valeurs entrées, mais c'est pas grave

Et pourtant, c'est une habitude à ne pas prendre, ça te conduira directement vers des bugs à n'en plus finir, alors que vérifier les entrées est simple, et sécurise le programme.

[Invité]

Désolé à tous
Mon programme sert en fait à chercher les nombres amicaux.
Explication :

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
 
//Inclure les librairies (bon ok pas de commentaires inutiles xD
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char *argv[])
{
  unsigned long x,i,s,s2; //Déclaration des variables
 
//tout d'abord on boucle sur tous les nbrs
  for (x=strtol (argv[1], NULL, 10);x<=strtol (argv[2], NULL, 10);x++)
  {
   s=0;
   //pour chaque nombre on calcule la somme de ses diviseurs à part lui même
   for (i=2;i<=sqrt(x);i++)
   {
      if (x%i==0) //On regarde si c'est divisible
     {
        s=s+i+x/i; //si oui on ajoute au nombre actuel, le diviseur et le diviseur "opposé"
      }
   }               
   s++;//On ajoute 1 car 1 divise tout xD
 
   s2=0;
   for (i=2;i<=sqrt(s);i++) //On cherche les diviseurs de la somme des diviseurs
   {
      if (s%i==0) //idem
      {
         s2=s2+i+s/i; //idem
      }
   }             
   s2++;
   if (s2==x) //si la somme des diviseurs de la somme des diviseurs d'un nombre égale ce nombre, il est amical et on l'affiche :p
  {
     printf("%d - %d\n",s,x);
  }
  printf ("Appuyez sur une touche pour continuer...\n");
  getchar ();
  return 0;
}

Désolé pour tout ce qui est cracra, mais j'ai appris à programmer sur calculette (graph 25 = 24ko d'espace mémoire et processeur à 10 hertz xD)

Sinon merci pour le sqrt ! Suis je bête de ne pas y avoir pensé :p

C'est merveilleux, sur une boucle de 1 millions mon programme est passé de 423 secondes à 71 secondes !

[droggo]

Hon,

Désolé pour tout ce qui est cracra, mais j'ai appris à programmer sur calculette (graph 25 = 24ko d'espace mémoire et processeur à 10 hertz xD)

A mon humble avis, ce n'est pas une raison, d'autant moins que tu es conscient que ton code n'est pas propre.

C'est merveilleux, sur une boucle de 1 millions mon programme est passé de 423 secondes à 71 secondes !

sqrt est une fonction plutôt gourmande.

Curieusement, ton code contient toujours la même ligne pour les boucles ?

[souviron34]

Bon déjà en corrigeant les boucles :

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
 
//Inclure les librairies (bon ok pas de commentaires inutiles xD
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char *argv[])
{
  unsigned long x,i,s,s2; //Déclaration des variables
  unsigned long xmin, xmax ;
  double racine ;
 
  xmin = strtol (argv[1], NULL, 10);
  xmax = strtol (argv[2], NULL, 10);
 
//tout d'abord on boucle sur tous les nbrs
  for (x=xmin ; x<=xmax ;x++)
  {
   s=0;
   racine = sqrt((double)x);
 
   //pour chaque nombre on calcule la somme de ses diviseurs à part lui même
   for (i=2;i<=racine;i++)
   {
      if (x%i==0) //On regarde si c'est divisible
     {
        s=s+i+x/i; //si oui on ajoute au nombre actuel, le diviseur et le diviseur "opposé"
      }
   }               
   s++;//On ajoute 1 car 1 divise tout xD
 
   s2=0;
   racine = sqrt((double)s) ;
 
   for (i=2;i<=racine;i++) //On cherche les diviseurs de la somme des diviseurs
   {
      if (s%i==0) //idem
      {
         s2=s2+i+s/i; //idem
      }
   }             
   s2++;
   if (s2==x) //si la somme des diviseurs de la somme des diviseurs d'un nombre égale ce nombre, il est amical et on l'affiche :p
  {
     printf("%d - %d\n",s,x);
  }
  printf ("Appuyez sur une touche pour continuer...\n");
  getchar ();
  return 0;
}

Ensuite 2 questions existentielles :

es-tu sûr que s et s2 doivent être des long, et non pas des doubles ? Et que tes divisions doivent être des divisions entières (comme ici : x/i et s/i dont des divisions entières) ?

Et enfin, tu pourrais également éviter tes tests %i == 0 :

le départ de la boucle sera forcément |x| (abs(x))
et l'incrément x

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
for ( i = x ; i <= racine ; i=i+x )
 {
         s2=s2+i+s/i; //idem
}

par exemple

[Jean-Marc.Bourguet]

* Chercher les facteurs premiers en se servant d'une table de nombres premiers plutot que tous les diviseurs et ensuite former les diviseurs.

* On peut eviter les racines carrees en utilisant de l'induction. Genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
racine = sqrt(xmin);
carre = racine*(racine + 2) +1;
for (x = xmin; x <= xmax; ++x) {
   if (carre == x) {
      ++racine;
      carre += 2*racine+1;
   }
   ...
}

* Tu peux eviter de chercher si un nombre a un jumeau si xmin <= s < x car le cas a deja ete envisage.

[fearyourself]

C'est merveilleux, sur une boucle de 1 millions mon programme est passé de 423 secondes à 71 secondes !

Tu ne compiles pas avec les bonnes options...

Le compilateur doit voir que tes appels sqrt(x), sqrt(s) et les strtol de la boucle externe sont des invariants. Du coup, il les sortira tout seul. Je ne dis pas que c'est forcément idiot de le faire soi-même mais si déjà tu ne compiles pas avec les bonnes options...

NB: J'ai testé les deux versions avec gcc -O3...
Jc