Bonjour
je cherche a faire un programme pouvant calculer le plus grand diviseur commun et je n´arrive a rien. A chaque fois sa ne marche pas.
Est ce que quelqu´un saurait comment faire ?
merci d´avance

J´ai oublie:
je suis avec dev C++
et je travail en C dans l´invit de commande

int pgcd (int m, int n)
{
if (n==0)
return m;
return pgcd(n,m%n);
}

J´ai meme encore plus compact

int pgcd (int m, int n)
{
return (n==0)?(m):pgcd(n,m%n);
}

Ton code est erroné pour m ou n négatifs... Et pourquoi faire du récursif quand on peut très facilement s´en passer ?

int pgcd(int u, int v)
{
int t;

if (u < 0)
u = -u;
if (v < 0)
v = -v;

while (v > 0)
{
t = v;
v = u % v;
u = t;
}

return u;
}

Je préfère comme ça^^

Ton code est erroné pour m ou n négatifs
--> Oui, j´ai pas géré les nombres négatifs

Et pourquoi faire du récursif quand on peut très facilement s´en passer ?
--> Je ne suis pas d´accord la récursivité peut etre tres sympa dans certains cas

Bon, apres, c´est vrai que des fois c´est sympa de changer pour de l´itératif, mais pas toujours !
Enfin, apres, les gouts et les couleurs !

Dans le cas présent, on évite de déposer des infos en plus sur la pile. Mais bon, les compilos modernes dérécursivent d´eux´mêmes pour ce genre de choses.

Après, Génie logiciel ou Optimisation ?
Choisit ton camp camarade !

C´est vrai que l´algo de JujuDredd sera plus rapide, car y´a pas d´empilage.

Tout dépend ensuite si les calculs de PGCD se trouvent en zone critique dans le programme a faire, ou non. Si le calcul du PGCD est appelé 1 million de fois par seconde, c´est vrai qu´il faut optimiser !

"Et pourquoi faire du récursif quand on peut très facilement s´en passer ? "

parce que c´est plus compacte, donc plus lisible, et qu´il y a moins de source d´erreur. D´autre part ça rend mieux compte de la logique de l´algorithme d´euclide (c´est bien lui ?) du calcul du pgcd qui se décrit naturellement de manière récursive.

"C´est vrai que l´algo de JujuDredd sera plus rapide, car y´a pas d´empilage."

faux : l´algo que tu as donné est récursif terminal, et même GCC est capable de dérécursifier un truc comme ça (avec les options de compilation qui font bien) donc il n´y a pas de passage par la pile pour les appels récursifs de la fonctions.

merci a vous

En effet il sait transformé la récursivité terminal en itératif a partir de -O2. Eb outre apres avoir fait plein de test de performance en début d´année, le nombre d´opération simple a optimiser qu´il n´a pas vu m´a consterné. Et je penses qu´il faut vérifier ce que fait gcc même s´il dit qu´il le fait!

Je penses par exemple a -f-unroll-loop qui est tellement réputé pour ne pas fonctionner que les developeur de la STL ont déroulé des boucles a la main.

dnob700 => Ah oui, exact, j´avais oublié que les compilos savent optimiser maintenant... enfin ça fait même un bon moment je crois.
Enfin perso, quand c´est pas trop lourd, je préfère utiliser l´itératif même si je doit gérer une pile. Avec une pile que je gère moi-même je vais pouvoir contrôler que chaque malloc ne retourne pas null au lieu de faire un programme qui plante à cause d´un débordement de pile.

godrik => Ouais on devrait tous faire de l´assembleur pour plus se faire arnaquer par les compilos verreux

mmm, peut etre pas. Mais il ne faut pas trop lui faire confiance non plus!

"Enfin perso, quand c´est pas trop lourd, je préfère utiliser l´itératif même si je doit gérer une pile. Avec une pile que je gère moi-même je vais pouvoir contrôler que chaque malloc ne retourne pas null au lieu de faire un programme qui plante à cause d´un débordement de pile."

perso je préfère programmer en récursif dans un langage qui se charge de tout ses détail pour moi, ce qui me permet d´être 10 fois plus productif, et de faire beaucoup moins d´erreur que celui qui codera la même chose "à la main". Pour un résultat sensiblement équivalent en terme de performance (c´est-à-dire asymptotiquement au moins aussi bon, avec peut-être un petit facteur quand même de perte de vitesse, mais rarement critique) grâce à un compilo qui sait faire de l´optimisation.

En résumé ? ... OCaml powaaa !! !

Dnob, ce style de raisonement depend profondement de ce que tu fais et sur quel plateforme tu le fais. Tu ne peux pas forcement te permettre de perdre cette performance.

Pour le cas général de je fais un test chez moi, je suis bien evidement d´accord! ocaml powah!!

"Dnob, ce style de raisonement depend profondement de ce que tu fais et sur quel plateforme tu le fais."

On programme bien les téléphone mobile en Java. Donc pourquoi pas en OCaml (sur ces machines le java est interprété ou bien JIT-é ?) .

Même pour du calcul numérique, le Caml peut se justifier, ensuite c´est sur que si on a un supercalculateur, là on ´a pas le choix, il faudra faire du C avec le compilo propre de la plateforme. Mais bon, ce n´est pas le cas général (surtout sur ce forum) je pense.

JE ne conteste pas l´idée de fair du C, là bien sûr c´est une question de choix, mais juste, j´ai trouvé l´argument de jujudredd ("Avec une pile que je gère moi-même je vais pouvoir contrôler que chaque malloc ne retourne pas null au lieu de faire un programme qui plante à cause d´un débordement de pile.") assez étonnant. Plus précisement, il montre une incompréhension de ce qu´est un système garbage collecté. I.e. ce n´est pas parce que tu controle que le malloc a réussi que ton programme ne plante pas ? une fois qu´il a échoué, que peut-tu faire d´autre que de terminer ce que tu était en train de faire avec un message d´erreur ?

Coder ce genre de chose à la man permet de savoir ce qui se passe (mais si on connait son langage, on peut le savoir aussi), mais ça n´empêche pas le programmeur de faire une erreur d´implémentation (là, je parle d´algo) qui provoqueront des débordement de pile à cause d´une erreur dans l´algo.

bref, je ne veux pas troller, mais juste dire que je trouvais cet argumement très mauvais (là où il y a beaucoup de bon argument pour défendre le C ou autre langage itératifs "bas niveaux")

En effet, l´argument "je peux verifier le retour de malloc" est debile.

Par contre, il y a sur ce forum plusieurs personnes qui sont vraiment à la recherche de performance. Que ce soit parcequ´ils ont peu de ressource (je penses a ceux qui developpe sur DS par exemple) ou bien qu´il font des applications gourmande en ressource (je penses a ceux qui font du rendu 3D) ou ceux qui cherchent a tirer le meilleur parti de la machine (et la je penses au calcul scientifique).

Apres je suis bien convaincu que ca dépend de ce que tu cherches a faire. Par exemple la premiere version de rsync a été (rapidement) écrite en ocaml. Mais cette version était bien plus gourmande en ressource et a été réecrite en C plus tard.

Oh, mes argument sont "débiles"

• shocked*