Discussion :

[TrexXx]

Bonjour à tous,
Je dois réaliser une calculatrice qui travaille sur des grands nombres (de l'ordre de mille chiffres), et je ne sais pas trop comment stocker ces nombres en mémoires, et je voulais savoir si certains d'entre vous avaient une idée sur le meilleur moyen pour stocker de tels nombres, pour pouvoir les utiliser facilement par la suite (multiples opérations).
Merci d'avance.

[Invité(e)]

Bonjour,

Une solution serait d'utiliser gmp qui permet de travailler sur des entiers de taille arbitraire.

http://gmplib.org/ en particulier : http://gmplib.org/manual/Integer-Fun...eger-Functions.

EDIT : exemple simple

Code :

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

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
47
48
#include <stdio.h>
/* utilisation de lib gmp */
#include <gmp.h>
 
int main(void)
{
    char result[256];
 
    /* trois entiers */
    int int32[3];
 
    /* trois entier gmp */
    mpz_t integ[3];
 
    /* initialisation des entiers gmp */
    mpz_init(integ[0]);
    mpz_init(integ[1]);
    mpz_init(integ[2]);
 
    /* assignation des entiers */
    int32[0] = 3000000;
    int32[1] = 10000;
 
    /* assignation des entiers gmp */
    mpz_set_str(integ[0], "3000000", 10);
    mpz_set_str(integ[1], "10000", 10);
 
    /* multiplication */
    int32[2] = int32[0] * int32[1];
 
    /* multiplication gmp */
    mpz_mul(integ[2], integ[0], integ[1]);
 
    /* affichage du resultat */
    printf("result: %d\n", int32[2]);
 
    /* affichage du resultat gmp */
    if (NULL != mpz_get_str(result, 10, integ[2])) {
        printf("result (gmp): %s\n", result);
    }
 
    /* nettoyage gmp */
    mpz_clear(integ[0]);
    mpz_clear(integ[1]);
    mpz_clear(integ[2]);
 
    return 0;
}

donne

Code :

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

1
2
result: -64771072
result (gmp): 30000000000

[oniric]

sinon sans bibliotheque supplementaire, from scratch, tu peux stocker tes nombres sous formes de string et coder des fonctions specials qui gere les operations de 2 strings qui represente un nombre etc.
Avec ce systeme tu peux faire un calculateur de nombre bcp plus grand que si tu les stocks sous forme de nombre directement.

exemple :
tu as le nombre 123456789123456789 tu le lis au format string
idem avec 987654321987654321

tu as donc 2 string qui represente des nombres, imaginons une addition, tu sais que le caractere '9' et le caractere '1' donne 0 + 1 au chiffre suivant etc. Apres il faut optimiser tes fonctions pour les multiplications/divisions etc.

[droggo]

Hai,

sinon sans bibliotheque supplementaire, from scratch, tu peux stocker tes nombres sous formes de string et coder des fonctions specials qui gere les operations de 2 strings qui represente un nombre etc.
Avec ce systeme tu peux faire un calculateur de nombre bcp plus grand que si tu les stocks sous forme de nombre directement.

exemple :
tu as le nombre 123456789123456789 tu le lis au format string
idem avec 987654321987654321

tu as donc 2 string qui represente des nombres, imaginons une addition, tu sais que le caractere '9' et le caractere '1' donne 0 + 1 au chiffre suivant etc. Apres il faut optimiser tes fonctions pour les multiplications/divisions etc.

Pour optimiser, certainement pas en stockant, calculant avec des caractères.

C'est un sujet récurrent, il faut chercher un peu sur le forum.

[TrexXx]

On m'a déjà parler de gmp mais le problème c'est que c'est dans un cadre scolaire, donc je dois tout faire moi même sans aucune bibliothèque (à part les standards). Mais je vais regarder gmp, dois y avoir moyen de comprendre comment c'est coder (voir d'avoir les sources ?)?

[Emmanuel Delahaye]

On m'a déjà parler de gmp mais le problème c'est que c'est dans un cadre scolaire, donc je dois tout faire moi même sans aucune bibliothèque (à part les standards). Mais je vais regarder gmp, dois y avoir moyen de comprendre comment c'est coder (voir d'avoir les sources ?)?

Je ne suis pas sûr qu'un programmeur confirmé y comprenne quelque chose, alors un débutant...

Les source, c'est pas le manuel de conception. Et ça, ce n'est jamais publié. La publication des sources est une vaste fumisterie markéting qui fait croire que la technologie est accessible (free, c'est à dire 'libre' !).

Je peux sans gros problèmes, écrire du code source source fonctionnel tellement illisible que même moi, je ne saurais ni le lire ni le dépanner...

[contremaitre]

Les source, c'est pas le manuel de conception. Et ça, ce n'est jamais publié. La publication des sources est une vaste fumisterie markéting qui fait croire que la technologie est accessible (free, c'est à dire 'libre' !).

Oui c'est bien connu, tous les projets open sources sont là pour faire du "marketing"...

Meme si ça peut prendre un peu de temps, a moins d'etre très mal écrit (ce qui n'est pas le cas des projets de qualités), on peu très bien comprendre un projet, meme conséquent, avec son code source, je l'ai deja fait et je ne suis pas un expert.

Par contre pour un débutant, je suis d'accord, c'est pas la peine.

[Garulfo]

Oui c'est bien connu, tous les projets open sources sont là pour faire du "marketing"...

Meme si ça peut prendre un peu de temps, a moins d'etre très mal écrit (ce qui n'est pas le cas des projets de qualités), on peu très bien comprendre un projet, meme conséquent, avec son code source, je l'ai deja fait et je ne suis pas un expert.

Par contre pour un débutant, je suis d'accord, c'est pas la peine.

Emmanuel n'a pas dit que tous les projets open-sources sont commerciaux, ce qui serait faux. Je pense qu'il voulait dire que quand une boite comme Sun dit qu'elle fait de l'open-source, c'est pour se donner une bonne apparence car elle sait très bien que, même bien écrit, un code source de 200000 lignes est incompréhensible sans documentation externe supplémentaire. Ne te leurres pas en pensant que tu pourrais comprendre un projet industriel de taille moyenne en utilisant uniquement le code source. Même sans le modifier, c'est à peu près infaisable de manière général.

De plus, énormément de projet open-source sont mal rédigés. Le manque de coordination, de réunion, d'assiduité et de méthodologie claire en sont la cause bien sûr. Les techniques AGILE sont souvent prises pour du « on code et a pas besoin de faire de la vrai documentation » ce qui n'est pas du tout le cas. Il est vrai que même dans des entreprises on voit des horreurs

-------------

En tout cas, pour mettre mon petit grain de sel dans la discussion, il y a un beau moyen de coder des grands entiers en utilisant les suites de Goodstein. Mais bon je crains d'effrayer nos jeunes informaticiens avec un peu trop de math http://en.wikipedia.org/wiki/Goodstein's_theorem

[contremaitre]

Sauf qu'ici on ne parle pas d'une boite mais du projet GMP qui n'est pas commercial et ne fait pas dans le marketing en publiant son code source.

Pour ce qui est de la qualité du code c'est un autre débat, et je dirai que le fait que ce soit publique, et que plusieurs développeur lisent toutes les modifications apportées permet d'avoir de la qualité. Bien sur cela dépend beaucoup des projets, de leur taille, etc...

[TrexXx]

Sans vouloir vous offensez serait il possible de revenir au sujet central du thread ? A savoir stocker des grands nombres en mémoires, le tout pour pouvoir effectuer toutes les opérations standards avec ceux ci (opérations à recoder en fonction bien sur). Je ne suis pas un débutant en C, même si je n'ai certainement pas le niveau de certains ici. Donc quel serait d'après vous un moyen simple et efficace pour faire ça ? J'avais personnellement pensé aux listes chainées (où chaque cellule stockerait une partie du nombre) , est ce une bonne idée ou y a t il une meilleure solution ?
Merci d'avance à ceux qui prendront la peine de me répondre.

[Melem]

Jette un coup d'oeil : Opérations sur des grands nombres.

[souviron34]

Sans vouloir vous offensez serait il possible de revenir au sujet central du thread ? A savoir stocker des grands nombres en mémoires, le tout pour pouvoir effectuer toutes les opérations standards avec ceux ci (opérations à recoder en fonction bien sur). Je ne suis pas un débutant en C, même si je n'ai certainement pas le niveau de certains ici. Donc quel serait d'après vous un moyen simple et efficace pour faire ça ? J'avais personnellement pensé aux listes chainées (où chaque cellule stockerait une partie du nombre) , est ce une bonne idée ou y a t il une meilleure solution ?
Merci d'avance à ceux qui prendront la peine de me répondre.

uh.....

1.6 e+308 c'est pas un grand nombre ??

(c'est la limite 32 bits des doubles)..

J'avoue avoir toujours un peu (beaucoup) de mal avec ces trucs de grands nombres...

[droggo]

Hoe,

uh.....

1.6 e+308 c'est pas un grand nombre ??

(c'est la limite 32 bits des doubles)..

J'avoue avoir toujours un peu (beaucoup) de mal avec ces trucs de grands nombres...

C'est la limite des double, soit sur 64 bits.

Le problème posé ne concerne pas la valeur maximale possible, mais le fait de garder et calculer avec beaucoup plus de chiffres significatifs que les types natifs, soit 16 à 17 pour double..., loin de

Bonjour à tous,
Je dois réaliser une calculatrice qui travaille sur des grands nombres (de l'ordre de mille chiffres), et je ne sais pas trop comment stocker ces nombres en mémoires, et je voulais savoir si certains d'entre vous avaient une idée sur le meilleur moyen pour stocker de tels nombres, pour pouvoir les utiliser facilement par la suite (multiples opérations).
Merci d'avance.

[souviron34]

Hoe,

C'est la limite des double, soit sur 64 bits.

Le problème posé ne concerne pas la valeur maximale possible, mais le fait de garder et calculer avec beaucoup plus de chiffres significatifs que les types natifs, soit 16 à 17 pour double..., loin de

les double sont bien sur 64, mais sur une architecture 32

Secondo, je ré-itère ce que j'avais dit dans un autre post à ce sujet, à part pour du chiffrage (et combien y at-il d'informaticiens et de mathématiciens dans le monde travaillant sur le chiffrage ??) en quoi est-ce utile d'avoir autant de chiffres significatifs ????

Après 27 ans de carrière scientifico-informatique, je n'ai pas de réponse... Je ne connais pas une seule mesure qui justifierait - mathématiquement - cette précision... (si l'on peut appeler ça une précision.... 1 millième ce n'est que 3 chiffres, un milliardième 9, alors je ne sais même pas quel serait le nom pour 1000....)

[Emmanuel Delahaye]

Secondo, je ré-itère ce que j'avais dit dans un autre post à ce sujet, à part pour du chiffrage

Il semblerait que ce soit précisément le sujet...

[souviron34]

Il semblerait que ce soit précisément le sujet...

je suis d'accord mais je ne comprend pas qu'on prenne ça comme exemple pour des débutants (et même pour des cours normaux) : encore une fois quelle est la proportion des informaticiens touchant à ce domaine ?? et je trouve que c'est inculquer de fausses notions (grands nombres = nécessité d'une biblio spéciale, de calculs spéciaux, types standards insuffisants, etc etc)..

Et vu la fréquence à laquelle cela apparaît sur ce forum, cela a l'air d'être enseigné de manière relativement large... D'où mon questionnement... C'est comme enseigner une exception pour apprendre à se servir des maths ou d'un raisonnement...

[droggo]

Hei,

je suis d'accord mais je ne comprend pas qu'on prenne ça comme exemple pour des débutants (et même pour des cours normaux) : encore une fois quelle est la proportion des informaticiens touchant à ce domaine ?? et je trouve que c'est inculquer de fausses notions (grands nombres = nécessité d'une biblio spéciale, de calculs spéciaux, types standards insuffisants, etc etc)..

Et vu la fréquence à laquelle cela apparaît sur ce forum, cela a l'air d'être enseigné de manière relativement large... D'où mon questionnement... C'est comme enseigner une exception pour apprendre à se servir des maths ou d'un raisonnement...

Je pense que tu confonds grand nombre et précision du calcul.

D'ailleurs, "grand nombre" est très relatif, et dans certains domaines, 1.6e308 est un très petit nombre.

Il y a quand même pas mal de cas où la précision est nécessaire, et où la perte d'un seul digit significatif est irrémédiablement proscrite (théorie des nombres, crypto, comme déjà dit, ....).
L'informatique, ce n'est pas que de l'application aux finances ou à la physique.

De plus, et c'est sans doute le but des exercices, apprendre à faire du calcul multi-précision amène à réfléchir sur les moyens de le faire, et même à réfléchir sur des algorithmes que tout le monde connaît, mais applique sans forcément les avoir vraiment compris.

Il est cependant vrai qu'il y a d'autres choses plus importantes à apprendre en informatique, ceci n'étant qu'une application que je dirais presque basique.

[souviron34]

Hei,

Je pense que tu confonds grand nombre et précision du calcul.

Non, du tout, mais quand on dit : "1000 chiffres significatifs", on parle quand même de précision...

D'ailleurs, "grand nombre" est très relatif, et dans certains domaines, 1.6e308 est un très petit nombre.

Encore une fois, j'aimerais des exemples hors du cryptage...

Même dans mon domaine initial d'astrophysique, même à la taille de l'Univers (14 milliards d'années-lumières), ça ne fait que 14 10^9 * 365 * 86400 * 3 * 10^5
soit (1.4 * 3.65 * 8.64 * 3) 10^21 soit 3.97 10^23 kms, donc même si tu voulais exprimer la taille de l'univers en millimètres (on se demande bien pourquoi et quelle signifcation cela aurait), cela ne représenterait que 29 chiffres "significatifs".... (et on est loin du e+308)
(et même si l'on voulait la mesurer (la plus grande chose connue) en unité la plus petite connue, la distance inter-quark, ça ne représenterait que 41 chiffres)..

Il y a quand même pas mal de cas où la précision est nécessaire, et où la perte d'un seul digit significatif est irrémédiablement proscrite (théorie des nombres, crypto, comme déjà dit, ....).
L'informatique, ce n'est pas que de l'application aux finances ou à la physique.

Voir plus haut.... La présence de chiffres "significatifs" étant la "signification", que vient faire une telle précision dans l'écriture à moins de concourir pour le calcul des décimales de PI ???? Cela n'a aucune signification dans tous les domaines sauf la cypto...

De plus, et c'est sans doute le but des exercices, apprendre à faire du calcul multi-précision amène à réfléchir sur les moyens de le faire, et même à réfléchir sur des algorithmes que tout le monde connaît, mais applique sans forcément les avoir vraiment compris.

Là c'est toi qui mélanges précision et grand nombre

Mais je ne vois pas en quoi calculer un nombre à 1000 chiffres sera utile pour les calculs multi-précision que 99.99% des programmeurs rencontrent au cours de leur vie...

Faudra qu'on m'explique, mais je ne vois aucune utilité à part théorique, or les questions posées sur ce forum le sont en quasi-totalité par des débutants.... Donc je reviens sur le fait que la théorie des grand nombres n'a que très très très très peu d'intérêt dans ce cadre, et ne fait que mélanger les futurs programmeurs sur les notions de précisions, d'affichage, de limite "conceptuelle" d'un calcul (à quoi cela peut bien servir à une banque de calculer ses dividendes au milliardième de milliardième de milliardième (et j'en passe pas mal) de centime ???? puisque cela n'existe pas et que, même multiplié par des milliards, cela ne changera en rien le bilan des opérations... Et pour la vie de tous les jours, une position sur une image, ou la préparation d'une opération chirurgicale, ou la position d'un TGV, ou l'inclinaison d'un avion et la poussée de son moteur, à une précision qu'aucun servo-moteur, engrenage, moteur électrique, moteur analogique, microscope électronique, faisceau atomique, etc etc n'est capable de fournir, ni un utilisateur de comprendre ?????


A part quelques (très peu nombreux) qui seront dans la recherche en informatique, la quasi-totalité des programmeurs auront à faire face à des calculs concrets...

Et les calculs et applications concrètes sont limités par la compréhension, et les applications par leur impact dans le monde réel (pilotage de machine, reproduction, calcul d'aide, etc etc)).

La précision induite par ces grand nombres, je n'en connais pas d'exemple dans la vie pratique industrielle, sauf encore une fois pour la crypto..

[souviron34]

je rajouterais un point (une explication ??) qui m'est venue ce matin en prenant mon café...

Je ne sais pas si c'est toujours le cas, mais à la fin des années 70 début 80, on n'enseignait plus les ordres de grandeur , même en terminale scientifique.. Or un certain nombre de profs ont entre 30 et 40 ans... et ont donc subi cette "éducation" au lycée. Par conséquent, pour eux, ils n'ont absolument aucune espèce d'idée de ce que cela représente... d'où une présentation de choses totalement absurdes..

M'enfin c'est juste un avis sur le pourquoi de la présence de tels exemples....

[souviron34]

et pour conclure sur ce sujet, un rapide calcul "informatique" :

si 2^3 = 3 bits est pris pour être environ un facteur 10 (approximation par valeur supérieure du nombre de chiffres nécessaire), un nombre 32 bits nécessiterait environ 10 chiffres, 20 pour 64 bits, 40 pour 128, 80 pour 256, 160 pour 512, 320 pour 1024, 640 pour 2048, 1280 pour 4096..

Donc mille chiffres signifierait un nombre sur environ 3000 bits !!!!

Vous trouvez ça fréquent, ou même raisonnable, vous ????