Projet : calculette à nombre entiers infiniment GRAND

Question

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/manual/dc-1.05/html_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

cs_niky · Answer

Salut,

1/ Tu le stockes sur 3 entiers. C'est à toi de gérer les retenues qu'il peut y avoir lorsque tu vas faire une addition pour les passer du 1er entier au 2è, etc.

2/ Avec une notation post fixée, c'est une pile qui est préférable: tu dépiles les nombres jusqu'à trouver un opérateur et tu fais ton calcul. Avec la résulat, tu dépiles jusqu'à trouver un opérateur et tu fais ton calcul, etc.

3/ Je pense que ton calcul, tu le feras en binaire en utilisant les opérateurs natifs du C. Tu as simplement à gérer l'effet de bord entre 2 entiers (voir 1/). La base n'a d'importance que lorsque tu vas lire et afficher les données.

4/ Du temps et de la patience :-)... ou tout jeter et refaire par soi même, quitte à se tromper et à recommencer :-p

5/ De mon côté, j'ai développé ceci : http://tuxy2885.free.fr/?cat=labo&id=integer
C'est pas parfait, ni super optimisé mais ça marche pas mal. Ca permet de calculer sur de très grands nombres entiers dont tu fixes le nombre de bits au départ (par exemple 1024 bits, 4096, etc.)

Bon courage !

nzaeroax · Answer

Bonsoir,

Ok, merci pour ton fichier, je l'ai télécharger, je l'examinerais plus tard.

nzaeroax · Answer

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

cs_niky · Answer

Trop de questions tue la question :-)

1/ Si, comme tu l'as écrit tu es à la recherche de performances, parcourir 2 fois la chaîne sera une perte de temps.
Ce dont tu as besoin est de stocker des données dans un tableau dynamique (dont la taille grandit automatiquement au fur et à mesure qu'on y ajoute des éléments). La structure qui correspond à ça est une liste chaînée. Il se trouve que la pile est généralement implémentée sous forme de liste chaînée... donc parfaitement adaptée à recevoir ce type d'informations.
Pour lire l'expression arithmétique en entrée, tu vas lire des caractères (que tu vas concaténer pour faire une chaîne de caractères) et tu empiles cette suite quand tu tombes (par exemple) sur un espace ou la fin de fichier.

2/ Travailler avec une pile et un tableau est très différent et la complexité dépend des opérations à faire.
Si tu implémentes la pile sous forme de tableau, la complexité sera la même.
Si tu implémente la pile sous forme de liste chaînée, accéder à l'élément d'indice n se fera en un temps d'ordre O(n). Alors que sur un tableau elle est d'ordre O(1).
Ajouter un élément à la pile est d'ordre O(1) (idem pour la suppression). Pour un tableau, il te faut allouer un nouveau tableau plus grand, le recopier et ajouter ta nouvelle valeur : complexité en O(2n) => O(n)
Seulement, il faut voir qu'à priori, tu auras juste besoin d'empiler et de dépiler. Tu ne devrais jamais avoir besoin de faire un accès aléatoire à la liste chaînée.

3/ Une pile (sous forme de liste chaînée) en C ça ressemble grosso modo à ça  (le code ne fonctionne pas, il expose le principe. il pose notamment des probs au niveau du bas de la pile) :

struct Pile {
  void *valeur;
  struct Pile *precedent;
}

struct Pile* Empiler(struct Pile *p, void *v)
{
  struct Pile *p2 = malloc(sizeof(struct Pile));
  p2->value = v;
  p2->precedent = p;
  return p2;
}

struct Pile* Depiler(struct Pile *p, void **v)
{
  struct Pile *p2 = p->precedent;
  *v = p->valeur;
  free(p);
  return p2;
}

etc.

Tout ça pour te montre qu'une pile n'est pas compliquée à implémenter et qu'il est difficile de faire mieux.

4/ Je ferais plutôt comme ça :
struct stack *p = stack_new();
stack_push(&amp;p, &amp;v0); // v0 est une variable quelconque

nzaeroax · Answer

Bonjour,


rappel : le code est en C


Alors, j'essaie de m'appliquer sur la décomposition du sujet, et sur son organisation.


La calculette comprend 2 modules. (2 sous systèmes), l'un qui calcul l'expression, et l'autre qui l'analyse.


Je ne assez sure de ma méthode pour la version 1 de ma calculette,  qui
n'effectue que des calculs simples (+ et -). ex : 1+2-5+8+4+666-888.

Mais je bloque sur l'arrivée des priorités. (* / ())


J'appelle F.X, une fonction utile a son module. F1.1 sera la première
fonction implémentée, puis F1.2, celle améliorée qui la remplacera. etc
etc.


Je dois pourvoir tester chaque modules indépendamment des autres, sauf
lors du rendu final d'une version, qui a pour but de faire marcher
modules en même temps. (Vous comprendrez tout en bas)


MODULE 1 : le calcul

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||


F.1 - FAIRE LE CALCUL

-----------------------------------------

    F 1.1 - calcul sur des int (prise en compte des bases)

    prototype : int calculer (int operandeA, int operandeB, char operateur, int base)


    F 1.2 - calcul sur des nombres infiniment grands (piles)

    prototype : pile calculer (pile operandeA, pile operandeB, char operateur, int base)


REMARQUE : comme le nombre peut être très grand, il serait préférable
de ne pas le retourner par valeur (CAR RECOPIE DU TABLEAU). Donc il
faudrait mettre le résultat dans l'opérande A. (Je le passe par
référence)


