Projet : calculette à nombre entiers infiniment GRAND

Bonjour,


----------------------------------
Analyse du Problème :
----------------------------------

Voila, ce sont les vacances, et pour me perfectionner, j'essaie de faire un sujet qui est demande a des etudiants de EPITA : "Créer une calculette, en language C, qui peut faire les operations + - / * sur des nombres infiniment grands (TRES GRAND disons.), et dans toutes les bases"

Difficulté : Doit prendre en compte les parenthèses : ex : (3+4) * 5
Simplicité : Que des nombres entiers (pas de décimal)
Précision : Les calculs a effectuer, devront auparavant etre lus dans un fichier texte (donne en entre au prgm).
Fonctionalité supplémentaire : Calcul possible dans toutes les bases : (2, 3,4...16)
Intêret : Faire la calculette la plus rapide possible.

Alors, j'ai analysé plusieurs choses et j'ai retenu ca :

- RPN : notation Polonaise (utilisation de la structure PILE)
cf wiki : http://fr.wikipedia.org/wiki/Notation_polonaise_inverse

- dc : Calculatrice UNIX, qui je pense, fait exactement ce que je veux!
cf DOC GNU : http://www.gnu.org/software/bc/manua...l_mono/dc.html

- algo de Karatsuba : technique de la multiplication croisé, pour calculer plus vite.


-----------------
MES QUESTIONS
-----------------

1/ Pour des nombres très grands, comment je les stock en mémoire ?
CAS : Si le nombre est plus grand que un int (qui fait en mémoire fait 4 OCTETS).
Donc si mon nombre fait 10 OCTETS, ça se passe comment ?

2/ Alors, est il plus rapide d 'utiliser une structure de type PILE ou ARBRE BINAIRE ?
Si le calcul prend en compte les parenthèses, je pense que la structure en ARBRE devrait aidé ? Vrai ou faux ?

3/ Il faut que se soit possible de faire le calcul dans toutes les bases, donc quelle méthode utilisé ?
Me faut il une méthode de + * / -, généralise à toute les base ?

4/ J'aimerais, en fait, pour m'aider arriver a refaire le prgm de DC (très ancien sur système UNIX).
Est ce une bonne idée ? Quelqu'un ne connaitrait il pas un tutoriel pour me permettre de le refaire, ou alors, quelle méthode utiliseriez vous pour refaire un prgm, dont vous avez les sources, et que vous voulez comprendre ?

5/ Tous liens, tutoriels sur ce sujet est la bienvenue...


MERCI (c'est un peu long désolé !)

Cordialement,
REGNOULT AXEL

Citation:

---

1/ Pour des nombres très grands, comment je les stock en mémoire ?
CAS : Si le nombre est plus grand que un int (qui fait en mémoire fait 4 OCTETS). Donc si mon nombre fait 10 OCTETS, ça se passe comment ?

---

Sur les types de bases, les opérations { +, -, *, / } sont déjà implémentée.
Si on doit utiliser des tableau d'entier pour représenter des nombre "très grands", il va falloir coder ces opérations de bases.
Imaginons coder les entiers sous la forme d'un tableau de 3 entiers, l'addition de la partie basse pourra générer une retenue qu'il faudra propager sur l'addition de la partie médiane.
Cela étant pourquoi représenter ces entiers par une représentation de taille fixe (un tableau de 3 entiers), plutôt qu'un tableau de longueur variable?

Citation:

---

2/ Alors, est il plus rapide d 'utiliser une structure de type PILE ou ARBRE BINAIRE ?
Si le calcul prend en compte les parenthèses, je pense que la structure en ARBRE devrait aidé ? Vrai ou faux ?

---

L'expression (3+4) * 5 se représente mieux sous forme d'arbre mais transformer cela en *(+(3,4),5) ou en ((3,4)+,5)* lors de l'analyse lexicale est assez simple aussi.

Citation:

---

3/ Il faut que se soit possible de faire le calcul dans toutes les bases, donc quelle méthode utilisé ?
Me faut il une méthode de + * / -, généralise à toute les base ?

---

Il faut distinguer la représentation interne (tableau de 3 entiers) dans laquelle vous faites les calcul et les "interfaces" qui vous permettront de lire ou d'afficher un nombre dans sa représentation décimale, hexadécimal,...

Citation:

---

4/ J'aimerais, en fait, pour m'aider arriver a refaire le prgm de DC (très ancien sur système UNIX).
Est ce une bonne idée ? Quelqu'un ne connaitrait il pas un tutoriel pour me permettre de le refaire, ou alors, quelle méthode utiliseriez vous pour refaire un prgm, dont vous avez les sources, et que vous voulez comprendre ?

---

DC est très bien.
Par contre, il se réduit à lire en notation polonaise inversée... Ce qui n'est peut être pas ce qu'on vous demande.
- W

Hai,

Tout cela est à couper en plusieurs parties :

- Calcul sur des entiers de précision quelconque. À faire en premier apparemment, sinon la calculatrice ne pourra pas répondre au cahier des charges.
Sans être complexe, ce n'est pas si trivial si la performance est impérative (mais on peut faire une première version qui marche, et on pourra améliorer quand le reste fonctionnera)

- Interpréter une ligne de commande (ou une ligne prise dans un fichier, peu importe).
Ça traîne un peu partout.

- Le problème des différentes bases est un simple problème d'affichage/lecture.
Ça se fait les doigts dans le nez, les yeux fermés, en écoutant un discours de "qui vous voulez" sur une musique de Pink Floyd. :)

