Accélérer du code après l'impossible !

Version imprimable

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:

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

11/04/2007, 22h24
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 ;)
11/04/2007, 22h27
zooro

+1 pour les commentaires et l'indentation

Sinon, ton programme se terminerait beaucoup plus vite sans le getchar à la fin :aie:
11/04/2007, 22h41
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:

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

Citation:

Envoyé par nico le terrible

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.

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

Code:

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 !

12/04/2007, 02h00
droggo

Hon,

Citation:

Envoyé par nico le terrible

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.

Citation:

Envoyé par nico le terrible

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 ?

Bon déjà en corrigeant les boucles :

Code:

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:

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

par exemple
:D

12/04/2007, 10h40
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:

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.
12/04/2007, 20h51
Invité

Merci à tous pour vos nombreuses et pertinentes réponses !

Citation:

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

Une table des nombres premiers, pourquoi pas :s, mais je vais jusqu'à 10 milliards alors je sais pas si ça ferais vraiment gagner du temps de manipuler un assez gros tableau...
D'un autre coté formé tous les diviseurs ne me fera t'il pas perdre un temps fou ?

Citation:

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) ?

Tout a fait sur :p En effet je cherche des diviseurs, donc toutes les divisions auront des résultats entier ;)

Citation:

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

la je pige pas ce que tu veut dire :s

Citation:

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

J'en suis conscient mais ce sont des mauvais réflexes, même sur PC, j'ai toujours peur d'utiliser toute la mémoire :( Et les commentaires ne sont pas non plus un réflexes et les miens sont généralement mauvais, et font double emplois avec le code (je vois pas comment expliquer ^^). Je tente néanmoins de les corriger :p

Citation:

On peut éviter les racines carrées en utilisant de l'induction

Eux je vais essayer de comprendre je commenterais après :p

Citation:

* Tu peux eviter de chercher si un nombre a un jumeau si xmin <= s < x car le cas a déjà été envisage.

C'est amusant j'avais bien vu qu'à la fin, je pouvais n'en afficher que un sur deux, mais j'avais pas vu que je pouvais faire la distinction dès ce moment la :p

Merci encore une fois à tous ^^
13/04/2007, 11h01
Ulmo

Citation:

Envoyé par nico le terrible

Citation:

Envoyé par Jean-Marc.Bourguet

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

la je pige pas ce que tu veut dire :s

Plutot que d'incrémenter ton compteur de 1 en 1 pour ne garder que les multiples de N, autant incrémenter ton compteur de N en N, en démarrant de N au lieu de 1.
13/04/2007, 11h14
fearyourself

Citation:

Envoyé par nico le terrible

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