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 :

Algorithm Knuth division


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2008
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2008
    Messages : 5
    Par défaut Algorithm Knuth division
    Bonsoir,

    j'essaye d'implementer l'algorithme de Knuth pour la division. J'ai trouvé un pseudo code sur un vieux post de developpez.net :

    http://www.developpez.net/forums/d81...rands-nombres/

    voilà le pseudo code en question :

    Multiplier u et v par d = {b/(v[n-1]+1]} (c'est une étape de normalisation, l'important dans le choix de d est que v[n-1] soit plus grand ou égal à B/2 à la fin

    Pour j de m à 0 par pas de -1
    qh = {(u[j+n]B + u[j+n-1])/v[n-1]}
    rh = (u[j+n]B+u[j+n-1]) mod v[n-1]
    Si qh = B ou qh*v[n-2] > rh*B + u[j+n-2]
    qh = qh-1
    rh = rh +v[n-1]
    si rh < B et qh*v[n-2] > rh*B + u[j+n-2]
    qh = qh -1
    rh = rh + v[n-1]
    fin si
    fin si
    u = u - qh v B^j
    si u < 0
    u = u + v
    qh = qh - 1
    fin si
    q[j] = qh
    fin pour
    Et quelques posts plus loin :

    Je sais que je déterre un vieux topic mais j'ai besoin d'un tel algorithme. J'ai essayé d'appliquer celui de Jean-Marc à un exemple et cela ne fonctionne pas :
    u = 1234
    v = 45

    On trouve d=2 d'où u=2468 et v=90

    j=2 :
    qh = 2/9 = 0
    rh = 2%9 = 2
    donc q[2] = 0

    j=1 :
    qh = 24/9 = 2
    rh = 6
    u = u-2*90 = 288
    donc q[1] = 2

    j=0:
    qh = 28/9 = 3
    rh = 28%9 = 1
    u = u-3*90 = 2018
    donc q[0] = 3

    On trouve un quotient de 23 alors qu'il vaut 27...
    Mon soucis c'est que quand je retrace à la main l'évolution de l'algorithme pour 1234/45, je ne trouve absolument pas ça... Il est vrai qu'il y a eu une correction entre temps mais je tombe sur 25 au lieu de 27, car la dernière valeur que prend qh est 46/9 = 5...

    donc je stock 0, 2, 5 soit 25...

    au lieu de 27. Cette implémentation est elle correct? si quelqu'un peut me dire ce qu'il trouve... merci.

    EDIT : je stock bien le résultat de u*d et v*d sous la forme u[m], u[m-1], ...

  2. #2
    Membre très actif Avatar de Gorzyne
    Profil pro
    Collégien
    Inscrit en
    Janvier 2008
    Messages
    337
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Collégien

    Informations forums :
    Inscription : Janvier 2008
    Messages : 337
    Par défaut
    ce code tel que rapporté est un peu erroné je suis en train de le corriger

    le piège c'est que l'algorithme sort un résultat correct dans la plupart des cas donc on peut être tenté de croire qu'il fournit le bon résultat tout le temps, mais en fait le passage dans la condition u<0 engendre le fait que u+v peut dans certains cas rester négatif, et puis il faut également préciser que u[x] = 0 quand x > longueur(u)

    je posterais une suggestion de correction quand j'aurai fini de résoudre le sujet

    Gorz

Discussions similaires

  1. Algorithme de division ou de modulo sur grands nombres
    Par méphistopheles dans le forum Algorithmes et structures de données
    Réponses: 40
    Dernier message: 13/06/2019, 14h58
  2. Optimisation des opérations sur les grands nombres, algorithme de Knuth
    Par Jackyzgood dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 21/10/2010, 20h27
  3. Réponses: 4
    Dernier message: 03/01/2009, 14h15
  4. Algorithme de division de grands nombres.
    Par Jack_serious dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 03/11/2005, 15h09

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