Discussion :

[jerem721]

Bonjour à tous,

je vous écrit car je recherche un méthode qui permet de faire des calcul avec des nombres infiniment grand.
J'ai vu sur le net qu'on pouvais utilisé les char pour faire des calcule.
Il y a t'il d'autre méthode? algorithme? qui permet de faire cela.

merci d'avance.
jerem721

[Melem]

Infiniment grands (= l'infini mathématique) ou justes très grands (milliards de milliards ... de milliards) ? Dans le deuxième cas, il y a des bibliothèques comme GMP qui sont faites pour. Du point de vue algorithmique, il faut en effet représenter les nombres avec des chaînes de caractères et faire les calculs sur ces chaînes.

[jerem721]

oui serait pour des nombre de l'ordre du milliard de milliard (tout ce qui ne rentre pas dans un int en faite)
c'est quoi la méthode a utiliser avec les char car je comprend pas trop en faire comme on peut calculer avec des char :s

[10_GOTO_10]

des nombres infiniment grand.

INFINIMENT ? Tu vas avoir du mal à trouver.

Si tu peux te contenter seulement de nombre très grands, il existe des bibliothèques.

Regarde ici: http://gmplib.org/

[edit]Grillé par un modérateur qui poste plus vite que son ombre[/edit]

[jabbounet]

Autrement si tout tes nombres sont du même ordre de grandeur, tu peux changer d'unité/d'échelle pour que tes nombres tiennent dans un int.

Par exemple pour une application manipulant des distance/longueurs. On peux très bien choisir que l'unité stocké dans un int sera le ..., millimètres, mètres, kilomètres, ....

le millimètre sera plutôt pour des plan type menuiserie ...
le mètre sera plutôt utilisé pour les plans cadastraux
les kilomètres pour les plans d'autoroute.

[Obsidian]

Hello,

oui serait pour des nombre de l'ordre du milliard de milliard (tout ce qui ne rentre pas dans un int en faite)
c'est quoi la méthode a utiliser avec les char car je comprend pas trop en faire comme on peut calculer avec des char :s

En fait, calculer avec des « char » n'est pas la méthode la plus efficace. Le mieux reste encore d'utiliser les types natifs de ta machine (int) et de faire de l'arithmétique avec, comme sur papier. Ce n'est pas forcément très difficile en soi, mais cela demande d'être TRÈS soigneux, et c'est quand même beaucoup de boulot, car il faut ré-implémenter toutes les opérations arithmétiques de base et gérer l'allocation de la mémoire avec.

L'idée, donc, est de considérer que FFFFFFFFh + FFFFFFFFh font 1FFFFFFFEh. Donc la somme de deux nombres 32 bits tient au maximum sur 33. Tu peux donc obtenir le résultat un registre du même format que les opérandes et gérer la retenue à côté.

Pour la multiplication, le produit de deux nombres 32 bits tient sur 64 bits au maximum (le double de la taille des opérandes). Dans l'absolu, tu pourrais donc obtenir le résultat du produit de deux long dans un long long. Tu peux alors « poser » les 32 bits de poids faible et « retenir » les 32 autres.

C'est de la même façon que, sur papier, lorsque tu multiplies deux nombres de 1 chiffre, par exemple 8 × 9, le résultat tient au maximum sur deux chiffres, ici 72. Tu poses alors « 2 » et tu retiens « 7 ».

Si tu considères que tu travailles en bases 4294967925, alors chaque chiffre unique tient exactement sur 32 bits et les règles de l'arithmétique restent valables.


Si c'est juste pour l'exercice, tu peux essayer de t'y coller. Si c'est pour travailler avec, utilise GMP.

[Elboras]

si tu veux vraiment te baser sur du type char, tu peux.
Quelque chose me dit que tu es étudiant d'epita ou d'epitech, que tu dois faire le projet bistromatique. Vu la date, j'obterais plus pour Epitech vu que ca doit etre la fin de la "piscine" en ce moment.

Pour faire des operations sur des nombres infiniment long, en se basant sur des chaines de caractères, il faut que tu fonctionne par retenu.

pour te donner des exemples:
une addition de "1234" et "1234" :
- 4+4 = 8
- 3+3 = 6
- 2+2 = 4
- 1+1 = 2
-> 2468

Ici c'est un cas classique, ou tu prend chaque chiffre et que tu les additionnes.
Maintenant, si tu remplace "1234" par "1236":
6+6 = 12, ici comme quand tu étais petit, tu peux avoir une retenu à ajouter à la dizaine au dessus ...

Après tu dois bien penser a tous les cas de figure, si tu as une retenu sur ta dizaine la plus haute, que ce que tu fais (reallouer une autre chaine un poil plus grande ? ou encore une solution un peu plus optimisé).

Pour les autres operations, je te laisse faire des recherches, sachant que si tu ne recherche pas forcément les performances, une multiplication de chiffre entier n'est rien d'autre qu'une succession d'addition ...

Bon courage

[Melem]

[edit]Grillé par un modérateur qui poste plus vite que son ombre[/edit]

Plutôt par un modérateur qui n'a pas pris la peine de mettre un lien dans son message :lol

En fait, calculer avec des « char » n'est pas la méthode la plus efficace. Le mieux reste encore d'utiliser les types natifs de ta machine (int) et de faire de l'arithmétique avec, comme sur papier. Ce n'est pas forcément très difficile en soi, mais cela demande d'être TRÈS soigneux, et c'est quand même beaucoup de boulot, car il faut ré-implémenter toutes les opérations arithmétiques de base et gérer l'allocation de la mémoire avec.

En fait, le calcul en binaire est certes plus efficace, et pas plus difficile à implémenter que la méthode avec des chaînes, mais c'est l'affichage du résultat qui est très compliquée.

[droggo]

Hoa,

En fait, le calcul en binaire est certes plus efficace, et pas plus difficile à implémenter que la méthode avec des chaînes, mais c'est l'affichage du résultat qui est très compliquée.

Pas du tout, on fait exactement comme pour tout affichage : on extrait les modulos 10 (pour afficher en décimal) successifs.
Si l'implémentation est bien faite, ça va bien assez vite pour qu'on n'ait pas le temps de voir le temps de calcul de la chaîne (à moins d'avoir un vraiment très grand nombre ).

