Partage

Optimiser un code

Décomposition en facteurs premiers

Sujet résolu

Anonyme

16 novembre 2009 à 19:59:50

Bonjour, j'ai codé un programme qui décompose un nombre en facteurs premiers, et j'aimerais savoir comment l'optimiser, sachant qu'il va pas super vite (même si j'ai fat ce que je pouvais). Voilà le code :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int isPrime(unsigned long long nb);

int main (int argc, const char * argv[]) {
    unsigned long long entree, i, racine;
	unsigned long long *facteurs = NULL, *exposants = NULL;
	scanf("%lld", &entree); 
	racine = sqrt(entree);
	exposants = malloc(racine * sizeof(int));
	facteurs = malloc(racine * sizeof(int));
	for (i = 1; i < racine+1; i++) {
		if (isPrime(i) == EXIT_SUCCESS) {
			facteurs[i] = 1;
			exposants[i] = 1;
			while (entree%(int)pow(i, exposants[i]) == 0)
				exposants[i]++;
			exposants[i]--;
		}
	}
	if (isPrime(entree) == EXIT_FAILURE) {
		printf("%lld = ", entree);
		for (i = 1; i < racine+1; i++) {
			if (facteurs[i] && exposants[i] == 1)
				printf("%lld * ",i);
			else if (facteurs[i] && exposants[i]) {
				printf("%lld^%d * ", i, exposants[i]);
			}
		}
		printf("%c%c", 8, 8);
	}
	else {
		printf("\npremier\n");
	}

	free(facteurs);
	free(exposants);
    return EXIT_SUCCESS;
}

int isPrime(unsigned long long nb) {
	unsigned long long i, prime = 0;
	for (i = 1; i < nb; i++) {
		if (nb%i == 0) {
			prime++;
		}
	}
	if (prime == 1)
		return EXIT_FAILURE;
	return EXIT_SUCCESS;
}

EDIT : Sachant que je compile en "Release". Sinon, il a des problèmes lorsque je calcule 2^32-1, pourtant c'est en-dessous de la limite des unsigned long long non ?

colbseton

16 novembre 2009 à 20:12:36

Tout d'abord, ton code est très moche. Il est pas aéré, ensuite si la fonction "isPrime" est la fonction qui teste si un nombre est premier ou non, je te conseille de la faire comme ça :
C'est une sorte d'optimisation :

int est_prem(int n) {
  int i;

  for (i=2;i<sqrt(n);i++) 
      if (n % i == 0) 
          return 0;
  
  return 1;
}

Ensuite, toutes les conditions où il n'y a qu'une instruction ne nécessitent pas de crochet. Tu peux donc les supprimer pour améliorer la visibilité.

4drien

16 novembre 2009 à 20:14:44

Salut,
Je viens de coder ca il y a 1 jour exactement. J'ai trouvé un algo beaucoup plus simple à l'adresse suivante:

1. Fonction DecoFact : reçoit un nombre K
   2. Calculer sa racine
   3. Pour tous les nombres inférieurs à cette racine (appelons les « i »),
         1. Si le nombre testé est divisible par i
               1. L’ajouter dans la liste des diviseurs.
               2. Faire K = K / i
               3. Faire i = i -1
         2. Si K>2, continuer la boucle, sinon en sortir
   4. Si K>2, le nombre restant est premier : l’ajouter à la liste
   5. Fin de la fonction : Renvoyer la liste.

Anonyme

16 novembre 2009 à 20:45:15

4drien, ton code ne gère pas les exposants...
colb-seton, si j'utilise ta fonction mon code ne marche plus.
Il y a en fait un problème dans mon code : si j'entre 44, il me met

44 = 2^2

. Je pense que c'est parce que 11 > racine de 44, mais en mettant

for (i = 1; i < entree; i++) {
		if (isPrime(i) == 1) {
			facteurs[i] = 1;
			exposants[i] = 1;
			while (entree%(int)pow(i, exposants[i]) == 0)
				exposants[i]++;
			exposants[i]--;
		}
	}

au lieu de ce qui est dans mon post original, il me dit

90 = 2 * 3^2

au lieu de

90 = 2 *3^2 * 5

WTF ?!

4drien

16 novembre 2009 à 20:55:33

Ba après c'est à toi de l'adapter bien sûr, j'ai coder le mien en C pour ma calculatrice, et les exposants sont très bien gérés (je parcour ma liste chainée de facteur, si il existe déjà j'incrémente la variable occurrence, sinon je le rajoute à la liste).

