Le TP est à rendre, par email, avant le mercredi 21 avril à 20h...
Pour ce TP comme pour les suivants, la pièce la plus importante sera une archive tp1-nom-prenom.tar contenant votre programme. J'insiste sur les points suivants :
tar (éventuellement au format tar.gz ou tar.bz2),
tp1-nom-prenom contenant votre code (elle ne crée rien d'autre dans le répertoire courant),
Makefile pour compiler votre programme, avec au minimum les cibles all et clean.
Le non-respect des ces consignes risque de me mettre de mauvaise humeur... (Remarque : un fichier Makefile basique mais modulaire est disponible ici.)
Attention, le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :
Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier principal. Si vous le souhaitez vraiment, vous pouvez aussi m'envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :
README au format texte (mais avec un minimum de mise en page),
.odt),
Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :
-Wall -Werror -Wextra -pedantic -std=c99,
info614, ou info-614 ou info 614,
La bibliothèque GMP est une bibliothèque pour manipuler des nombres (entiers, rationnels ou flottants) avec une précision arbitraire. Les initiales signifient « GNU Multi Precision ». Pour compiler du code utilisant cette bibliothèque avec gcc, il faut ajouter le drapeau de compilation -lgmp. (Il faut bien entendu que la bibliothèque soit installée sur votre machine. Pour Debian ou Ubuntu, il s'agit du paquet libgmp3-dev.)
Nous allons essentiellement nous intéresser aux nombres entiers. Pour GMP, un entier est simplement un tableau de « chiffres ». Les types suivants sont définis par GMP :
mpz_t pour le type des entiers signés (mp pour « multiprecision », z pour le symbole mathématique des entiers Z, et _t pour « type »),
mp_limb_t pour le type des « digit » (normalement un entier machine 32 ou 64 bits).
En fait, le type mp_limb_t est plus général que juste des « digit », mais cette intuition est suffisante pour les entiers.
Les autres types importants sont :
mpq_t pour le type des rationnels,
mpf_t pour le type des flottants avec mantisse arbitraire et exposant borné.
Je vous renvoie à la documentation, et plus particulièrement à la partie sur les entiers et celle sur les fonctions de formatage.
J'attire votre attention sur le fait que toutes les opérations sur les grands entiers sont en passage par adresse. Ceci vient du fait que les grands entiers sont stockés dans des tableaux, et que l'on veut pouvoir contrôler l'utilisation de la mémoire.
En regardant le fichier /usr/include/gmp.h (ou /usr/include/gmp-ARCH.h), cherchez les définitions des types
mp_limb_t,
mpz_t.
Qu'en pensez-vous ?
Écrivez à la main une fonction de prototype
void initialise_grand_entier (mp_size_t t, mpz_t grand_entier) ;
qui alloue l'espace mémoire demandé pour un grand entier et initialise le grand entier à 0.
mpz_init(mpz_t grand_entier) pour initialiser vos entiers multiprécision. Comme la re-allocation de mémoire est automatique, on n'a pas besoin de préciser la taille de l'entier...
mpz_clear (mpz_t grand_entier) lorsque vous n'avez plus besoin d'utiliser des grands entiers.
Écrivez une petite fonction qui affiche le contenu d'un grand entier, digit par digit. Affichez également les autres informations contenues dans l'entier :
void affiche_grand_entier(mpz_t n) ;
Pensez à tester votre fonction sur des entiers petits, grands, positifs, négatifs, etc. Expliquez ce que vous observez...
Pour faciliter l'affichage des digits, vous pouvez utiliser la fonction gmp_printf qui permet d'afficher des entiers, des digits et autres, tout en suivant les conventions de la fonction printf habituelle. (Voir ici pour les nouveautés par rapport à printf.)
(falcultative, bonus) Programmez une fonction d'addition des grands entiers :
int addition (mpz_t resultat, mpz_t a, mpz_t b);
Cette fonction renverra 0 ou 1 suivant qu'il y a eu un dépassement de capacité, càd si l'on a du réalloué de la mémoire pour stocker le résultat.
Programmez votre propre version de la fonction mpz_powm qui permet de calculer x^n (mod m) de deux manières différentes :
void puissance_naive (mpz_t resultat, mpz_t x, mpz_t n, mpz_t m) ; void puissance_chinoise (mpz_t resultat, mpz_t x, mpz_t n, mpz_t m) ;
Vous n'avez bien entendu pas le droit d'utiliser la fonction mpz_powm, mais vous pouvez utiliser les fonctions mpz_add, mpz_mul ou mpz_cmp.
Comparez l'efficacité de vos deux fonctions, et comparez la seconde avec la fonction de GMP. Expliquez votre démarche et donnez vos résultats.
Reprogrammez votre propre version de la fonction gcdext qui calcule le pgcd de deux nombres ainsi que les nombres de Bezout associés :
void pgcd_bezout (mpz_t g, mpz_t x, mpz_t y, const mpz_t a, const mpz_t b) ;
N'oubliez pas de tester votre fonction.
(Bonus) Programmez une petite interface de calcul modulaire multiprecision que vous appellerez dans votre fonction principale.
Votre interface pourra par exemple vous permettre :