Discussion :

[nocta]

Bonjour!
Je cherche actuellement à créer une librairie de calcul sur les grands nombres. L'idée est la suivante:
J'ai un grand nombre de type unsigned long int, possedant par exemple 50 chiffres.
Je le decoupe dans un tableau, avec, par exemple encore une fois, 4 chiffres par case (les 4 premiers, puis les 4 suivants, etc...).
Ensuite il me reste à faire mes opérations "comme à l'ecole" en considerant les blocs de chiffres! J'aimerai en premier lieu ecrire de cette manière la multiplication et le modulo.

Mes questions sont alors:
comment decouper mon nombre en blocs de 4 chiffres? Sans utiliser d'operateurs mathematiques sur celui ci car ils ne fonctionnent pas pour de grands nombres!!
Puis comment gerer les fifferentes opérations entre les blocs de 4 chiffres?
Merci d'avance si vous avez une idée!

[Invité(e)]

Bonjour,

Une idée serait de ne jamais travailler sur des types de base, mais seulement sur des chaines de caractères.

En gros cela reviendrait à créer un programme qui compte comme nous : directement en décimal, sans passer par du binaire.

[nocta]

Oui je pensai effectivement à ca aussi. Finalement en entrée j'ai une chaine de caractere (cela me permet d'avoir des nombres tres grands).
Ensuite je coupe cette chaine en un tableau de unsigned int où chaque case contient 4 chiffres. Il me reste donc à effectuer les calculs entre ces cases de unsigned int, a priori je n'aurai jamais de depassement. Mon problème maintenant c'est d'effectuer les opérations entre les dîtes cases. Je ne suis pas resté en char parce que je suis incapable de comprendre comment faire des calculs entre operande de type 'char'.

[Invité(e)]

Je ne suis pas resté en char parce que je suis incapable de comprendre comment faire des calculs entre operande de type 'char'.

Dans le code ascii, les caractères codant les chiffres se suivent, il suffit donc de connaitre la valeur de '0' pour déterminer les autres valeur. Or ton compilateur connait la valeur du caractère codant 0, c'est '0'.

Donc, pour transformer un caractère en entier, on peut faire comme ça :

Code :

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

1
2
3
4
/* la caractère à convertir*/
char c = '5';
/* le résultat de la conversion */
int i = c - '0';

(Tu peux prendre ta table ascii pour vérifier.)

Un exemple plus poussé :

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
#include <stdio.h>
 
int main(void) 
{
    int i;
    /* taille de travail*/
    const int len = 5;
    /* opérandes et résultat : chaines de caractères */
    char op_1[len+1] = "15991";
    char op_2[len+1] = "35219";
    char resultat[len+1] = "00000";
    /* retenue : ne prendra que 1 ou 0 comme valeur */
    int retenue = 0;
 
    for(i = len - 1; i >= 0; --i) {
        /* récupération des chiffres et transformation en entiers */
        int int_1 = op_1[i] - '0';
        int int_2 = op_2[i] - '0';
 
        /* addition */
        int res = int_1 + int_2 + retenue;
 
        /* retenue */
        if(res > 9) {
            if(i == 0) {
                printf("dépassement!\n");
            } else {
                retenue = 1;
            }
        } else {
            retenue = 0;
        }
        /* conversion du résultat en caractère */
        resultat[i] = res%10 + '0';
    }
 
    /* affichage du résultat */
    printf("  %s\n", op_1);
    printf("+\n");
    printf("  %s\n", op_2);
    printf("  -----\n");
    printf("  %s\n", resultat);
 
    return 0;
}

[nocta]

ok merci, ça m'eclaire beaucoup!
Pour l'addition c'est parfait.
Par contre, si je comprend bien le système, ça m'oblige à considerer les caracteres un par un? Pour la multiplication, je pensai proceder par blocs de 4 chiffres pour gagner de la vitesse, mais ta solution ne marche plus en ce cas.

Est ce que je gagne réellement de la vitesse en prenant des blocs de 4 chiffres? Car autrement t'as solution est impecc.

[Invité(e)]

Par contre, si je comprend bien le système, ça m'oblige à considerer les caracteres un par un? Pour la multiplication, je pensai proceder par blocs de 4 chiffres pour gagner de la vitesse, mais ta solution ne marche plus en ce cas.
Est ce que je gagne réellement de la vitesse en prenant des blocs de 4 chiffres? :

Utiliser 4 chiffres peut être une bonne méthode, mais il faut mieux commencer par quelque chose de simple et lent qui fonctionne plutôt quelque chose complexe et rapide qui ne fonctionne pas.

Dans un premier temps, je te conseillerai donc de rester sur du chiffre à chiffre et d'optimiser quand tu en verras les limites.

[nocta]

Ok, je pense que tu as raison. De toute façon ca y est j'ai commencé avec du chiffre par chiffre.
Merci beaucoup.

[Sve@r]

Ok, je pense que tu as raison. De toute façon ca y est j'ai commencé avec du chiffre par chiffre.
Merci beaucoup.

Petite astuce: pense à inverser tes nombres. Ca te permettra de les caler sur la bonne unité.

