Discussion :

[syllasako]

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

[joel.drigo]

Salut,

Dans quel langage voudrais-tu faire cette bibliothèque ?

[syllasako]

bonjour,
Langage C

[Sve@r]

Bonjour

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

Code c :

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

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

[Bktero]

Tu peux utiliser GMP : https://gmplib.org/ https://fr.wikipedia.org/wiki/GNU_MP

[syllasako]

Bonjour

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

Code c :

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

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

[Sve@r]

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

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

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 c :

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

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

[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.

[syllasako]

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 c :

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

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

[syllasako]

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 :

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

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

[droggo]

Bonjour,

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.

[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.

[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...