MODULE 2 : la lecture dans le fichier et son analyse grammaticale

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||


F2 - LIRE LE CALCUL

-----------------------------------------

    F2.1 - Lire 1 Calcul (qui a un operateur et 2 operandes)

    prototype : vide lirePartieCalcul  (int & operandeA, int & operandeB, char & operateur, int & base)

     // donc, a la fin de la fonction lireCalcul, on a initialise les variables passe en paramètre

     // ex : 2+5+6+3 : on lit 2+5 et on s'arrête de lire.

     // Car pour continuer a lire il faut d'abord effectuer le calcul.


    F2.2 - Lire TOUS les calculs

     prototype : vide lireCalculEntier ()

     // on appelle plusieurs fois F2.1

     // ex : 2+5+6+3 : on appelle F2.1 qui lit (2+5) et on met le résultat dans l'opérande A.

     // Puis on appelle encore F2.1 qui lit ce qui suit : (+6)

     // et on met le résultat dans opérande A. etc etc...jusqu'à la fin de la ligne.


    F2.3 - lecture de nombre infiniment grand et initialisation des champs (pile)  

    prototype : lireCalcul  (pile operandeA, pile operandeB, char operateur, int base)

     // c'est F2.1 avec des piles


    F2.4 - lecture de nombre infiniment grand et initialisation des champs (pile)

    // c'est F2.2 avec des piles


F3 - ANALYSE GRAMMATICALE :

-----------------------------------------

    F3.1 - ?????????????????

    // ICI, je bloque, il faut que je réfléchisse : c'est ici, que je vais réussir a prendre en compte

    // les priorités de calcul. ( (), *, /, - unaire)


LIASON DE MODULE : (historique des différentes version de ma calculette)

---------------------------------------

version 1 - prise en compte de + et -

    version 1.1 - mettre F1.1 et F2.2 ensemble

    version 1.2 - mettre F1.2 et F2.4 ensemble


version 2 - prise en compte de * / (- unaire) et des parenthèses

    version 2.1 - TODO : FAIRE LA CONCEPTION. JE NE SAIS PAS.


Voila, alors, voues êtes pas oblige de tout lire, c'est pour vous
montrer comment je structure mon programme, et donc que vous pouvez
critiquer.

