Aller au menu - Aller au contenu

Icône GMP - "Arithmetic without limitation"

L'auteur de ce cours cherche un repreneur pour continuer son travail
Parfois, certains auteurs de cours n'ont plus le temps de rédiger et de mettre à jour leur travail. Ils recherchent alors un nouvel auteur pour "reprendre" leur tutoriel (voir la liste des tutoriels en attente de repreneur).
Contactez l'auteur si vous aimeriez continuer la rédaction !

Par Avatar Simon Chabot (TuxWeb) et Avatar Toulousaing
Mise à jour : 09/09/2009
Creative Commons BY-SA
1 105 visites depuis 7 jours, dont 69 sur ce chapitre classé 112/786
Cette partie présente l'intérêt d'une telle bibliothèque et explique comment l'installer (sous GNU/Linux, et Windows), et finit par la création d'un petit programme d'exemple...
Retour en haut
Sommaire du chapitre :
Icône du chapitre
Chapitre précédent Sommaire Chapitre suivant
Retour en haut

L'intérêt de cette bibliothèque

Euh... une bibliothèque ? mais c'est pour quoi faire ?

La bibliothèque GMP est une bibliothèque qui va nous permettre de gérer de très très grand nombre, et d'effectuer tout un tas de calculs rapidement.

Un "double" ou un "float" peut très bien pu suffir pour gérer nos grands nombres, non ? Pas la peine de prendre cette... GMP !

