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