Je m'applique sur cet aspect, car lors du travail en groupe, cela est
important pour repartir les taches, n'est ce pas ? Alors tout conseil
d'organisation des taches est la bienvenue.

Merci.


MA QUESTION

-------------------------------

Ensuite, donc en effet, je bloque sur le fait, qu'il faudra gérer les
parenthèses et les autres priorités. Il faut que je me documente un peu
plus :

2 solutions pour l'instant :

- arbre binaire

- transformer le calcul en notation polonaise. (il parait que c'est plus simple, mais transformer :

2+2*4 ce qui donne 2,4,*,2,+ dites moi si je me trompe..et bien, je ne vois pas du tout a quoi pourrait ressembler l'algo.)

Il faut vraiment que je reflechisse dessus, car vous êtes; d'accord
avec moi, je ne vais pas commencer a coder, en ayant qu'une partie de
la solution. Et pourtant, petite parenthèse, c'est ce que sont pousse a
faire les élèves, pour montrer au prof qu'ils ont fait quelque chose.

Einstein a dis (mas o menos ) : 70% de réflexion et le reste a l'exécution.

Donc pour se sujet de calculette, sur 15 jours, j'ai disons 10 jours
pour réfléchir. disons, que moi, ça fait déjà 7 jours que je suis
dessus..


AX

nzaeroax · Answer

Bonjour,

Ben apparement, il faudrait rentrer dans de l'assembleur pour gérer les retenues (overflow flag.). Et le type long long permetrait de coder sur 64 bit (équivalent au int64, mais qui est du C standard, c'est bien ca ?)

En utilisant la structure pile (for a gigantic integer), il peux y avoir un débordement de mémoire, mais là, c'est une limite physique au problème n'est ce pas ?

Alors, je pense être convaincu de quelque chose, ne serait-il pas préférable, (et savez vous comment faire) pour que, lors de la lecture des chiffres (dans le fichier), je les stock en HEXADECIMAL ou plutot en BINAIRE dirais je ?
Enfin, je suis pas trop clair dans mes idées, mais je veux dire, que si je lis chiffre par chiffre, ca me fait un nombre entre (0-9) donc codable sur 4 bits, donc gain de stockage. (8bits pour un char)
Après le fait d'être en binaire, devrait simplifier les conversions ou je me trompe ?

Ensuite, ben, est ce possible de mélanger du C et de l'assembleur ?
Ma calculette, ne serait il pas plus simple de la faire en assembleur ? (je connais juste les bases de l'assembleur, manip de registre, et puis, comme c bas comme language c plus simple non ? C'est plus long aussi je crois mais bon...)

Sinon, ben pour ceux de epita, epitech qui me lisent, je voudrais aussi, me mouiller la nuque avant de rentrer dans le bain, et s'il est possible de savoir les liens des exos des piscines précédentes c'est cool. Merci.

D'autre part, la bistro, les notes sont correctes ou ca vole bas ?

Merci

nzaeroax · Answer

Bon le sujet de ma bistromatique est clairement définit sur ce site (qui est très bon je trouve, surtout le lien vers OTB World): 
http://cv.otbworld.com/bistro.php

Et donc je vais commencer à faire cette calculette simplement, en notation POLONAISE, et avec des int.
Après on verra.

Je remercie beaucoup ceux qui m'ont aidé jusque là.

Remarque : ceux qui connaissent d'anciens d'EPITA EPITECH qui ont leurs sites en ligne, tel celui que j'ai mis en lien, se serait sympas de me les passer.

AX

nzaeroax · Answer

Bonjour tout le monde....

*****************************************
Alors, la ma question es simple et courte : 

POUR décomposer mon grand entier dans une pile, il faut choisir quel sera sa représentation interne. (int ou char ?)

J'ai 2 choix :

choix 1 - Pile de int
choix 2 - Pile de char
*****************************************