Exemple: tu dois additionner 123 et 45.
Soit tu laisses dans ce sens et tu seras obligé d'additionner l'élément [3] du premier avec l'élément [2] du second, puis l'élément [2] du premier avec l'élément [1] du second etc...
Soit tu les inverses ce qui donne 321 + 54 et là, tu additionnes les deux éléments [0] puis les deux éléments [1] puis l'élément [2] du premier qui est tout seul (mais qui pourrait avoir une retenue) ce qui donne 861 puis ensuite tu inverses le résultat => 168

PS: ce que tu cherches à faire existe quand-même déjà => http://gcc.gnu.org/onlinedocs/gcc/Decimal-Float.html

[droggo]

Gai,

Bonjour,

Une idée serait de ne jamais travailler sur des types de base, mais seulement sur des chaines de caractères.

En gros cela reviendrait à créer un programme qui compte comme nous : directement en décimal, sans passer par du binaire.

Oui, mais c'est aussi un moyen d'obtenir des performances catastrophiques.

Les algorithmes requis s'implémentent aussi facilement en utilisant la largeur native du processeur, alors pourquoi se passer de la puissance (quand on commence à avoir besoin de ce type de calcul, on a généralement besoin d'aller vite).

Pour nocta : faire une telle bibliothèque est assez simple, mais ça devient long à faire si tu veux optimiser correctement, et tu n'échapperas pas à l'assembleur.
Si c'est seulement pour l'utilisation, il faut mieux prendre ce qui existe déjà, et GMP est là pour ça.

[Obsidian]

Oui, mais c'est aussi un moyen d'obtenir des performances catastrophiques.

Les algorithmes requis s'implémentent aussi facilement en utilisant la largeur native du processeur, alors pourquoi se passer de la puissance (quand on commence à avoir besoin de ce type de calcul, on a généralement besoin d'aller vite).

Je plussoie.

Ramener le problème au décimal est autant un piège à éviter qu'utiliser les formats natifs de sa machine une habitude à prendre. Mais je pense qu'à ce stade, l'important est surtout de savoir ce que nocta veut vraiment faire :

• Écrire une lib pour pouvoir gérer les grands nombres dans ses projets. Dans ce cas, il faut plutôt se tourner vers GMP ou équivalent ;
• Écrire cette lib pour l'exercice. Dans ce cas, se rapprocher des types natifs ;
• Écrire cet outil à titre pédagogique, pour pouvoir afficher directement les chiffres, faire des exemples d'arithmétiques, etc. Dans ce cas, on peut travailler au niveau du chiffre décimal en le stockant dans un tableau, quitte à perdre des bits. Après tout, c'est pour des besoins similaires qu'on a défini le BCD. Mais il faut être sûr que c'est bien la finalité de la chose.

[nocta]

Veuillez m'excuser pour cette réponse tardive.
En fait je souhaite concevoir cette lib pour deux choses:
-l'utiliser dans le cadre d'un projet de cryptographie/authentification basé sur l'utilisation des courbes elliptiques,
-et d'autre part montrer, de facon explicite, la necessité d'utiliser des algorithme spéciaux pour l'utilisation des grands nombres.

Je suis donc à cheval entre l'utilisation d'une bonne lib telle GMP, et la conception d'une lib par mes soins. Mais plus j'avance plus je me dit que cette derniere option n'est pas vraiment réalisable, ou ne sera pas operationelle.

[droggo]

Goa,

-et d'autre part montrer, de facon explicite, la necessité d'utiliser des algorithme spéciaux pour l'utilisation des grands nombres.

Il est de fait que les algorithmes "naïfs" sont vite dépassés dès que les nombres s'allongent.

Je suis donc à cheval entre l'utilisation d'une bonne lib telle GMP, et la conception d'une lib par mes soins. Mais plus j'avance plus je me dit que cette derniere option n'est pas vraiment réalisable, ou ne sera pas operationelle.

Oui. Comme déjà dit, ce n'est pas compliqué, mais assez long à implémenter, surtout si tu veux tous les algorithmes "rapides" sur les grand nombres, sans parler du temps passé en tests ...

À mon avis, la solution pour toi est d'utiliser une bibliothèque prête à l'emploi.

[nocta]

En ce cas une derniere question: en essayant de compiler GMP, j'obtiens une erreur à la commande 'make', et la reponse:
make: *** Pas de cibles spécifiées et aucun makefile n'a été trouvé. Arrêt.

Quelqu'un a une idée??

[Invité(e)]

As tu lancé ./configure avant ?

[nocta]

oui, j'ai suivi la procedure suivante:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
wget http://ftp.sunet.se/pub/gnu/gmp/gmp-4.2.3.tar.gz
tar xfz gmp-4.2.3.tar.gz
cd gmp-4.2.3
./configure --enable-cxx
make
make check
sudo make install
cd ..
rm -rf gmp-4.2.3 gmp-4.2.3.tar.gz
cd /usr/lib/
sudo ln -s /usr/local/lib/libgmpxx.so.4 libgmpxx.so.4