Ma liste chainée:

typedef struct element element;
struct element
{
    int nombre;
    int occurence;
    struct element *nxt;
};
 
typedef element* liste;

Mon Main

#include <tigcclib.h>

#include "listeChainee.h"

void _main(void)
{
  long int nombre = 0;
  int racine;
  int i = 0;
  liste facteur = NULL;

  clrscr();
  getInteger (&nombre);
  racine = (int) sqrt((double) nombre) +1;
  
  clrscr();
  printf ("Décomposition en produit de facteur premier: \n");
  
  for (i = 2; i < racine; i++)
    {
    	if (nombre % i == 0)
    	  {
    	  	facteur = ajouter(facteur, i);
    	  	nombre = nombre / i;
    	  	i = i - 1;
    	  }
    	if (nombre < 2)
    	  break;
    }
    
  if (nombre > 2)
    facteur = ajouter(facteur, nombre);
    
  afficherListe (facteur);

  
  ngetchx();
}

Mes fonctions de liste chainée

#include <tigcclib.h>

#include "listeChainee.h"

liste ajouter(liste liste, int valeur)
{
    element *tmp = liste;

    while(tmp != NULL)
    {
        if (tmp->nombre == valeur)
          {
            tmp->occurence ++;
            return liste;
          }

        tmp = tmp->nxt;
    }


  element* nouvelElement = malloc(sizeof(element));
 
  nouvelElement->nombre = valeur;
  
  nouvelElement->occurence = 1;
 
  nouvelElement->nxt = liste;
 
  return nouvelElement;
}


void afficherListe(liste liste)
{
    element *tmp = liste;

    while(tmp != NULL)
    {
        /* On affiche */
        printf("%d e %d\n", tmp->nombre, tmp->occurence);
        tmp = tmp->nxt;
    }
}

résultat pour le nombre 98:
Image utilisateur

[edit] La fonction getInteger:

void getInteger (long int *integer)
{
	char buffer [9];
  SCR_STATE ss;
  short key;
  unsigned short i = 0;
  
  printf ("Nombre: ");
  
  buffer[0] = 0;
  SaveScrState (&ss);
  do
    {
      MoveTo (ss.CurX, ss.CurY);
      printf ("%s_  ", buffer);
      key = ngetchx ();

          
      if ( (key >= '0' && key <= '9') && (i < 9) ) /*on accepte que les chiffres*/
        buffer[i++] = key;
    
      if (key == KEY_BACKSPACE && i)
        i--;
      buffer[i] = 0;
    } while (key != KEY_ENTER || i < 1);
    
	*integer = atol (buffer);
}

Anonyme

16 novembre 2009 à 21:00:53

En tout cas, maintenant je sais qu'on peut coder en C pour TI, je pensais qu'il n'y avait que le TI-Basic.

HighTam

16 novembre 2009 à 21:32:09

Citation : Colb-Seton

C'est une sorte d'optimisation :

int est_prem(int n) {
  int i;

  for (i=2;i<sqrt(n);i++) 
      if (n % i == 0) 
          return 0;
  
  return 1;
}

La fonction sqrt() est relativement lente et avec ton code, à chaque tour de boucle on va faire appel à la fonction sqrt(), donc ça serait meilleur de stocker la valeur de la racine carrée dans une variable :

int isPrime(int n)
{
    int i, r = sqrt(n);
    for (i = 2 ; i <= r ; i++) 
        if (!(n % i)) 
            return 0;
  
    return 1;
}

Pouet_forever

16 novembre 2009 à 21:43:53

On peut améliorer encore

Avant de calculer ta racine carrée et d'entrer dans ta boucle tu peux tester déjà si ton nombre est divisible par 2, si c'est le cas tu renvoies 0.
Et comme on sait que de toutes façons un nombre premier n'est pas pair, dans ta boucle tu peux simplement faire i += 2

Tu divises déjà par 2 le nombres de calculs fait dans ton for

Anonyme

16 novembre 2009 à 21:56:57

Effectivement Pouet_forever, je n'avais pas pensé à ça. Cependant cela ne résout pas le problème de si je mets 44 comme entrée (phrase boiteuse), il me met 44 = 2^2. Je pense que c'est parce que sqrt(44) < 11. Sinon, je sais que sqrt est lente, je l'ai recodée moi-même pour voir.

bluestorm

16 novembre 2009 à 22:08:37

Tu ferais mieux d'utiliser la solution proposée par 4drien, elle est à la fois beaucoup plus simple et beaucoup plus rapide que la tienne.

L'optimisation passe avant tout par le choix de méthodes efficaces au départ, plutôt que de la bidouille après avoir terminé.

Anonyme

16 novembre 2009 à 22:38:06

Bon, j'ai essayé d'implémenter ton algorithme ce qui donne ça :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main (int argc, const char * argv[]) {
	int i, racine, entree, k;
	int *diviseurs = NULL, *exposants = NULL;
	scanf("%d", &entree);
	
	k = entree;
	racine = sqrt(entree)+1;
	diviseurs = malloc(entree*sizeof(int));
	exposants = malloc(entree*sizeof(int));
	
	for (i = 1; i < racine; i++) {
		if (k%i == 0) {
			if (exposants[i] == 0)
				exposants[i]++;
			diviseurs[i] = 1;
			exposants[i]++;
			k = k/i;
			i--;
		}
		if (k <= 2)
			break;
	}
	if (k > 2)
		diviseurs[i] = 1;
	
	printf("%d = ", entree);
	for (i = 1; i < racine; i++) {
		if (diviseurs[i] && exposants[i] == 1)
			printf("%d * ", i);
		else if (diviseurs[i] && exposants[i])
			printf("%d^%d * ", i, exposants[i]);

	}
    return 0;
}

Qui ne marche pas, je n'ai pas encore trouvé pourquoi.

bluestorm

16 novembre 2009 à 22:44:33

Entre temps, j'ai fait un petit essai, et c'est effectivement très rapide.

