Classe d'entiers tres grands

Salut les developpeur,je suis etudiant en 3eme année ingénierie informatique.
notre prof de c++ nous a demander d'inplementer une classe representant des entier tres grand non supportée par des int qui est represente sur 32 bits,par exemple des nombres du genre (987321412365974219562132),un nombre de 24 chiffre.

Cette classe,je doit la realiser heritante d'une classe tableaux dynamique que j'ai deja realiser qui contient entre autre un constructeur ,des methode telle que inserer,supprimer ,rechercher...

cette classe je vais l'appeler mpi(multiple precision integer).
je dois realiser un constructeur pour la classe qui construira un entier long ,par exemple
mpi x(987321412365974219562132);

je doit réaliser les opérateurs suivants:
mpi operator+(mpi& );
mpi operator-(mpi& );
mpi operator*(mpi& );
mpi operator/(mpi& );

ma question est comment stocker le nombre 987321412365974219562132 dans la variable x en utilisant des tableaux dynamiques?
et puis comment je peut effectuer les operations voulus sur des objet mpi?
merci d'avance pour vos réponse.

J'ai aussi le meme soucis je cherche aussi à realiser une telle class je pense que c'est un peu difficile ,, mais on attend toujours des reponses -_-

Pour résumer l'essence de ce qui a été dit sur le post de Devaben :

Tu ne peux pas construire a partir d'un grand entier :

Code:

---

mpi x(987321412365974219562132);

---

Par contre, tu peux le construire a partir de la chaine de caractère :

Code:

---

mpi x("987321412365974219562132");

---

Ensuite, en découpant la chaine en sous chaine,

Code:

---

"987321412365974219562132" -> "9873" + "21412" + "36597" + "42195" + "62132"

---

tu pourras convertir ces sous chaines en int (car la chaine est suffisamment petite pour être représenter par un int). Pour cela, tu peux utiliser std::istringstream. Il reste a remplir ton "tableau dynamique" avec ces entiers.

Pour les opérations +, *, ... : implémente les opérateurs adaptees : operator+(...), operateur*(...), ...

Une remarque : pourquoi faire une dérivation du tableau dynamique. Il est plus simple que ta classe mpi contiennent un tableau d'entier.

Et je me répéte... pourquoi découpé? Tu remplis directement tes cases avec les cases de ta chaine de caractères, c'est direct... Ah noté que il n'a jamais était question d'entiers négatifs... Il vous est précisé explicitement dans l'énoncé que c'est une classe d'unsigned ?

salut je suis de retour ,donc selon vous "Solkien", je dois saisire le grand nombre et le programme la lis comme chaine de caractere,donc mon costructeur sera en quelque sorte comme cela(juste le debut):
mpi::mpi (char* c)
{
}
Et pour le decoupage du nombre:
pour stocker ce nombre il me faut allouer un tableaux de 5 case c-à-dire 5 int,
"987321412365974219562132" -> "9873" + "21412" + "36597" + "42195" + "62132"?
mais je n'ai pas comprit comment faire cela en utilisant istringstream,expliquer moi plus s'il vous plais.
pour l'heritage c'est le prof qui nous l'a exigé,je pense il veut savoir si on a bien metriser ses technique.

