Pour effectuer certains calculs, il est nécessaire de
manipuler de grands nombre cad des nombres qui dépassent la capacité d’un
registre 32 bits ou même de 2 registres 32 bits (doubles). Il serait possible
d’écrire les routines de calcul en multi précision en assembleur mais cela
représente un gros travail. J’ai préférais faire appel aux routines de la
librairie gmp déjà présente dans la version de raspbian pour le Raspberry pi.
Pour l’utiliser, il faut d’abord installer le package libgmp3-dev
et modifier le script de compilation pour effectuer le link avec gcc et
l’option –lgmp comme par exemple :
Comme exemple d’utilisation, nous allons résoudre le
problème N° 25 du projet Euler (voir https://projecteuler.net/archives
ou https://www.lucaswillems.com/fr/articles/19/project-euler-traduction-des-problemes-1-a-50)
Il s’agit de trouver le terme de la suite de Fibonacci qui
contient 1000 chiffres !!
Dans le programme, nous déclarons dans la zone BSS, 3 zones
qui contiendront les structures des nombres gérés par gmp. J’ai mis une taille
de 100 caractères mais la taille nécessaire doit être plus petite. En effet
l’espace nécessaire au stockage des milliers de chiffre est alloué dans la
mémoire dynamiquement par les routines et donc ces structures ne contiennent
que quelques données (type, taille, pointeur etc). Nous déclarons aussi une
zone qui recevra la valeur d’un nombre en caractères ascii ce qui permet de
compter ses chiffres.
Dans la partie code, nous initialisons à 1 un premier nombre
en appelant la routine __gmpz_init_set_ui. Cette routine correspond à la
routine mpz_init_set_ui de la documentation gmp. Donc il nous faudra modifier
le nom des routines pour pouvoir les utiliser depuis notre programme assembleur
en ajoutant __g (attention, pour certains routines ce préfixe pourra être
différent). Vous remarquerez que nous passons les adresses des structures
représentant les nombres par les registres habituels r0 et r1
Puis nous initialisons 2 autres nombres à zéro avec la
routine __gmpz_init. Nous trouvons ensuite une boucle qui va additionner
successivement 2 termes de la suite pour trouver le suivant avec la routine bl
__gmpz_add et nous convertissons le nombre trouvé en une chaine de caractères
par la routine __gmpz_get_str. Pour le calcul suivant, nous copions les nombres
en utilisant la routine __gmpz_set. Enfin, nous calculons la longueur de la chaine
convertie dans zone et nous testons si nous avons atteint le nombre de chiffre souhaité
sinon nous bouclons pour calculer le terme suivant.
Après la boucle, nous affichons le nombre pour contrôle par
la routine __gmp_printf puis nous l’affichons une deuxième fois avec l’instruction
__gmpz_out_str. La première nécessite un paramètre de formatage et pas la
seconde. Cette dernière m’a donné du mal car l’utilisation du code 1 pour la
sortie standard entraine une erreur. Il faut mettre 0 et d’après la doc, la
routine déterminera la bonne entrée ou sortie. L’autre problème est qu’il faut la
compléter par l’ instruction printf du C car autrement l’affichage ne se fait
pas !!!
Après quelques tests avec des petites valeurs, le programme
fonctionne avec la valeur 1000.
Dans le deuxième programme, nous allons saisir une chaine de
caractère représentant un grand entier positif par l’appel système Linux read,,
la convertir en grand entier avec la fonction __gmpz _set_str, calculer son
carré par la fonction __gmpz_pow_ui puis calculer sa racine carrée avec la
fonction __gmpz_sqrt.
Puis nous allons le convertir en nombre en virgule flottante
avec la fonction __gmpf_set_z calculer à nouveau sa racine carré mais avec la
fonction en virgule flottante __gmpf_sqrt et l’afficher correctement avec une
précision de 20 chiffres après la virgule.
Enfin nous allons saisir directement un grand nombre en
virgule flottante par la fonction __gmp_scanf et calculer sa racine carrée.
Attention, lors de la saisie, il faut saisir un point et non une virgule pour
séparer les 2 parties du nombre.
Dans la documentation gmp, vous trouverez toutes les fonctions
disponibles.
Aucun commentaire:
Enregistrer un commentaire