Discussion :

[ToadD]

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

[Gorzyne]

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