pour repondre à Goten,oui on nous a précisé de travailler avec des unsigned int,et j'ai pas compris l'idee de (Tu remplis directement tes cases avec les cases de ta chaine de caractères, c'est direct).
maerci pour vos reponse.

http://www.developpez.net/forums/m4164619-15/


Le principe c'est qu'il faut que chaque case de ton tableau contienne un int n tel que :

0<=n<=9

Ainsi chaque cases de ton tableau représente un chiffre de ton long long nombre.

imaginant sue ma classe de tableau dynamique s'appelle array,
la classe mpi je doit la consevoire heritante de array donc je fais :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class array { unsigned int *t; int dim;//dimension du tableau dynamique public: void inserer( unsigned int valeur);//methode pour inserer des valeur dans le tableau int& operator[](int i);//pour retourner la valeur t[i] ... }; class mpi:public array { mpi(); ... };

---

je pense que je doit utiliser cette methode inserer pour construire mon objet mpi,par ex si mon entier nécessite 12 octets pour etre stockée il faut construire un tableau de 3 cases,chaque case contient un int(on repartit l'entier long sur le cases du tableau).
je pense que si je saisie un entier tel que 2458930218985210029859845621
le constructeur doit decouper se monstre en des entier stockable,
t[0]contiendra 859845621
t[1]contiendra 985210029
t[2]contiendra 2458930218

pour le code que vous m'avez envoyer
code:

Code:

---

1 2 3 4 5 6 7 8 9

int i = 0;   while(tonEntierAdecouper >= 0) { tonMint[i] = tonEntierAdecouper%10; tonEntierAdecouper /= 10; ++i }

---

j'ai pas comprit son fonctionnement pourquoi le modulo?

Ca permet de découpé ton entier selon chacun des chiffres qui les composent. C'est pour une solution utilisant un entier inclus entre [0;9] comme je te le disais.


Maintenant si je suis ta méthode (ie des entiers de type xxxxx dans plusieurs classes), déjà quelle taille va tu prendre comme taille maximale dans chaque case?? la taille d'un entier?

alors maintenant va plus loin dans le code et réfléchi comment tu peux codé ton opérateur * ? Avec ma méthode tu multplies chaque cases puis si le résultat est supérieur à 9 tu gardes une retenu.
Maintenant avec ta méthode si tu multiplies chaque case, ton entier risque de débordé de la capacité maximale d'un entier non?

Goten, il serait pas mal de typer tes exemples.

Dans

Code:

---

1 2 3 4 5 6 7 8 9

int i = 0;   while(tonEntierAdecouper >= 0) { tonMint[i] = tonEntierAdecouper%10; tonEntierAdecouper /= 10; ++i }

---

que sont tonMint et tonEntierAdecouper ?

Si tonEntierAdecouper est un entier, on est mal barre pour contenir le gros entier.
Si tonEntierAdecouper est une chaine de caractère, je ne savais pas que l'on pouvait appliquer les opérateurs % et / a une chaine de caractère.
Si c'est autre chose, merci de le préciser.

De même,
si tonMint est un tableau d'entier, c'est pas top de stocker dans un entier des nombres compris entre 0 et 9 (surtout lorsque des retenus demanderont de modifier tous les éléments du tableau).
si tonMint est un tableau de chaine de caractère, ca ne sera pas top quand il s'agira d'additionner et de multiplier.
Si c'est autre chose, merci de le préciser.

Marbouchi, tu as le droit de regarder dans la FAQ comment utiliser istringstream...

il me semblait que les noms étaient assez parlant... il semblerait que non...
donc :

Code:

---

1 2 3

Mint tonMint; // c'est le nom de la classe qu'il doit codé... int tonEntierAdecouper;

---

Mes deux codes sont a utilisé dans les constructeurs prenant en argument soit une chaine de caractères soit un entier... ce qu'il demandé à l 'origine.


Pour ce qui est du systéme de stockage... la solution la plus répandue dans ce genre d'exercice c'est d'utiliser un std::vector<int> où chaque int est compris entre 0;9...

Ainsi chaque chiffre est représenté par une case. Et ça simplifie grandement l'implémentation des opérateurs derrière.
Maintenant si tu penses pouvoir faire mieux (ie plus rapide) je suis tout ouïe.

bonjour,
donc selon vous pour stocker un nombre de 21 chiffres j'alloue un tableau dynamique de 21 cases et j'insère chaque chiffre dans une case,il n'y a pas une autre solution optimale?

Ca se réfléchit en fait... j'avais pas fait gaffe à ton implémentation de ton array... Moi je parlais dans le cas d'un std::vector<int>... Mais après si tu stocks des entiers de taille supérieur à 10 dans les cases, ça va être un très gros casse têtes pour toute opération.

Goten, je n'arrive pas a te suivre.

Tu dis que tonEntierAdecouper est un entier. Mais une des difficultés de ce projet est de prendre en entrée de grands entiers. Ces entiers sont tellement grands qu'il ne rentre pas dans un int (et plus généralement dans aucun type primitif).

C'est pour cela qu'une solution est de prendre en entrée un chaine de caractère potentiellement tres grande. Dans ton cas, tu découpe un int (qui par définition n'a pas besoin d'etre découper) en d'autres entiers plus petits.

Marbouchi : si tu veux un code simple, utilise le principe de Goten qui consiste a considérer un vecteur d'entier compris entre 0 et 9. Tu as une relation très simple entre cette représentation et sa représentation en base 10.
Si tu veux un code efficace, il est beaucoup plus efficace de travailler dans une base tenant dans un mot machine. Si cette valeur est B, tu auras un vecteur d'entier compris entre 0 et B-1. Ton grand entier vaudra alors :
Mint[0] + B*Mint[1] + B^2*Mint[3] + ...
Mais si tu veux afficher ton entier, il faudra travailler pour le convertir vers la base decimal.

Je tiens tout de même a préciser : Goten, tu dis que manipuler une base décimale est la plus utilisée. C'est peut être vraie pour les personnes qui apprennent le langage, mais aucune classe de grands entiers sérieuses ne travaille en base décimale (tu troques une facilite d'implémentation (qui est surtout une facilite mathématique) contre une très grosses pertes de performances). A la limite, tu peux travailler dans une base B avec B la plus grande puissance de 10 qui tient dans un type primitif d'entier (int, long, ...).

Bonjour,

La première solution qui me viens a l'esprit est des traiter n'importe quel nombre en chaine de caractère (char * ou string), qui soit petit ou pas.

Après c'est à toi de faire les fonctions membres de ta classe pour faire en sorte que les opérations usuelles paraisse transparente ( +, - , / , *....etc).

Citation:

---

Envoyé par Solkien

Goten, je n'arrive pas a te suivre.

Tu dis que tonEntierAdecouper est un entier. Mais une des difficultés de ce projet est de prendre en entrée de grands entiers. Ces entiers sont tellement grands qu'il ne rentre pas dans un int (et plus généralement dans aucun type primitif).

C'est pour cela qu'une solution est de prendre en entrée un chaine de caractère potentiellement tres grande. Dans ton cas, tu découpe un int (qui par définition n'a pas besoin d'etre découper) en d'autres entiers plus petits.

---

Seulement il est aussi traditionnel d'avoir un constructeur prenant en compte un entier.. Pourquoi? parce qu'il arrive souvent d'avoir un entier en entrée PUIS d'avoir des opérations à effectuer dessus qui feront un dépassement de capacité de l'entier. Enfin, ça permet de faire des conversions (implicite celà dit), dans des cas où tu écrirais par exemple:

Code:

---

tonMint + unEntierQuelconque // ici le constructeur prenant un entier est appelé implicitement

---

Citation:

---

Envoyé par Solkien

Marbouchi : si tu veux un code simple, utilise le principe de Goten qui consiste a considérer un vecteur d'entier compris entre 0 et 9. Tu as une relation très simple entre cette représentation et sa représentation en base 10.
Si tu veux un code efficace, il est beaucoup plus efficace de travailler dans une base tenant dans un mot machine. Si cette valeur est B, tu auras un vecteur d'entier compris entre 0 et B-1. Ton grand entier vaudra alors :
Mint[0] + B*Mint[1] + B^2*Mint[3] + ...
Mais si tu veux afficher ton entier, il faudra travailler pour le convertir vers la base decimal.

Je tiens tout de même a préciser : Goten, tu dis que manipuler une base décimale est la plus utilisée. C'est peut être vraie pour les personnes qui apprennent le langage, mais aucune classe de grands entiers sérieuses ne travaille en base décimale (tu troques une facilite d'implémentation (qui est surtout une facilite mathématique) contre une très grosses pertes de performances). A la limite, tu peux travailler dans une base B avec B la plus grande puissance de 10 qui tient dans un type primitif d'entier (int, long, ...).

---

Je suis tout à fait d'accord, et c'est justement pour ça que j'ai parlé de la plus utilisée, c'est par rapport à ce contexte, apperemment le posteur débute en C++, donc la représentation la plus simple et la plus rapide était la plus adéquate amha.
Surtout qu'à mon avis ce n'est qu'un exercice, ça n'a pas un but final d'être utilisé en production. Donc autant ce focalisé sur les détails purement C++ que sur des considérations de l'ordre de la vitesse ou autre.
Mais après je te l'accorde dans un code visant à être utilisé intensivement la représentation que j'ai donné n'est vraiment pas approprié, mais de toute façon pour ce genre de chose je n'irais pas réinventé la roue et j'utiliserais GMP par exemple..

D'accord pour le constructeur qui prend en entrée un entier. Mais la question de Marbouchi, c'était :

Citation:

---

je dois réaliser un constructeur pour la classe qui construira un entier long ,par exemple
mpi x(987321412365974219562132);

---

Ensuite, avoir une implémentation ridiculement lente, c'est pas top pour un projet scolaire. A mon sens, utiliser des algorithmes rapides quand c'est nécessaire fait partie des difficultés d'un projet informatique. A Marbouchi de savoir si il s'agit d'un exercice de style ou d'un projet.

Vu les questions posée il s'agit bien d'un exercice de style. (il demandé comment implémenté les opérateurs).


Pour le constructeur : Ce qu'il a donné est faux ça ne compilera pas car le compilo va essayer de le casé dans un int et d'appelé le constructeur prenant un paramètre entier.
Vu qu'après il donnait quelque chose de ce type :
mpi x("987321412365974219562132");

j'ai assumé que c'était une erreur de sa part et qu'il parlait bien d'un entier..

ps : une fois bien implémenté je suis pas sur que ça soit 'ridiculement' lent... (surtout de nos jours avec les pc que l'on a.)

Bref en l'attente du PO on peut que supposer/

salut a tous j'ai commencer a implementer ma classe avec un heritage d'un vecteur dynamique ,j'ai ecrit un constructeur qui construit mon entir tres long à partir d'une chaine de caractere

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

mint::mint(char* c):array(strlen(c)) {   int pos=0;   for(int i=0;i<strlen(c);i++) { inserer(c[i]-'0',pos); pos++;   }   }

---

et ça marche tres bien et j'zi developper l'operateur +.
merci pour votre aide.
au debut je me comliquait la vie en voulant inserer toute une partie de mon mint dans une case pour utiliser le moins possible d'octet.

Oui c'est un peu ca si c possible montre nous les deux classes avec leurs methodes et aussi la fonction d'affichage