- Karatsuba, c'est bien d'y avoir pensé, mais il en est d'autres, plus ou moins efficaces selon la taille des nombres à traiter (pour un calcul qui cherche a être optimal, il convient d'en implémenter plusieurs, et de lancer le calcul le plus efficace en fonction des données, sachant que les limites fluctuent avec le processeur [type, fréquence, taille du cache...]).

Bref, bon courage. :)

Bonsoir,

Alors, voila, désolé de changer un peu de sujet, mais en fait, j'ai un problème avec la programmation. Je sais pas, c'est comme si j'avais peur de me lancer, de ne pas savoir quoi faire. J'ai peur de développé quelque chose qui n'ait pas de sens, ou de trop me compliqué l'esprit, et donc de faire 1000 fois trop dure (et donc de perdre du temps et de l'énergie)...

A part ce problème psychologique (revenons au sujet):

Je ne visualise pas, le fait de différencier la représentation interne des chiffres de leurs interface ("le simple affichage").
Par exemple si je lit le nombre en binaire : 1111111 + 1010
et bien deja 1+1 en binaire, ca fait pas 2, ca fait 0 et je retient 1.

Donc ce n'est pas le même calcul (donc la représentation interne si je ne me trompe pas) que quand je fais 1+1=2 en base 10.
Voila pourquoi je bloque. LE pire, c'est que je sais que c'est en relation avec le fait que tous les nombres dans la machine sont sous forme BINAIRE.

Ensuite, je pensais, que si je ne connaissais pas la taille des nombres (très grand), il faudrait faire des déclarations de tableau DYNAMIQUE. Pas vrai ?
Je propose donc de lire le nombre de chiffres du nombre, d'en déduire le nombre d'octets, et donc le nombre de "int" de mon tableau. Est ce cela ?

Désole, j'suis pas doué pour la simplicité, d'ou ma nullité en algo.

AX

Citation:

---

Alors, voila, désolé de changer un peu de sujet, mais en fait, j'ai un problème avec la programmation. Je sais pas, c'est comme si j'avais peur de me lancer, de ne pas savoir quoi faire. J'ai peur de développé quelque chose qui n'ait pas de sens, ou de trop me compliqué l'esprit, et donc de faire 1000 fois trop dure (et donc de perdre du temps et de l'énergie)...

---

Il faut commencer par réfléchir sur papier, crayon après le code c'est "simple"... et puis le but de l'exercice est bien que vous puissiez être plus à l'aise avec tout çà après?

Citation:

---

Je ne visualise pas, le fait de différencier la représentation interne des chiffres de leurs interface ("le simple affichage").
Par exemple si je lit le nombre en binaire : 1111111 + 1010
et bien deja 1+1 en binaire, ca fait pas 2, ca fait 0 et je retient 1.

---

Un langage de programmation définit des types de base comme les entiers, les chaines de caractères,... et offre des méthodes pour convertir des chaines de caractères en entier et réciproquement.

Un entier comme un caractère sera représenté comme une suite de 0 et de 1 mais le langage de programmation permettra de les manipuler comme abstraction d'entiers ou de caractères.

Citation:

---

Ensuite, je pensais, que si je ne connaissais pas la taille des nombres (très grand), il faudrait faire des déclarations de tableau DYNAMIQUE. Pas vrai ?
Je propose donc de lire le nombre de chiffres du nombre, d'en déduire le nombre d'octets, et donc le nombre de "int" de mon tableau. Est ce cela ?

---

yup soit N il va falloir l'écrire en base B comme:

x0 + B * x1 + B^2 * x2 + ... + B^n * xn

ou B sera choisi comme un "int" ou un "long".
- W

Bonjour,

Voila, je remercie Wiztricks et Droggo pour leur aide.
Je vais, déja bien me poser sur un papier, après je reviendrai poster.

merci.

Lorsque vous serez un peu plus clair sur ce que vous voulez faire, n'hésitez pas à regardez les projets OpenSource qui implémentent tout ou partie de vos besoins. Il y en a qui implémentent la gestion d'entiers et de flottant arbitrairement long pour le calcul scientifique qui pourraient 'aider'.
Bon il est possible que le but de votre excercice soit justement de faire cela, mais sans pour autant "copier", vous pourriez regarder comment certains des problèmes que vous allez rencontrer ont déjà été résolus.
Bon courage
- W

As-tu le droit d'utiliser une bibliothèque telle que GMP pour les calculs avec les grands nombres ? Sur le plan des performances, ça peut être intéressant.

Thierry

Bonsoir,

Alors, merci pour cette bibliothèque GMP, c'est une très bonne info, mais non, je pense ne pas l'utiliser en fait, car je préfèrerais moi même développer les fonctions.

J'ai déjà bien analysé mon sujet, et j'ai quelques réponses :

OBJECTIF 1 : Parser le fichier (donc récupérer la chaine de caractère)
OBJECTIF 2 : Remplir l'arbre binaire
OBJECTIF 3 : Effectuer le calcul dans la base demandée

Et maintenant, je vous pose mes questions, en fonction de ma méthode de résolution :

RÉSOLUTION OBJECTIF 1 :
--------------------------------
J'ai pensé faire ca : "je stock ma chaine de caractère dans une pile" Pourquoi une pile, car comme je ne connais pas la taille de la chaine de caractère, je n'ai qu'à lire a coups de : "cin.get(c)" et empiler chaque caractères progressivement.

1/ Comment feriez vous, pour parcourir une chaine de caractère, dont vous ne savez pas la longueur, pour ensuite la stocker dans un tableau ? (Alors moi je pense la parcourir 2 fois, ou utiliser comme on me l'à conseillé un algorithme récursif (Mais je ne sais pas du tout comment le faire.))
Ou alors, ais je bien raison d'utiliser mon idée de PILE ?

2/ Le parcours d'une pile sera il plus long que celle d'un tableau ? Et si oui, de beaucoup, ou pas trop ? Type de comparaison (n), (n^2), (log(n)) ?

3 / Quelle est la meilleure structure "pile" qui existe ? (J'allais dire comme celle de la STL ? Mais je suis en C, donc la STL c est pour le C++ c'est ca ? Ça ne marchera pas sous C, ce que je veux dire ?)

RÉSOLUTION OBJECTIF 2 :
--------------------------------
Alors, merci internet, voila ma super aide :
http://recursivite.developpez.com/?page=page_8
Qui dit comment faire un arbre binaire évaluant une expression arithmétique.

1/ Idem, quelle serait la meilleur source possible, pour utiliser un arbre binaire en C. (C'est pas que j'ai pas envie de la faire, mais je veux la plus performante.)

RÉSOLUTION OBJECTIF 3 :
--------------------------------
J'y suis pas encore.




Voila, à part cela, j'ai essayer d'utiliser la pile d'écrite par ce lien :
http://nicolasj.developpez.com/articles/pile/

Et je m'excuse, mais en fait je n'arrive pas à tester la classe. J'ai fais ceci :

/*main.c*/

struct stack_s **pile;
pile = (*pile)->stack_new(void);


Enfin, j"ai essayer pleins d'autres truc, mais l'erreur qui revient c'est le :
(sous GCC : error : incomplete type)
-> "Vous essayer de dérefencez un type incomplet"

Donc, merci, surtout, n'hésitez pas à répondre petit à petit, car je mélange souvent un peu tout...

Merci.

Si j'avais à faire cela, je me serais donné d'autres taches:
1 - fabriquer un calculette qui effectue les opérations arithmétiques demandées avec des types simple (int).
2 - construire une représentation des entiers arbitrairement longs et implémenter les opérations de bases à effectuer dessus { +, -, *, / }
3 - remplacer les (int) par les objets construits en (2).

Je découperais 1 en
1a - lecture dans les différentes bases et stockage dans un (int)
1b - affichage dans la représentation demandée
1c - analyseur des expressions arithmétiques à évaluer

Puis je découperais 1c en...
Mais c'est vous qui voyez;)

Citation:

---

J'ai pensé faire ca : "je stock ma chaine de caractère dans une pile" Pourquoi une pile, car comme je ne connais pas la taille de la chaine de caractère, je n'ai qu'à lire a coups de : "cin.get(c)" et empiler chaque caractères progressivement.

---

Ce que vous lirez seront des nombres séparés par des opérateurs { +, ...} ou des parenthèses ().
Un nombre commence par un caractère dans 0-9 et se termine par quelque chose qui n'est plus dans 0-9.
Sans connaitre la taille vous pouvez stocker la suite de 0-9 dans un buffer 'suffisament' grand et le stocker comme vous voulez après.
=> parcourir deux fois l'entrée, une pour la stocker et une 2ème pour la coder dans la représentation.

Citation:

---

1/ Comment feriez vous, pour parcourir une chaine de caractère, dont vous ne savez pas la longueur, pour ensuite la stocker dans un tableau ? (Alors moi je pense la parcourir 2 fois, ou utiliser comme on me l'à conseillé un algorithme récursif (Mais je ne sais pas du tout comment le faire.))
Ou alors, ais je bien raison d'utiliser mon idée de PILE ?

---

Séparez les problèmes lecture et stockage.
Si vous stockiez la suite de 0-9 lues dans un entier, vous le feriez sans pour autant connaitre sa longueur...
Vous ne savez pas plus la longueur de votre entier arbitrairement long, sinon que vous ne pourrez pas le stocker de la meme façon.

Citation:

---

RÉSOLUTION OBJECTIF 2 :
--------------------------------
Alors, merci internet, voila ma super aide :
http://recursivite.developpez.com/?page=page_8
Qui dit comment faire un arbre binaire évaluant une expression arithmétique.

1/ Idem, quelle serait la meilleur source possible, pour utiliser un arbre binaire en C. (C'est pas que j'ai pas envie de la faire, mais je veux la plus performante.)

---

Très bien l'article...
Maintenant réfléchissons un peu.
Lorsqu'on évalue (3 + 4) * 5, est ce qu'on va construire l'arbre complètement ou est-ce qu'on va evaluer des expressions?
Evaluer des expressions signifie que lorsqu'on rencontre ")" on pourra calculer le résultat 7 sans avoir lu * 5 (et donc sans avoir construit d'arbre en tant que représentation).
- W

Pour illustrer ce que j'entend par evaluer les expressions.

Imaginons que nous ayons a faire une calculette qui ne sache que faire des additions et des soustractions d'entiers positifs.
La première chose à faire est une grammaire. Ca donne:

• entier := 1-9(0-9)*
• expression := entier (('+' entier) | ('-' entier))*

Ca dit qu'un entier est un chiffre compris entre 1 et 9 suivi d'un nombre quelconque de chiffres entre 0 et 9. Puis, çà dit qu'une expression est un entier éventuellement suivi par la répétition indéfinie d'un '+' ou d'un '-' et d'un entier.

Si on fait l'impasse sur la gestion d'erreurs, l'acceptation de caractères comme les espaces,... La calculette correspondante est implémentée dans le petit programme ci dessous:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

# include <iostream> using namespace std; const char EOL = '\n';   int lire_entier() { char c; int value = 0; do { cin.get(c); if (c >= '0' && c <= '9') value = 10 * value + c - '0'; } while (c >= '0' && c <= '9'); cin.putback(c); return value; }   int expression() { char c; int v = lire_entier(); while (1) { cin.get(c); if (c == EOL) break; switch (c) { case '+' : v = v + lire_entier(); break; case '-' : v = v - lire_entier(); break; default : cout << "expected +,- got /" << c << "/\n"; exit (1); } } return v; }   int main () { int v; char c; while (! cin.eof()) { v = expression(); cout << v << endl; cin.get(c); } }

---

Pas besoin d'avoir une représentation de l'expression sous forme d'un arbre binaire, on évalue au fur et à mesure que les unités sémantiques sont complètes : l'arbre est caché dans la pile d'exécution du programme.

Ajouter les opérations * et / et la gestion des parenthèses, donne une grammaire de la forme:

• entier := 1-9(0-9)*
• group ::= '(' expression ')'
• factor ::= entier | group
• term ::= factor (('*' factor) | ('/' factor))*
• expression ::= term (('+' term) | ('-' term))*

Elle n'est pas plus compliqué à coder que la précédente: on aura des fonctions en plus group, factor, term,... mais on les écrira de la même façon.

-W

Il faut que tu te fasse un plan plus structuré.
Ce projet s'apelle la bistromatique (calculatrice infini), elle pour but de savoir bien utilisé le parsing et le jeu de chaines de caractères.

Le but est donc de pouvoir faire les calcules sur des chaines de caractères.
Commence par faire des trucs simple du genre 35+47 (une chaine avec 35, une autre avec 47, ensuite faire le calcules graces au codes ascii).

C'est quelque chose de long et dure pour un débutant (surtout la gestion des bases sur les chaines de caractères).

Gae,

Citation:

---

Envoyé par stevin

Il faut que tu te fasse un plan plus structuré.
Ce projet s'apelle la bistromatique (calculatrice infini), elle pour but de savoir bien utilisé le parsing et le jeu de chaines de caractères.

Le but est donc de pouvoir faire les calcules sur des chaines de caractères.
Commence par faire des trucs simple du genre 35+47 (une chaine avec 35, une autre avec 47, ensuite faire le calcules graces au codes ascii).

C'est quelque chose de long et dure pour un débutant (surtout la gestion des bases sur les chaines de caractères).

---

Il ne faut surtout pas calculer sur les chaînes de caractères !!

Pour la performance, il faut faire les calculs sur le plus grand mot utilisable en natif par le processeur (32 bits, 64 bits...)

Les chaînes ne sont qu'une visualisation des valeurs, et il suffit d'écrire la traduction données <==> chaîne dans les différentes bases à visualiser/lire.

Cela a de plus l'immense avantage de ne nécessiter qu'une manière de calculer. :)

Yop,

Citation:

---

Il ne faut surtout pas calculer sur les chaînes de caractères !!
Les chaînes ne sont qu'une visualisation des valeurs

---

Oui bien sur que les chaines de caractères ne sont qu'une représentation du nombre.
après on va biensur parser le char* pour avoir chaque caractère (donc nombre) et ainsi faire une opération avec...
Donc il n'y a que des petites opérations au final, mais il y en a beaucoup c'est tout.

Pour avoir fait le projet, le plus dur réside dans le fait que c'est un projet de 1ere année d'école et quand on débute c'est pas très facile.

A+