Voici mon code (attention, je ne code pas en C, donc il n'est sans doute pas un exemple) :

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int *decompose(int n, int *len)
{
    int k = 2;
    int *table = malloc(sizeof(int) * (int) floor(log2(n) + 1));

    for (k = 2; n > 1; k++) {
        table[k] = 0;
        while (n % k == 0) {
            n /= k;
            table[k]++;
        }
    }

    *len = k;
    return table;
}

int main()
{
    int i, len, n, *table;

    scanf("%d", &n);
    table = decompose(n, &len);

    for(i = 0; i < len; i++)
        if (table[i] > 0) {
            printf("%d", i);
            if (table[i] > 1)
                printf("^%d", table[i]);
            printf(" ");
        }
    printf("\n");

    free(table);
    return 0;
}

Anonyme

16 novembre 2009 à 22:49:34

Effectivement ton code marche (et est même beaucoup plus rapide que le mien). Cependant, une petite question (due à mon niveau de maths) : Que fait la fonction log2() ? Pourquoi prends-tu sa troncature ? EDIT : ceil c'est pas la troncature, je me plante toujours.

bluestorm

16 novembre 2009 à 22:53:50

floor(log2(k))+1 renvoie le nombre de bits utilisés par k en binaire.

Edit : en fait, le code est faux; log2(k) approxime le nombre de facteurs différents, mais l'espace utilisé par cette méthode dépend en fait de la taille du plus grand facteur, qui peut aller jusqu'à <math>\(n\)</math> ou <math>\(\sqrt{n}\)</math>.

Il faudrait utiliser une forme compressée. Je poste une version corrigée dans quelques minutes.

Floooder

16 novembre 2009 à 23:02:20

Hum, bluestorm, tu es sur que ton code est bon?

Parce que si n est premier, alors k va dépasser log2(n)+1

Edit : pas vu ton edit

Je pense que la meilleure methode serrait une variante du crible d'eratosthène (je poste mon code dans 5 minutes)

bluestorm

16 novembre 2009 à 23:09:26

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

void decompose(int n, int *len, int **facteurs, int **exposants)
{
    int k, cur_fact;
    *facteurs = malloc(sizeof(int) * ((int) log2(n) + 1));
    *exposants = malloc(sizeof(int) * ((int) log2(n) + 1));

    for (k = 2, cur_fact = 0; n > 1; cur_fact++) {
        while (n % k != 0)
            k++;
        while (n % k == 0) {
            n /= k;
            (*exposants)[cur_fact]++;
        }
        (*facteurs)[cur_fact] = k;
    }

    *len = cur_fact;
}

int main()
{
    int i, len, n, *facteurs, *exposants;

    scanf("%d", &n);
    decompose(n, &len, &facteurs, &exposants);

    for(i = 0; i < len; i++) {
        int expo = exposants[i];
        printf("%d", facteurs[i]);
        if (expo > 1)
            printf("^%d", expo);
        printf(" ");
    }
    printf("\n");

    free(facteurs);
    free(exposants);

    return 0;
}

NB : la liste chaînée proposée par 4drien convient aussi, ce serait même un meilleur choix dans l'absolu, mais comme elles n'existent pas en standard en C, j'ai préféré ne pas m'embêter à les recoder.

candide

17 novembre 2009 à 0:46:53

Citation : bluestorm

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

void decompose(int n, int *len, int **facteurs, int **exposants)
{
    int k, cur_fact;
    *facteurs = malloc(sizeof(int) * ((int) log2(n) + 1));
    *exposants = malloc(sizeof(int) * ((int) log2(n) + 1));

OK pour l'algorithme mais le code est artificiellement compliqué : malloc/free, floor, doubles pointeurs, arithmétique des pointeurs
Ce code sera peu abordable à un débutant (voire débutant avancé) alors que le problème est élémentaire. Je pense que la complexité du code a pour effet de masquer l'idée apparemment simple que contient l'algorithme (à savoir qu'un facteur minimal > 1 est premier), idée qui d'ailleurs n'a rien de spontanée chez l'apprenti programmeur (qu'il s'agisse de C ou d'un autre langage). Je trouve même que ta façon d'implémenter l'algorithme est peu naturelle.

Moi j'aurais plutôt écrit cela :

#include <stdio.h>

int factor(int n, int facteurs[])
{
  int d = 2;
  int k = 0;

  while (n > 1)
    if (n % d == 0)
      {
        facteurs[k] = d;
        k++;
        n /= d;
      }
    else
      d++;
  return k;
}

#define  N 32
int main(void)
{
  int i;
  int facteurs[N];
  int n, nb_facteurs;

  scanf("%d", &n);
  nb_facteurs = factor(n, facteurs);

  for (i = 0; i < nb_facteurs; i++)
    printf("%d ", facteurs[i]);
  printf("\n");
  return 0;
}

Citation : bluestorm

NB : la liste chaînée proposée par 4drien convient aussi, ce serait même un meilleur choix dans l'absolu,

Je ne vois pas du tout l'intérêt des listes chainées ici.

colbseton

17 novembre 2009 à 19:08:49

Citation : Pouet_forever

On peut améliorer encore
Avant de calculer ta racine carrée et d'entrer dans ta boucle tu peux tester déjà si ton nombre est divisible par 2, si c'est le cas tu renvoies 0.
Et comme on sait que de toutes façons un nombre premier n'est pas pair, dans ta boucle tu peux simplement faire i += 2
Tu divises déjà par 2 le nombres de calculs fait dans ton for

Et si n==9 ? J'ai beau aller de deux en deux, 9 est divisible par 3. J'ai ptète pas bien compris ce que t'as dis... A moins que tu démarres la boucle à i=1

Citation : ttthebest

colb-seton, si j'utilise ta fonction mon code ne marche plus.

J'ai jamais dis que ça allait résoudre tous tes problèmes

Pouet_forever

17 novembre 2009 à 19:24:01

int isPrime(int n)
{
	int i, r;
	if (n < 2 || n%2 == 0)
		return (n == 2);
	r = sqrt(n);
	for (i = 3 ; i <= r ; i+=2) 
		if (!(n % i)) 
		return 0;
	return 1;
}

bluestorm

17 novembre 2009 à 19:47:52

Il n'y a pas besoin de savoir faire un test de primalité (compliqué) pour donner les facteurs premiers d'un nombre (simple).

Il suffit de prendre tous les facteurs en partant du plus petit, et de diviser à chaque fois le nombre par le facteur, jusqu'à que le nombre soit égal à 1. Comme on a commencé par les petits facteurs, on ne tombe que sur des facteurs premiers¹, sans avoir besoin de faire de test de primalité.

¹ : on ne peut pas tomber sur un facteur composé de plusieurs sous-facteurs, puisqu'on serait tombé sur un de ses sous-facteurs avant

candide > l'intérêt de la liste chaînée vient du fait qu'on ne connaît pas à l'avance le nombre de facteurs. J'ai aussi pensé à borner par la largeur des entiers en mémoire, mais ce n'est pas portable (même en utilisant sizeof, puisque je ne sais pas avoir accès à la taille d'un byte²) donc j'ai préféré éviter.

² : maintenant que je l'écris, on peut en fait borner "facilement" par sizeof(int)+4, mais ce n'est pas terriblement clair.

Dans un langage avec des listes chaînées, on ne se pose pas toutes ces questions.

candide

17 novembre 2009 à 21:38:47

Citation : bluestorm

candide > l'intérêt de la liste chaînée vient du fait qu'on ne connaît pas à l'avance le nombre de facteurs. J'ai aussi pensé à borner par la largeur des entiers en mémoire, mais ce n'est pas portable (même en utilisant sizeof, puisque je ne sais pas avoir accès à la taille d'un byte²)

On peut tout à fait y parvenir en utilisant l'entête standard limits.h et la macro-constante ULONG_MAX qui te donne la valeur max d'un unsigned long. Ensuite tu extrais sans difficulté la plus grande puissance de 2. De toute façon, même cela est vain, en pratique tu ne dépasseras pas un nombre N de 64 ou 128 bits ce qui obligatoirement majore par N le nombre maximum de facteurs premiers (2 est le plus petit des nombres premiers) et il suffit donc d'allouer un (petit) tableau statique. En outre, tu sais bien que la méthode naïve ne permet pas de factoriser des nombres grands et donc toutes ces subtilités sont vaines. Petit exemple avec mon programme compilé avec option d'optimisation :

536870923
536870923 

real        0m13.325s
user        0m11.277s
sys        0m0.084s

Donc je répète, c'est une absurdité que d'utiliser des listes chainées ici. Dans le pire des cas, on aurait juste besoin d'une liste extensible (!= chainée) ce que realloc() permettrait de faire. Je réagis un peu brusquement car c'est une tendance trop marquée que d'entendre un peu partout (ici comme dans beaucoup de livres par exemple) qu'il faut utiliser à tout bout de champ des listes chaînées alors que leur utilisation comporte de nombreuses difficultés (en particulier en C standard) et présente un coût d'utilisation qui est loin d'être négligeable, sans parler de leur lenteur si elles sont mal utilisées.

Il ne faut pas faire dévier l'esprit des débutants sur des questions artificielles de codage ou d'implémentation qui risquent de masquer le coeur algorithmique. Un débutant comme le PO doit plutôt consacrer son effort à réfléchir à l'obtention des facteurs premiers par la méthode que tu as indiquée (ce qui est une question d'algorithmique et d'arithmétique élémentaire).

4drien

17 novembre 2009 à 22:27:55

Les listes chainées je les utilise car c'est le moyen le plus simple que j'ai trouvé pour gérer les exposants.
Avant d'ajouter un élément à cette liste, je la parcours pour vérifier que ce facteur n'existe pas déjà, si c'est le cas j'incrémente la variable exposant. Sinon je rajoute une cellule.
Après s'il existe une méthode plus efficace, je suis preneur

bluestorm

17 novembre 2009 à 22:33:09

Citation

Après s'il existe une méthode plus efficace, je suis preneur

Tu peux utiliser la méthode avec un while imbriqué que j'ai montrée dans ce post :

for (k = 2, cur_fact = 0; n > 1; cur_fact++) {
        while (n % k != 0)
            k++;
        while (n % k == 0) {
            n /= k;
            (*exposants)[cur_fact]++;
        }
        (*facteurs)[cur_fact] = k;
    }

Avec la boucle while (la deuxième), tu peux facilement calculer l'exposant d'un facteur donné en une seule passe, sans lecture de ta table/liste de facteurs déjà trouvés.

candide

17 novembre 2009 à 22:59:24

Citation : 4drien

Après s'il existe une méthode plus efficace, je suis preneur

Avec la méthode que bluestorm a montré, la gestion des exposants est très simple puisque tes facteurs premiers identiques arrivent les uns après les autres.

Ta façon d'utiliser les listes chaînées est assez typique de la complexification artificielle dont certains programmeurs (amateurs comme professionnels) font preuve : à défaut de pratiquer la bonne algorithmique, ils utilisent des outils lourds à mettre en oeuvre, couteux en mémoire et en temps d'exécution, générateurs de bogues et la plupart du temps inefficace.

Sur ta TI 89, les int sont codés sur 32 bits et tu n'as aucun type standard qui soit codé sur 64 bits : tu ne peux donc pas avoir plus que 32 facteurs premiers donc un tableau de 32 int (et même de 32 short voire 32 char) suffirait largement.

Si ça te fait plaisir d'utiliser des listes chaînées, fais-le mais je te le répète, c'est totalement inutile et artificiel ici. Je viens de regarder tout ce que tu fais dans ta fonction ajouter(), c'est proprement ahurissant de complexité inutile sans compter les grossières erreurs corrélatives (allouer sans vérifier, ne pas libérer, sur de l'embarqué et même sur une machine comme la TI89, ce genre de manquement ne pardonne pas).

4drien

17 novembre 2009 à 23:34:18

J'ai eu un peu de mal à comprendre la méthode, mais finalement elle se révèle efficace et plus légère que les listes (c'est toujours quelques octets de gagné).

Citation

[...]les grossières erreurs corrélatives (allouer sans vérifier, ne pas libérer, sur de l'embarqué et même sur une machine comme la TI89, ce genre de manquement ne pardonne pas).

Ne pas libérer, je m'en suis rendu compte quelque temps après avoir posté le code (la RAM disponible qui diminue après chaque exécution, ça présage rien de bon).

candide

18 novembre 2009 à 0:22:30

Citation : 4drien

J'ai eu un peu de mal à comprendre la méthode, mais finalement elle se révèle efficace

Je me suis rendu compte que beaucoup d'étudiants ne pensaient pas à coder comme cela la décomposition en facteurs premiers. Voire beaucoup d'étudiants, y compris des étudiants en maths, avaient du mal à comprendre pourquoi cela marchait. L'idée de base est que si un entier est > 1, son plus petit diviseur d > 1 est forcément premier et que n/d fournit les autres facteurs premiers.

La version récursive de cet algorithme est naturelle, cf. ICI