La réponse est non (vous deviez vous en douter ^^). Le type "double", le plus grand des
types primitifs, a pour extréma -1.7 \times 10^{308} et 1.7 \times 10^{308}. Or, je sais pas si vous vous rappelez, mais dans le chapitre sur le déchiffrage, on avait à un moment donné ce calcul : 386^{4279}. Autant vous dire que le résultat dépasse largement le type "double". (Même un "unsigned double" ne ferait pas l'affaire pour ceux qui y auraient pensé...)

Pour la petite histoire, j'ai calculé 386^{4279} avec la bibliothèque GMP, et le résultat est composé d'exactement 11069 chiffres, un double aurait rendu l'âme bien avant d'afficher le résultat ^^ . On ne peut donc pas se passer d'une telle bibliothèque pour faire notre programme.

Passons à l'installation :p .
Retour en haut

Installation sous Windows

Préparation...



Pour installer la bibliothèque GMP sous Windows, nous allons installer une sorte de paquetage, composé d'un shell (une console en gros :p ) et de plusieurs petits programmes, qui va nous permettre de compiler les sources de la bibliothèque, pour que l'on puisse ensuite s'en servir... Ce paquetage ce nomme MSYS, et est disponible en téléchargement ici.

Pour continuer, vous devez avoir MinGW d'installé sur votre machine ! Si ce n'est pas le cas, vous devez le faire. (Si vous avez Dev-Cpp ou Code-Blocks, il doit être présent...)


Allez dans le répertoire d'installation de MinGW, puis dans le dossier "bin". (Ce répertoire est pour ma part "C:\MinGW", mais il peut être "C:\Dev-Cpp", tout dépend de votre machine) Dans ce répertoire "bin", vous devriez trouver un fichier nommé "mingw32-make.exe". Copier-le dans ce même dossier sous le nom de "make.exe".

Il faut maintenant installer MSYS. Lancer l'exécutable téléchargé. Les options par défaut devraient faire l'affaire. A la fin de l'installation, une console s'ouvre et vous pose quelques questions. Répondez par "y" aux deux premières questions. On vous demande ensuite où est le dossier d'installation de MinGW. Copiez-y alors l'adresse de ce dossier.

Voici un screen de ce que j'ai :

Image utilisateur


Répondez aux questions suivantes par "y" puis Entrée.

Une fois ceci fait, nous pouvons télécharger la bibliothèque proprement dite. Rendez-vous sur la page de téléchargement du site, à savoir ici. Téléchargez l'archive de la dernière version de la bibliothèque. Extrayez ensuite l'archive dans un dossier facile d'accès... "C:\gmp" par exemple.


Compilation...



Nous pouvons dorénavant compiler la bibliothèque. Pour ce faire, lancez MSYS. (Double-cliquez sur l'icône MSYS de votre bureau pour le lancer.) Une console s'ouvre...

Déplacez-vous dans le dossier où sont les sources de GMP, grâce à la commande "cd", ce qui donne : cd c:/gmp

Ensuite il faut préparer et vérifier si la compilation de la bibliothèque est faisable. Cette préparation se fait avec la commande suivante : ./configure --prefix=/c/dev-cpp --enable-cxx

Note : Remplacez "c/dev-cpp" par le chemin correspondant à votre IDE. Si le chemin de votre IDE est "C:\Code-Blocks\" tapez "c/Code-Blocks"

Laissez travailler. Une fois cela fini (Il ne devrait pas y avoir d'erreur...) On peut compiler... La compilation se fait avec la commande : make. La compilation peut être longue... Il faut être patient ^^ . A la fin de la compilation, tapez make check puis make install, pour installer la bibliothèque. (Encore un peu de patience... ^^ )

Normalement, rendu à ce point, la bibliothèque devrait être (correctement) installée.

(Si tout c'est bien déroulé, vous devriez avoir dans le dossier "include" de votre IDE les fichiers "gmp.h" et "gmpxx.h")
Retour en haut

Installation sous GNU/Linux

Normalement, la bibliothèque GMP est déjà installée sur votre machine si vous avez suivi le tutoriel dans l'ordre. Si vous l'avez installé, vous pouvez aller directement à la dernière partie de ce chapitre. Sinon ouvrez une console et copiez-y :

Code : Console
cd ~
mkdir RSA
cd RSA
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
cd ~/RSA




Voilà, c'est installé ^^

                

                
Retour en haut

            
                

                    

                        Créer un projet avec notre nouvelle bibliothèque
                        
                    


                    
Notre premier programme




Afin de voir si tout fonctionne correctement, on va faire un petit programme (très simple) qui affiche une liste de nombres premiers...



Créez un nouveau projet et dans le fichier "main.cpp" copiez le code suivant : (Je vous expliquerais plus en détail comment utiliser cette bibliothèque, ce code est juste fait pour vérifier si le tout marche, et montrer comment on link la bibliothèque...)



Code : C++
 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
/* Ce code a pour but d'afficher, grâce à une boucle, un nombre déterminé de nombres
 premiers */

#include <iostream>
#include <gmpxx.h> //On inclut la bibliothèque gmp

#define MAX 10 //On affichera MAX nombres premiers...

int main(int argc, char **argv)
{
	mpz_class a(0); //On créé un objet mpz_class nommé a. On l'initialise à zéro.

	//On va calculer puis afficher MAX nombres premiers
	for(int i = 0 ; i < MAX ; i++)
	{
		//Cette fonction attribue à "a" le premier nombre premier après "a"
		mpz_nextprime(a.get_mpz_t(), a.get_mpz_t());

		std::cout << a << " "; //On affiche le nombre a.
	}

	std::cout << std::endl; //On saute une ligne avant de quitter

	return 0;
}








Compiler notre code





Avec un IDE




Si vous utilisez un IDE, vous devez linker la bibliothèque avec le fichier "libgmpxx.a" situé dans le dossier "lib" de votre IDE, puis avec "libgmp.a" (L'ordre est important !). Avec Dev-Cpp, j'ai ceci : (Cliquez sur l'image pour la voir en plein écran)




Image utilisateur




Comme vous pouvez le constater, j'ai placé sur l'image des petits numéros, ils vous permettent de vous repérer quant à l'ordre des opérations à effectuer.



Une fois cela fait, vous pouvez ensuite compiler... Tout devrait bien se passer.






Avec un makefile




Si vous utilisez makefile ou la ligne de commande pour compiler, vous devez linker la bibliothèque avec vote programme en tapant : -lgmpxx -lgmp. Ce qui donne par exemple : g++ -o executable main.cpp -lgmpxx -lgmp



Et voilà, votre programme devrait compiler et fonctionner correctement. Il devrait afficher ceci : 



Code : Console
2 3 5 7 11 13 17 19 23 29

                

                
Retour en haut

            


Nous venons d'installer la bibliothèque GMP, dans le prochain chapitre, nous verrons quelques fonctions de bases de cette bibliothèque, et nous attaquerons notre programme de chiffrage.



Vous pouvez, si le cœur vous en dit, d'ores et déjà consulter la documentation de GMP, disponible au format PDF, ici.



    

        
            
            
        
    


    

        
            

                

                    
                    
                    
                

            

        
            Chapitre précédent
        
            Sommaire
        
            Chapitre suivant
        
    







    
Retour en haut



    
Partager

    


    


    

    
Retour en haut

    
            

                18 commentaires pour "GMP - "Arithmetic without limitation""
                

                    Note moyenne :
                        3.71
                    / 4
                    (31 votes)
                    
                

            

        
        

            
              

                Pseudo
                Commentaire
              

            
            
              
                

                  
                    
                      Hors ligne 
                    
                      zouou
                    
                  
                  
                    #
                    
                         Posté le 05/08/2010 à 21:07:34
                    
                    
                


                
                    

                
                
                    




    





                		
                
                    
                    Bonjour,

J'essaie d'installer gmp pour pouvoir l'utiliser sur Visual Studio 2008 mais je bloque pour trouver le chemin d'accès de celui ci (compilateur). afin de faire de faire le test:

Remplacez "c/dev-cpp" par le chemin correspondant à votre IDE. Si le chemin de votre IDE est "C:\Code-Blocks\" tapez "c/Code-Blocks" (cf tuto)



Merci.

A bientôt!
                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      lordofzejeux
                    
                  
                  
                    #
                    
                         Posté le 29/10/2010 à 12:26:53
                    
                    
                


                
                    

                
                
                    




    





                		
                
                    
                    Personnellement j'ai rencontré quelques soucis a l'installation de GMP donc j'espère pouvoir aider les autres en les montrant avec leurs résolutions.



-Tout d'abord grace à un commentaire plus haut j'ai découvert que lorsque une console demande un chemin absolu avec des espaces dedans il faut les faire précéder de "\" (l'antislash).



-ensuite lors de la compilation de la librairie j'avais des erreurs durant le Code : Console
make install


je n'ai pas vraiment compris mais j'ai contourné l'erreur et j'ai refait la compilation en enlevant l'argument Code : Console
--prefix=/c/dev-cpp
 de Code : Console
./configure --prefix=/c/dev-cpp --enable-cxx
 et j'obtiens donc Code : Console
./configure --enable-cxx
 et une fois les autres commandes effectuées (cette fois ci sans erreurs) je récupère les ".a" et les ".h" dans le dossier "local" situé dans le repertoire d'installation de MSYS soit chez moi : C:\msys\1.0 et je colle les fichiers dans les repertoires libs et includes de mon compilateur !

Avec cette lib j'ai adapté et amélioré les programmes présents dans l'autre tuto sur RSA (celui qui utilise python pour ses exemples) et j'ai des programmes bien plus rapides en c++.

En tout cas c'est un tuto très interessant mais parfois un peu flou. Je souhaite une bonne continuation !
                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      Alienore
                    
                  
                  
                    #
                    
                         Posté le 19/01/2011 à 15:33:33
                    
                    
                


                
                    

                
                
                    




     Études : Polytech'Lille






                		
                
                    
                    Citation
Un "double" ou un "float" peut très bien pu suffir pour gérer nos grands nombres, non ? Pas la peine de prendre cette... GMP !




La réponse est non (vous deviez vous en douter ^^). Le type "double", le plus grand des

types primitifs, a pour extrema -1.7 \times 10^{308} et 1.7 \times 10^{308}. Or, je sais pas si vous vous rappelez, mais dans le chapitre sur le déchiffrage, on avait à un moment donné ce calcul : 386^{4279}. Autant vous dire que le résultat dépasse largement le type "double". (Même un "unsigned double" ne ferait pas l'affaire pour ceux qui y auraient pensé...)




Il est utile de rappeler qu'il y avait un modulo avec. Les puissances sont gentilles avec les modulo.

Par exemple, 2^4 \equiv 1 [15]

On a donc 2^{2011} \equiv 2^{2008+3} \equiv 2^{4 \times 402} \times 2^{3} \equiv 8 [15]

Pourtant, je n'ai pas utilisé de calculatrice.



L'accroche est donc fausse puisqu'on n'a pas besoin de gérer de très grans nombres si on réfléchit un peu plus.

De plus, proposer un double (ou un float) est une aberration car c'est un nombre approximatif. On ne pourrait donc pas obtenir de valeur exacte à partir d'eux. (il n'y a qu'à essayer de mettre 10^50 + 1 dans un double, puis de lui retrancher 10^50)
                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      Elionor
                    
                  
                  
                    #
                    
                         Posté le 30/01/2011 à 21:24:03
                    
                    
                


                
                    

                
                
                    

Echec ...et Mat !!
Avatar



     Ville : Salé

	Pays : Maroc






                		
                
                    
                    Le lien de téléchargement du MSYS est mort, ou peut-on le télécharger ??
                    
                        
________________________________________________________

This is a signature .



                        
 

                    
                		
                

              
                

                  
                    
                      Hors ligne 
                    
                      platanex2
                    
                  
                  
                    #
                    
                         Posté le 03/04/2011 à 11:19:04
                    
                    
                


                
                    

                
                
                    




    





                		
                
                    
                    Bonjour à tous. Je me permets de faire part de ma petite expérience d'installation de GMP-4.2.3 sous codeblocks sous WIN XP SP3 (ce message reprend en partie le message que j'ai posté sur le forum) :



Installer codeblocks directement sur C:\ et MINGW avec, qui sera donc en c:\codeblocks\MINGW. Je n'ai pas renommé le fichier en make. J'ai pris celui de MSYS.

ATTENTION : Le dossier des .h de codeblocks est dans c:\codeblocks\MINGW\include donc si vous tapez exactement ce qu'il y a dans le tuto, gmp.h ne sera pas trouvé par codeblocks.

Installer MSYS et indiquez le chemin c:/codeblocks/mingw

lancer MSYS

Code : Autre
1
2
3

cd:/gmp
./configure --prefix=/c/codeblocks/mingw --enable-cxx
make && make check && make install


commentaire : 




(tout se fera à la suite en 2 ou 3 heures   :D )

/c/codeblocks/mingw installe gmp.h dans le dossier include de mingw (et pas include de codeblocks, qui n'existe pas et donc codeblocks ne va jamais y chercher gmp.h !!!!!)

on peut ajouter && à la fin de la 2ème ligne et continuer en tapant la 3ème et absolument tout se fera à la suite mais vous ne verrez pas les erreurs de configure...






Ce n'est pas fini !

Lancer codeblocks. Menu "settings>compiler and debugger". Onglet "linker settings" bouton "add" et taper (en deux fois" : libgmp.a et libgmpxx.a.

et normalement ça marche. "j'ai juste parfois des erreurs de taille de variable...)

J'espère avoir été utile.
                    
                        
WINDOWS XP SP3

CODEBLOCKS 10.10

bibliothèque GMP



                        
 

                    
                		
                

              
            
        

        
            
Voir tous les commentaires