*****************************************
MON ANALYSE : 
*****************************************

Alors de ce que j'ai lus il serait plus RAPIDE pour les calcul d'utiliser des int. Est ce cela ? Disons, que j'opte pour cette solution : 

Théoriquement, un int = 4 Octets 
                       --> 2^32 possibilités = 2.147.483.647 MAX
                       --> 10 chiffres 
(mais c'est pas 9.999.999.999) alors, je raisonerai sur 9 chiffres, car je considèrerai, lors de la lecture du nombre dans le fichier, que le plus grand nombre, contenant les caractère 0-9, stockable dans un int, est 999.999.999.
Ais je raison ? Me comprenez vous ?

Mes nombres sont dans une structure :

struct nombre
{
  int valeur                           // 
  struct nombre * p_next       // si le nombre depasse 9 chiffres, la suite se 
                                          // trouve la bas
  int taille                             // tres important lors des calcul (mettre bit poid 
                                          // fort ensemble et poid faible aussi)
}

Algorithme : 

1 - lire et stocker l'expression arithmétique
------------------------------------------
 1.1 - lecture char par char dans le fichier

 2.2 - lecture du premier nombre
(hypo : on commence par un nombre de 25 chiffre) donc je lis les 9 premiers caractères et les stock dans ma structure nombre. Puis je continue a lire jusqu'a mon 25eme chiffre.

 3.3 - on sait quand le nombre se termine car on arrive a un opérateur.

 3.4 - on le stock dans la pile de nombre, et on passe au nombre suivant

2 - calculer l'expression arithmétique
------------------------------------------
 2.1 - ca on verra après, mais ici, apparait l'intêret de les stocker sous forme de int je trouve que je pourrai additionner comme cela.

Rq : le '.' c'est pas pour DECIMAL, c'est un repère.

ex : 999999999.987654321 + 123456789
         nbre 1                               nbre 2

Ci dessous , je pense illustrer le fait que la représentation en "int" est plus rapide, que celle e "char" qui me demanderai de calculer case par case.
Me comprenez vous ?

EXEMPLE : 

Premier calcul : 

  987.654.321        bits faible nombre 1
+123.456.789        bits forts  nombre 2
------------------
 1.111.111.110        résultat                   retenue : +1

Second calcul : 

  999.999.999        bits forts nombre 1
+                1        retenue
------------------
 1.000.000.000       résultat (et la, ca fait trop grand pour un int donc je 
                             rallonge ma struct nombre...) 

aahhhhh, et bien vous voyez, j'ai posé tous les éléments, et bien ça va mieux dans ma petite tête...Tout était confus avant.

Bon alors, après, c'est l'analyseur de l'expression. J'utilise pas BISON, ni FLEX, ni de grammaire LL ou je sais plus quoi, car je n'y connais strictement rien, et comme j'aurais de futurs projets, comme la création d'un compilateur pour TIGER, je viendrai m'informer plus tard, la ça fait trop...

Donc, moi, j'aime bien l'idée suivante :

Une pile pour les nombres (type : struct nombre)
Puis une pile pour les opérateurs (type : char)

ex : 1 + 2 * 4

pile nombre    : 1 | 2 | 4
pile opérateur : + | * |

La je n'arrive pas a trouver l'algo pour la notation POSTFIXE. Enfin, je ne sais pas comment, je vais géré l'ordre des calculs.
Rq : en notation RPN : 1 2 + 4 *, la oui, j'ai compris, c'est bcps plus simple.

Pouvez vous m'éclairez en ce qui concerne cet algo de notation POSTFIXE ?

Bon, je suis long et lourd, je sais, j'aimerais savoir si c'est déplaisant de détailler ma façon de raisonner ainsi, et s'il me serait préférable de poser simplement des questions plus courte ?

MERCI.

Projet : calculette à nombre entiers infiniment GRAND

8 réponses

Votre réponse

Discussions similaires