[Wax-Reggea]

Yo le Lab',

Je viens vous voir car il faut que je recode (en C) l'algo de Knuth sur les divisions de grands nombres mais hélas j'y capte rien. Sur le net, il le décrive comme ça, mais c'est encore pire...

Citation :

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]
if (qh = B ou qh*v[n-2] > rh*B + u[j+n-2])
{
qh = qh-1
rh = rh +v[n-1]
if (rh < B && qh*v[n-2] > rh*B + u[j+n-2])
{
qh = qh -1
rh = rh + v[n-1]
}
}
u = u - qh v B^j
if (u < 0)
{
u = u + v
qh = qh - 1
}
q[j] = qh
}

Ce que j'ai compris :
u : dividende
v : diviseur
d : un facteur (utilité ?)
n : longeur de v
m : longeur de u
B : la base (je pars sur une base 10)

Enfaite, ce qui m’empêche de comprendre le truc, c'est que je vois pas qu'est ce que j et ce que signifie exactement "Pour j de m à 0 par pas de -1". Si quelqu'un pourrait m'éclairer, cela serait top !
Merci par avance !

[Veilugarux]

j est un nombre.
S'il s'appelle j c'est parce que c'est un nom classique de variable d'une boucle (en général c'est i d'ailleurs).

j va de m à 0.
En effet, chaque tour de la boucle baisse la valeur de j de 1.


C'est comme une boucle normal, sauf qu'on va vers le 0 en partant du maximum.

Si tu comprend le C, c'est :

Code:

for (int j = m; j >= 0; j = j -1)

Si tu ne connais pas les boucles, http://fr.openclassrooms.com/informa.../les-boucles-1.

Pour l'algorithme en lui même je ne peut pas t'aider par contre.

[Gardien]

ca remonte à un certain temps... Mais si je me souvient bien...

Tu va itérer les "chiffres" / caractère de ton "grand nombre" 1 par 1 en commençant par le plus haut rang (genre pour 1234, tu commence par 1 et tu fini par 4).

[Chernish]

Ca ressemble énormément à la division comme on l'apprend à l'école. On commence par la fin du numérateur et on soustrait au fur et à mesure.

Il y a une différence cependant: on estime le quotient en utilisant le premier chiffre du dénominateur. C'est la partie qh = {(u[j+n]B + u[j+n-1])/v[n-1]}

Ensuite on regarde s'il y a des problème de reste avec les chiffres suivants. Ce sont les deux "if".

Le facteur "d" sert à avoir un premier chiffre du diviseur le plus grand possible, afin d'avoir une précision plus grande. Si on avait pas ce facteur d, il faudrait plus que deux "if".

Par exemple si je divise par 100 par 19 avec cette méthode, sans facteur d, j'ai:
qh=10/1=10 -> premier if qh=10-1=9 ->second if qh=9-1=8, et donc 100/19=8. Ce qui est faux, évidemment.
Par contre si je multiplie par 5 j'ai 500 divisé par 95:
qh=50/9=5. C'est ok.

[Wax-Reggea]

Ok ok, ça devrait le faire au final, merci bien tous le monde