Discussion :

[marbouchi]

Salut à tous,j'ai besoin d'aide s'il vous plais.

Je suis en train de developper une classe d'entiers très grands,j'ai réaliser les opérateurs + , * , -.Mais je bloque pour l'opérateur / .

Mon entier est construit de la façon suivante :
le programme lit une chaine de caractére "126548654154848634"
et puis stock cette chaine dans un tableau d'entier,avec chaque case du tableau contient un nombre de 0 à 9999 .

Donc mon entier sera comme suit 12 6548 0541 5484 8634 stocké dans cinq cases .
Ma question c'est comment on peut faire une division tel que celle ci :

12 6548 0541 5484 8634 / 3970 8954 6101

Merci pour vos réponses.

[loufoque]

De la même façon qu'on t'a apprise en primaire.

[marbouchi]

D'accord c'est vrais que je dois faire une division classique comme pour des entiers normaux,mais ici l'algorithme est un peut délicat je croit.

le problème pour moi c'est comment manipuler les cases des deux tableaux pour arriver au résultat voulu,manipuler les restes,construire le quotient .

Est ce que je doit utiliser une récursivité?

[loufoque]

Suis un cours d'algorithmie de base. Ça n'a rien à voir avec le C++.

[Invité]

Salut,

La difficulté provient de la première étape de la division, quand il faut estimer le quotient ("combien il y va, comme on disait à la petite école..."). Knuth donne la méthode suivante (le détail se trouve au chapitre 4.3.1 de l'Art of Computer Programming, dans le second tome).

Le principe est de diviser les deux premiers nombres du dividende par le premier du diviseur, chez toi (en base 10000) diviser 126548 par 3970, et de prendre comme coefficient le minimum du quotient et de la base moins un (9999 chez toi).

Si tes nombres s'écrivent
u = u0 u1 u2 ... un
et
v = v0 v1 v2 ... vp
en base b (dans ton exemple b=10000, u0=12, u1=6548 etc...)

alors tu divises u0*b + u1 par v0, et si c'est supérieur ou égal à b, tu prends b-1. (Dans ton exemple, tu divises 126548 par 3970, et tu prends le minimum du quotient et de 9999, soit 31).

Si q est le résultat de ce calcul, alors on peut démontrer que la "bonne valeur" (le nombre que tu cherches) est égale à q, q-1 ou q-2... (Knuth donne un algorithme améliorant ce calcul).

Ici, le premier chiffre du quotient serait donc 31, 30 ou 29.

Comme tu sais faire la multiplication et la soustraction, la suite est simple :

1- tu multiplies q par v puis par la puissance de b qui convient, si c'est plus grand que les P+1 premiers termes de u tu en retranches v (et le quotient devient q-1), si c'est encore plus grand, tu retranches encore v (et le quotient devient q-2)
2- tu retranches ce produit des p+1 premiers termes de u, et tu recommences le même calcul avec le reste, sur un nombre maintenant plus petit. Tu t'arrêtes quand le reste est inférieur au diviseur.

Comme tu peux le voir, chaque étape du calcul implique une "division courte" (126548/3970), une multiplication longue (q*v) et entre une et trois soustractions longues (u-qv, et les deux soustractions de v le cas échéant). Diverses améliorations existent qui permettent de réduire la fréquence de ces soustractions supplémentaires, mais cela ne change pas l'algorithme.

Quant à l'implémentation, tu vas vraisemblablement avoir besoin d'un tableau intermédiaire (de taille p+1) pour calculer q * v, que tu retrancheras ensuite directement du dividende... Et d'un tableau additionnel (de taille n-p+1) pour stocker le quotient

Francois

[marbouchi]

Merci pour la reponse je vais y réfléchir et voir aussi ce qu'il ya dans ce livre
Art of Computer Programming .