Et, à moins de vouloir passer du temps à faire une implémentation, il vaut mieux utiliser une bibliothèque disponible (GMP, par exemple).
Car le principe est très simple, mais pour être suffisamment complet, c'est relativement long à écrire/tester.

[Melem]

Pas du tout, on fait exactement comme pour tout affichage : on extrait les modulos 10 (pour afficher en décimal) successifs.(

Ou les modulos (int)(10^((int)log10(UINT_MAX))) successifs . Bon, le "très" était en effet peut-être une exagération. Mais en implémentation, c'est nettement plus compliqué de faire un seul appel à printf quand même, non ?

[droggo]

Hoa,

Pourquoi aller chercher des log ?

De toute manière, si on veut utiliser ces grands nombres, on n'échappe pas à l'implémentation des fonctions permettant de les convertir en chaîne d'une part, et permettant de les lire depuis une chaîne d'autre part.

Ces fonctions sont d'ailleurs les 2 plus simples à écrire pour la bibliothèque, mais impliquent que les opérations basiques le soient déjà.

[Jean-Marc.Bourguet]

En fait, le calcul en binaire est certes plus efficace, et pas plus difficile à implémenter que la méthode avec des chaînes, mais c'est l'affichage du résultat qui est très compliquée.

Ce qu'on fait dans ce genre de bibliothèque, c'est utiliser une représentation en base B. B étant choisit de manière à être facilement stockable (donc B <= MAXUINT_MAX+1), B*B facilement manipulable (sinon les multiplications sont pénibles, donc B*B <= MAXUINT_MAX+1). B=10 est simple à visualiser mais pas très performant. Le plus grand B tel que B*B <= MAXUINT_MAX+1 est le plus performant pour les calculs (en temps et en espace) mais les conversions de et vers le décimal sont quand même relativement couteuses (pour donner une idée: le calcul de pi par F. Bellard a pris 103 jours, la conversion en décimal 13). La plus grande puissance de 10 tel que B*B <= MAXUINT+1, peut être le bon compromis dans certaines applications.

[droggo]

Joa,

Pour être le plus performant possible, ce qu'on fait en fait dans ce genre de bibliothèque, est d'utiliser comme base le mot natif du processeur cible, en non signé.

Pour gérer facilement les calculs, ça implique d'écrire les calculs de base (les algorithmes naïfs en assembleur, qui dispose de tous les mécanismes nécessaires.

[ABandApart]

Bonjour à tous,

je vous écrit car je recherche un méthode qui permet de faire des calcul avec des nombres infiniment grand.
J'ai vu sur le net qu'on pouvais utilisé les char pour faire des calcule.
Il y a t'il d'autre méthode? algorithme? qui permet de faire cela.

merci d'avance.
jerem721

J'ai eu a le faire pour un projet d’école.
J'ai utilisé des chaînes de caractères (char*), et j'ai posé les opérations comme en primaire.
C'est la seule et unique façon d'y arriver.
Finalement ça n'a pas été aussi dur que ça, le plus dur étant d’évaluer l'expression, de gérer les priorités (parenthèses, priorités de signe), etc...

Bonne chance.

[Obsidian]

J'ai utilisé des chaînes de caractères (char*), et j'ai posé les opérations comme en primaire. C'est la seule et unique façon d'y arriver.

On a expliqué au-dessus quelle est l'approche la plus sensée. Utiliser des chaînes de caractères est un raccourci fréquent parce qu'on ne fait pas l'association entre la façon dont le binaire est manipulé par le micro-processeur et la façon dont on calcule soi-même. Il est important de comprendre qu'au final, c'est le même procédé.

Ramener cela à des chaînes de caractères est utile quand on souhaite directement compter en décimal et afficher le résultat facilement, comme on l'a dit au-dessus, mais c'est peu efficace en termes de mémoire et ce n'est pas évolutif du tout. Et dans tous les cas : ça ne peut certainement pas être un cas d'école à donner en exemple.

Alors, s'y lancer pour un projet personnel, à la limite, mais annoncer que « c'est la seule et unique façon d'y arriver », ça me paraît très excessif.

[ABandApart]

On a expliqué au-dessus quelle est l'approche la plus sensée. Utiliser des chaînes de caractères est un raccourci fréquent parce qu'on ne fait pas l'association entre la façon dont le binaire est manipulé par le micro-processeur et la façon dont on calcule soi-même. Il est important de comprendre qu'au final, c'est le même procédé.

Ramener cela à des chaînes de caractères est utile quand on souhaite directement compter en décimal et afficher le résultat facilement, comme on l'a dit au-dessus, mais c'est peu efficace en termes de mémoire et ce n'est pas évolutif du tout. Et dans tous les cas : ça ne peut certainement pas être un cas d'école à donner en exemple.

Alors, s'y lancer pour un projet personnel, à la limite, mais annoncer que « c'est la seule et unique façon d'y arriver », ça me paraît très excessif.

La je dois bien avouer ne pas comprendre comment faire avec des types primitifs comme un int.

A partir du moment ou ton nombre dépasse 2^32 (unsigned int), il devient impossible de le manipuler.

ou alors "123456789123456789" devient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
int part[3];
 
part[0] = 1234567;
part[1] = 891234;
part[2] = 56789;

Et la ça devient vraiment délicat et complexe pour un gain de performance, complètement négligeable.

Ou alors je n'ai pas compris ta manière de procéder, ce qui est sûrement l'explication la plus probable

[droggo]

Hia,

A partir du moment ou ton nombre dépasse 2^32 (unsigned int), il devient impossible de le manipuler

La limite n'est pas forcément 2^32, elle dépend du processeur.

Pour manipuler aisément ces données de la taille des mots native du processeur, il faut utiliser l'assembleur. Les processeurs disposent de tout ce qu'il faut pour prévenir en cas de débordement (en clair : retenue à reporter), ce qui est le seul soucis pour l'application des algorithmes.

ou alors "123456789123456789" devient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
int part[3];
 
part[0] = 1234567;
part[1] = 891234;
part[2] = 56789;

Non, il ne devient pas ça, car tu te contentes de découper la chaîne. Il faut la traduire en binaire, et voir combien de mots elle utilise, etc.

[Melem]

Ce qu'on fait dans ce genre de bibliothèque, c'est utiliser une représentation en base B. B étant choisit de manière à être facilement stockable (donc B <= MAXUINT_MAX+1), B*B facilement manipulable (sinon les multiplications sont pénibles, donc B*B <= MAXUINT_MAX+1). B=10 est simple à visualiser mais pas très performant. Le plus grand B tel que B*B <= MAXUINT_MAX+1 est le plus performant pour les calculs (en temps et en espace) mais les conversions de et vers le décimal sont quand même relativement couteuses (pour donner une idée: le calcul de pi par F. Bellard a pris 103 jours, la conversion en décimal 13). La plus grande puissance de 10 tel que B*B <= MAXUINT+1, peut être le bon compromis dans certaines applications.

Cela me semble en effet être une bonne approche.

La je dois bien avouer ne pas comprendre comment faire avec des types primitifs comme un int.

A partir du moment ou ton nombre dépasse 2^32 (unsigned int), il devient impossible de le manipuler.

On traduit la chaîne qu'on va manipuler en binaire, par exemple "12" en 1100 (pas "1000"). On fait ses calculs sur ces binaires. Ces nombres binaires peuvent être représentés par des tableaux "d'octets", des tableaux de unsigned char donc par exemple. Pour l'affichage, chemin inverse : on convertit le tableau d'octets en chaîne décimale puis on affiche la chaîne (ou faire la conversion et l'affichage simultanément). C'est en résumé l'approche avancée dans les premières réponses de cette disussion mais Jean Marc nous en a présenté une autre visiblement meilleure, mais partant toujours du même principe, comme toutes les autres méthodes.