IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

PGCD: quelle est la méthode la plus rapide


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éclairé

    Inscrit en
    juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : juin 2004
    Messages : 1 397
    Points : 763
    Points
    763
    Par défaut PGCD: quelle est la méthode la plus rapide
    Bonjour tout le monde !

    Je me pose la question de savoir quelle méthode pour déterminer le PGCD est la plus rapide ?

    L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?

    Ma question est simple, mais impossible de trouver des preuves avec graphiques mesurant le temps consommé...

    Merci de m'éclairer !
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par progfou Voir le message
    L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?
    ??

    http://en.wikipedia.org/wiki/Binary_GCD_algorithm
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 74
    Localisation : France

    Informations forums :
    Inscription : novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?
    Simple mise au point, aucune de ces méthodes n'IMPOSE la récursivité. Il s'agit de récursivité terminale, l'implémentation en itératif est donc immédiate.
    Cela dit la référence de Pseudocode est définitive (rien à ajouter).
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  4. #4
    Membre éclairé

    Inscrit en
    juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : juin 2004
    Messages : 1 397
    Points : 763
    Points
    763
    Par défaut
    Si ce qui te choque c'est que je ne sois pas tombé sur ce lien, tu m'en vois désolé .

    Je te remercie pour cet excellent lien.
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par progfou Voir le message
    Si ce qui te choque c'est que je ne sois pas tombé sur ce lien, tu m'en vois désolé .


    C'est surtout "la soustraction successive qui impose la récursivité" qui m'a semblé louche. Généralement des "trucs successifs" ca impose plutot des itérations.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Quel est la méthode la plus rapide ?
    Par Invité dans le forum Langage
    Réponses: 9
    Dernier message: 10/11/2014, 21h20
  2. Réponses: 9
    Dernier message: 19/06/2012, 14h56
  3. Quelle est la multiplication la plus rapide? décimal ou binaire
    Par medkarim dans le forum VB 6 et antérieur
    Réponses: 4
    Dernier message: 14/10/2008, 00h27
  4. Réponses: 16
    Dernier message: 19/05/2005, 17h20
  5. [FB1.5]Quelle est la requete la plus rapide ?
    Par Sitting Bull dans le forum SQL
    Réponses: 4
    Dernier message: 10/12/2004, 14h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo