Manipulation des entiers très grands

Version imprimable

02/12/2016, 16h55
syllasako

Manipulation des entiers très grands

Bonjour!

je souhaite créer une bibliothèque qui fait des calculs sur des entiers très grand 12 octets par exemple en utilisant les opérations arithmétique (addition,soustraction, multiplication, div, modulo).
comme je suis débutant je vois pas comment m'y prendre .
aidez moi svp
04/12/2016, 23h29
joel.drigo

Salut,

Dans quel langage voudrais-tu faire cette bibliothèque ?
05/12/2016, 18h31
syllasako

bonjour,
Langage C
05/12/2016, 20h08
Sve@r
Bonjour

Une des façons les plus simple à coder pourrait-être de coder chaque chiffre sur un caractère...
Code:

1 2 3 4 typedef struct { char nbr[100 + 1]; // Pour gérer le nombre char fl_neg; // Si le nombre est négatif } t_superLong;
Ce "super long" pourra travailler sur des nombres de (ici) 100 chiffres (le "+1" pour le '\0').
Ensuite les opérations classiques pourraient se faire exactement de la même façon qu'un élève du primaire apprend à faire ces mêmes opérations. Exemple "45 + 38" => 8 + 5 = 3 (retiens "1") puis 4 + 3 + 1 de retenue = 8 => "45 + 38" = "83". Ici déjà je pense que si le nombre est stocké "à l'envers" dans la structure ce sera plus facile pour aligner les unités avec les unités, les dizaines avec les dizaines et etc... => "123" et "45" étant stockés "321" et "54" ça permettra de caler "3" avec "5" et "2" avec "4".

Ensuite ben à toi de continuer...
06/12/2016, 09h25
Bktero

Tu peux utiliser GMP : https://gmplib.org/ https://fr.wikipedia.org/wiki/GNU_MP
11/12/2016, 11h01
syllasako
Citation:
Envoyé par Sve@r

Bonjour

Une des façons les plus simple à coder pourrait-être de coder chaque chiffre sur un caractère...

Code:

1 2 3 4 typedef struct { char nbr[100 + 1]; // Pour gérer le nombre char fl_neg; // Si le nombre est négatif } t_superLong;

Ce "super long" pourra travailler sur des nombres de (ici) 100 chiffres (le "+1" pour le '\0').
Ensuite les opérations classiques pourraient se faire exactement de la même façon qu'un élève du primaire apprend à faire ces mêmes opérations. Exemple "45 + 38" => 8 + 5 = 3 (retiens "1") puis 4 + 3 + 1 de retenue = 8 => "45 + 38" = "83". Ici déjà je pense que si le nombre est stocké "à l'envers" dans la structure ce sera plus facile pour aligner les unités avec les unités, les dizaines avec les dizaines et etc... => "123" et "45" étant stockés "321" et "54" ça permettra de caler "3" avec "5" et "2" avec "4".

Ensuite ben à toi de continuer...
Merci pour ton aide, l'idee peut marcher mais les tableaux de caractère sont très lent.
je veux faire un code qui s’exécute en 3min max
11/12/2016, 12h21
Sve@r
Citation:

Envoyé par syllasako

mais les tableaux de caractère sont très lent.

Ben oui mais on ne peut pas tout avoir...

Citation:

Envoyé par syllasako

je veux faire un code qui s’exécute en 3min max

Tu te crois dans "mission impossible" ??? Ca veut rien dire "3mn". Tout dépend de ce qu'il faut traiter et de la machine sur laquelle ça sera traité...

Une autre solution serait de "concaténer" les longs. Par exemple
Code:

1 2 3 4 5 typedef struct { unsigned long nb1; unsigned long nb2; char fl_neg; } t_superLong;
Avec ce système tu pourras traiter des nombres allant jusqu'à 2^64 soit 18 446 744 073 709 551 616. Mais faudra le gérer. Dans cette écriture, un nombre comme (par exemple) 500 000 000 000 (donc plus grand que 2^32) sera décomposé en
- nb1 qui récupère la division entière de 500 000 000 000/2^32 soit 116
- nb2 qui récupère le reste de cette division, soit 1 783 793 664
Après faudra gérer l'addition, la soustraction etc...
11/12/2016, 12h42
picodev

Bonjour,
en plus de la représentation, il va aussi falloir choisir les algorithmes : passer des implémentations naïves à des implémentations moins évidentes pour améliorer la complexité. Mais en faisant ça tu réinventes la roue car tout cela est déjà fait (et bien fait) dans des bibliothèques comme GMP.
12/12/2016, 00h01
syllasako
Citation:
Envoyé par Sve@r

Ben oui mais on ne peut pas tout avoir...

Tu te crois dans "mission impossible" ??? Ca veut rien dire "3mn". Tout dépend de ce qu'il faut traiter et de la machine sur laquelle ça sera traité...

Une autre solution serait de "concaténer" les longs. Par exemple

Code:

1 2 3 4 5 typedef struct { unsigned long nb1; unsigned long nb2; char fl_neg; } t_superLong;

Avec ce système tu pourras traiter des nombres allant jusqu'à 2^64 soit 18 446 744 073 709 551 616. Mais faudra le gérer. Dans cette écriture, un nombre comme (par exemple) 500 000 000 000 (donc plus grand que 2^32) sera décomposé en
nb1 qui récupère la division entière de 500 000 000 000/2^32 soit 116
nb2 qui récupère le reste de cette division, soit 1 783 793 664

Après faudra gérer l'addition, la soustraction etc...
¨

Merci beaucoup. je vais essayer...
02/01/2017, 16h07
syllasako

la multiplication
bonjour!
je suis toujous sur cet projet.
j'ai fais l'addition et soustraction mais je suis bloquer sur multiplication .
Est ce que cette structure pourra me permettre de faire faire la multiplication car si j'ai par exemple
Code:

1 2 3 4 5 6 7 8 9 typedef struct{ long nbr1; long nbr2; }entier; et que je veux faire entier mult(entier A, entier B){ entier resultat; resultat.nbr2= A.nbr2*B.nbr2; }
A.nbr2 et B.nbr2 étant codés sur 64bit le produit sera codé sur 128 bit et ça ne peut rentré dans resultat.nbr2 qui codé sur 64bit donc je perds la retenu.
je vois pas comment je peux geré cela
Aidez moi svp
02/01/2017, 22h08
droggo

Bonjour,

Citation:

Envoyé par syllasako

A.nbr2 et B.nbr2 étant codés sur 64bit le produit sera codé sur 128 bit et ça ne peut rentré dans resultat.nbr2 qui codé sur 64bit donc je perds la retenu.
je vois pas comment je peux geré cela
Aidez moi svp

Ben oui, ce n'est pas aussi simple que tu sembles le croire.

La solution genre GMP est une bonne solution. Si tu préfères en développer une, tu peux au moins t'en inspirer. :)
03/01/2017, 12h38
syllasako

salut bien sur je sais que c'est pas facile...
je comprend pas le contenue de GMP si tu peux m'aider ça serai bien.
Genre un indice si tu a compris mon problème.
12/01/2017, 15h17
Captain'Flam

Si ton besoin de librairie de calcul sur des entiers longs correspond à un projet/devoir à rendre, tu ne peux pas te permettre de refiler une lib déjà faire comme gmp.
Donc tu dois te frotter aux mêmes problèmes que ceux qui l'ont écrite...
Par exemple le dépassement :

-> quand tu additionnes 2 entiers de N bits, ton résultats peut nécessiter N+1 bits.
-> quand tu multiplies 2 entiers de N bits, ton résultats peut nécessiter N*2 bits.
et là, personne ne peut rien pour toi, ce sont les maths !

A toi de voir si tu veux que tes entiers s'allongent automatiquement,
ou si tu te contentes de remonter une erreur en cas de dépassement.

Ça dépend de ton besoin (ou de la consigne).

Pour les algos, je te suggère de t'inspirer de ceux que tu as appris en primaire pour poser les opérations sur papier.
On n'a pas fait beaucoup mieux...