Home

Rapport

1. division d un nombre A de 2n mots par un nombre B de n mots tel que B soit normalis autrement dit que le reste de la division tienne sur n mots Cette division sert pour l algorithme d criture en diviser pour r gner Voici l algorithme Algorithm 7 Division de deux grands nombres avec B normalis Entr e deux grands nombres A 5 a 23 gt et B 5 bi 232 normalis Sortie un grand nombre C 55 c amp 23 pour le quotient et le reste dans A Pour i de n 1 0 faire Ci anpi 23 anpi 1 bn A A cB x232 Si A lt 0 Ci ci 1 A A B x23 Si A lt 0 Ci ci 1 A A B x 23 Retourner C On pourrait remplacer les deux Si ci dessus par une boucle n anmoins le th or me B partie 4 3 1 de l ouvrage de Knuth DEK nous indique qu elle n est parcourue au maximum que deux fois dans la condition que B soit normalis Deuxi me partie Autour de la r alisation 1 Strat gie et modalit s de validation Nous avons utilis la meilleure librairie C de calcul en pr cision arbitraire GMP afin de v rifier nos calculs sur des nombres comme 100 000 Les tests sur des nombres de moyenne importance 20000 chiffres ont t effectu s sur des puissances de 10 car en base 232 ces nombres s crivent de mani re non triviale et g n rent une multitude de cas particuliers De plus leur r sultat est tr s simple v rifier Le programme donn en exemple a aussi permis de
2. Q A 10 R Amod10 bn_1 00 Ecriture R bn bn Ecriture Q Renvoyer B Des pr cisions concernant la division utilis e viendront plus tard 3 Op rations arithm tiques sur les grands nombres 3 1 Addition 3 1 1 Algorithme L algorithme est celui utilis depuis l cole primaire Page 6 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Algorithm 4 Addition de deux grands nombres Entr e deux grands nombres A 5 4 23 et B 577 b 2 Sortie un grand nombre C DEN EDR Variable retenue 0 n lt min n m Pour i de 1 n faire Ci ai bi retenue retenue a b 2 Retourner C 3 1 2 Note pour l addition en assembleur avec MMX L addition avec MMX comporte une particularit il n y a pas de modifica tion de drapeau pour l addition MMX On calcule la retenue partir des bits les plus significatifs des deux mots et du bit le moins significatif du r sultat correspondant par la formule retenue a amp b C c amp Ca lb 3 2 Multiplication Nous avons disposition une ribambelle d algorithmes diff rents le na f l algorithme de Karatsuba celui de Toom Cook celui utilisant les NTT Nume rical Theoretic Transforms ie des FFT sur un corps fini avec une arithm tique modulaire Nous avons impl ment les deux premiers L algorithme de Karatsuba n tant plus rapide que l algorithme na f qu au dessus d un certain s
3. de la base choisie 1 1 Repr sentation des grands entiers Il existe un nombre infini de bases n anmoins nous pouvons d gager deux types de bases possibles simplifiant les calculs sur ces polyn mes dans l optique du projet 1 Microsoft TM Windows R Page 3 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR D une part les bases du type 10 celles ci ont l avantage de simplifier et de rendre intuitifs l criture des polyn mes qui se rapproche de notre sys t me de num ration mais ont pour inconv nient de demander des calculs plus lourds par exemple au niveau de la gestion des retenues pour une addition De plus la m moire tant scind e en lements de taille de type 2 une partie de cet espace m moire reste inutilis e D autre part les bases du type 2 elles ont l avantage de simplifier les cal culs par exemple les additions avec retenue qui directement c bl es dans le processeur et d utiliser toute la m moire disponible N anmoins les fonctions de conversion ne sont pas triviales Au vu des objectifs et de la disponibilit d ordinateurs architecture 32 bits ceux qui seront utilis s pour la pr sentation nous avons choisi la base 232 1 2 Mise en uvre de la structure de donn es en C La mise en oeuvre de cette base dans une repr sentation en C est telle que nous la trouvons d une part union umot cf ARPL h compos e de plusieurs structures donnant chacune une repr sent
4. shell Cygwin fera peut tre l affaire Placez vous dans le r pertoire de l archive du projet D compressez l archive 1 tar xvjf projet ieda albar aceituno tar bz2 Ensuite placez vous dans le r pertoire du projet 1 cd projet _ieda Vous devez maintenant compiler le projet En effet il est fourni avec un fichier ex cutable arpcalc mais celui ci n est certainement pas optimis pour votre architecture les calculs de temps seront erronn s Ce fichier ex cutable est uniquement l au cas o vous ne parvenez pas compiler le projet Essayons tout de m me Pour commencer nettoyons tout cela 1 make clean Ensuite il faut compiler toutes les sources Attention des avertissements vont appara tre sous vos yeux bahis Ceux ci ne d noncent pas une fragilit du code nous avons activ tous les avertissements possibles dans GCC Compilez avec 1 make Apr s une attente voici un moment bien m rit Vous allez pouvoir jouer avec le programme si tout s est bien pass ce qui est le cas bien entendu Lancez le programme en tapant Page 10 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR 1 arpcalc Vous verrez que le programme ne calcule rien et se termine apr s quelques explications Ce sont celles ci que vous pouvez suivre afin de mener bien des exp rimentations diaboliques La syntaxe du programme est la suivante 1 arpcalc lt operation gt lt a
5. 2 77 32 Lao et B bi 2 77 32 bo gros Karatsuba a1 b petit Karatsuba ao bo moyen Karatsuba ao a1 bo b1 moyen moyen petit gros min m n Retourner C gros 27 mm x82 1 moyen 2 27 32 petit 3 2 3 Performances Nous avons test les deux algorithmes sur des nombres quilibr s de m me taille de diff rents calibres sur un PC Pentium 4 3 00 GHz Nombre de chiffres Na f sec Karatsuba sec 1000 0 000078 0 000038 5000 0 001931 0 001213 8000 0 004718 0 002644 12000 0 018077 0 008590 20000 0 031245 0 010562 100000 0 767737 0 167462 On remarque que l algorithme de Karatsuba devient r ellement efficace pour des assez grands nombres mais pas pour 1000 qui n utilise que des multiplica tions par des petits nombres Cette efficacit se perd lorsque les nombres deviennent tr s d s quilibr s 4 Division Il existe plusieurs algorithmes de division N anmoins ceux ci sont nette ment plus complexes impl menter que ceux pour la multiplication On peut citer parmi eux l algorithme de Knuth DEK celui de Burnikel Zieger et la m thode de Newton m thode it rative convergence quadratique qui donne une approximation de l inverse d une s rie 1 Algorithme D Partie 4 3 1 2 Qui est aussi inventeur de TEX Page 8 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Nous avons impl ment l algorithme de Knuth dans le cas le plus favorable
6. 4 Introduction L objectif du projet d IEda est de construire un ensemble de fonctions r a lisant des op rations primaires sur des grands nombres entiers sans perte de pr cision Ces op rations addition et multiplication sont r alis es en C et en assembleur En tant que mise en uvre pratique de cette biblioth que une fonction de calcul de la factorielle d un nombre doit tre impl ment e Celle ci permettra en plus de juger de la rapidit des op rations arithm tiques de base C est selon ce crit re qu est choisie une repr sentation ad quate pour le calcul sur des grands entiers Ce projet permet de mettre en application les bases de programmation C et assembleur vues dans le cadre de l UE les structures de donn es dynamiques et pour notre part l optimisation par l utilisation de jeux d instructions sp cifiques aux processeurs compatibles Pentium 4 MMX SSE La recherche dans le domaine du calcul en pr cision arbitraire a clair nos choix et a permis outre la r alisation du projet de d couvrir une vaste tendue d algorithmes et de th ories math matiques La premi re partie du rapport est centr e sur la description de notre r ali sation sous toutes ses facettes On y trouvera les justifications de nos choix de d veloppement La deuxi me partie s oriente sur tout ce qui tourne autour de la r alisation comme les strat gies de test la r partition des t ches ou un mode d emploi succint
7. IE4a Projet 2008 Arithm tique sur de grands entiers en C et en assembleur ACEITUNO Jonathan ALBAR Boris 4 Juin 2008 Table des mati res I Description d taill e de la r alisation 1 Repr sentation des donn es 1 1 Repr sentation des grands entiers 1 2 Mise en uvre de la structure de donn es en C 2 Conversion des donn es 2 1 Passage de la repr sentation utilisateur la repr sentation interne lecture sine RU Re dense does ge did Rue 2 2 Passage de la repr sentation interne la repr sentation utilisateur criture Taar edi NS SA rs NAN MST a 3 Op rations arithm tiques sur les grands nombres SL Addition ee use Ba DEE TE A SA FE A e e ENEN 8 1 1 Aloimme se pK RATE a A mat A A RRE E 3 1 2 Note pour l addition en assembleur avec MMX 32 Multiplication 2 0 ets pok sa mn i i HR en E 3 2 1 Algorithme na f de multiplication 3 2 2 Algorithme de multiplication de Karatsuba 3 2 3 Performances un Dies Ne he pepe ie 4 Division II Autour de la r alisation OS TI I I co RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR 1 Strat gie et modalit s de validation 9 2 R partition des t ches 10 3 Mode d emploi 10 3 1 Utiliser le programme d exemple 10 3 2 Utiliser la librairie sss 28 Go mn un nes QE 11 4 Perspectives d am liorations 12 III Annexe 13 A Bibliographie 13 B Code source 1
8. Page 2 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Premi re partie Description d taill e de la r alisation Le choix de la plateforme de d veloppement s est port sur un syst me com patible UNIX en utilisant les outils de d veloppement GNU sauf Emacs La justification de ce choix est vidente au vu de la concurrence Nous avons volontairement omis de d tailler les fonctions telles qu elles sont crites car la plupart ne sont que des outils pour des fonctions plus g n rales Interpr tation personnelle des objectifs R aliser des op rations de base addition multiplication soustraction di vision d calage lecture et criture dans une cha ne sur des nombres ar bitrairement grands Rapidit d ex cution sur des nombres de taille moyenne jusqu 200000 chiffres Impl mentation d algorithmes non na fs pour les op rations les plus co teuses multiplication criture Utilisation des possibilit s particuli res des processeurs i686 1 Repr sentation des donn es Un nombre peut tre consid r comme un polyn me P dans l espace des polyn mes R X c est dire sous la forme P X aX Ou comme une s rie nulle partir d un certain rang P o4 X tel qu il existe N N avec Yn gt N an 0 L ind termin X d un polyn me repr sente la base dans lequel le nombre s exprime Rappelons que les coefficients du polyn me sont fonction
9. Sortie un grand nombre B J b 2 Variables total b Pour tout a faire total total a 10 D duire les b en connaissant la somme total et la taille des b par divisions successives Renvoyer B On aurait pu impl menter un algorithme de lecture de complexit moindre de type diviser pour r gner PZ n anmoins la rapidit des multiplications par 10 a rendu cette t che moins urgente 2 2 Passage de la repr sentation interne la repr senta tion utilisateur criture Il faut donc ici passer d une base par exemple 232 la base 10 en cha nes de caract res L algorithme de conversion na f est le suivant Page 5 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Algorithm 2 criture d un grand nombre en repr sentation utilisateur com plexit O n Entr e un grand nombre A 57 a 2 21 Sortie un entier B 5 b 10 Variable reste Sa Pour i de 1 n faire bi reste mod 10 reste reste 10 Renvoyer B Cet algorithme est limit du fait des divisions successives par 10 qui sont co teuses en temps processeur Nous avons donc impl ment un algorithme r cursif d criture de type diviser pour r gner Algorithm 3 criture d un grand nombre en repr sentation utilisateur com plexit O z D n avec a et D n d pendant du co t de la division Entr e un grand nombre A 37 a 2 Sortie un entier B 3 b 10 n lt m 2
10. ation diff rente par exemple 32x1 bits 8x4 bits ou 1x32 bits sont des repr sentation possibles Ceci tant rendu possible par l utilisation d une astuce peu connue du compilateur GCC pr sente aussi sur d autres compilateurs comme celui d Intel consistant sp cifier la fin de chaque l ment sa part en nombre de bits dans l union par exemple un unsigned long a 8 comptera pour 8 bits dans l union L union etant caract ris en C par le partage d un espace m moire entre diff rentes structures de donn es chaque repr sentation est accessible simultan ment Autrement dit on pourra acc der aux 8 bits de poids fort sans masque de bits et de fa on compl tement triviale La deuxi me structure entrant en jeu dans le programme est celle repr sentant un nombre en pr cision arbitraire elle comporte un pointeur vers un tableau de umot des entiers donnant le signe la base et la longueur du tableau pr c dent c est dire le nombre de coefficients du polyn me En voici le code 1 struct arpn 2 pointeur vers un tableau de n mots de base bits umot xmots nombre l ments allou s n unsigned long maxdeg J signe 1 long signe base 2 base unsigned long base O 01 amp 10 Listing 1 Structure de donn es pour un grand nombre Des typedef permettent d utiliser les structures d crites pr c demment la mani re de typ
11. e car elle est trop souvent n glig e de nos jours au vu de la puissance des ordinateurs actuels Cela nous a permis de nous prendre pour des John Carmack en herbe L criture d un rapport avec ETEX nous a permis de le ma triser encore un peu plus cet outil fantastique Ce projet montre vraiment quel point le logiciel libre et les syst mes UNIX sont puissants et agr ables utiliser Toute alternative est vou e terme l chec sauf les syst mes BSD sauf Mac OS X sauf Darwin sauf XNU sauf Mach Troisi me partie Annexe A Bibliographie R f rences DEK D E Knuth Art of Computer Programming vol 2 Addison Wesley PZ P Zimmermann Arithm tique en pr cision arbitraire Rapport IN IRA n 2372 IMQ Michel Quercia Calcul multipr cision TGPLM T Granlund P L Mongomery Division by Invariant Integers using Multiplication DJB D J Bernstein Scaled Remainder Trees CBJZ C Burnikel J Ziegler Fast Recursive Division RBPZ R Brent P Zimmermann Modern Computer Arithmetic Le nec plus ultra en complexit Page 13 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR B Code source Le code source est imprim s par ment Page 14
12. es de variable ce qui all ge grandement la notation Page 4 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Notons au passage que la taille des l ments de la structure ci dessus n a pas t choisie au hasard Elle a t choisie pour tre align e sur 16 bits Autrement dit la somme des tailles des l ments est gale 16 Si la structure n tait pas align e le compilateur l alignerait automatiquement en ajoutant des bits non utilis s 2 Conversion des donn es Les nombres entr s par l utilisateurs sont repr sent s sous forme de cha nes de caract re que l on nommera repr sentation utilisateur Il a fallu construire et optimiser des fonctions de conversion de la repr sentation utilisateur la repr sentation interne Ces op rations sont tr s co teuses en temps du fait de divisions sucessives par 10 n cessaires au changement de base De plus la com plexit de l op ration est en O n pour l algorithme na f Cela a motiv la recherche d algorithmes de conversion poss dant une complexit moindre 2 1 Passage de la repr sentation utilisateur la repr sen tation interne lecture On suppose la transformation d une cha ne de caract res un entier de pr cision arbitraire en base 10 triviale L algorithme de lecture na f est donc le suivant Algorithm 1 Lecture d une cha ne de caract res en repr sentation interne complexit O n Entr e un entier A J a 10
13. euil d fini empiriquement suivant le processeur l algo rithme est choisi suivant la taille des op randes 3 2 1 Algorithme na f de multiplication C est aussi le m me qu l cole Rappelons nous Algorithm 5 Multiplication na ve de deux grands nombres en complexit O n Entr e deux grands nombres A 577 a 2 et B 517 b 2 Sortie un grand nombre C Ha Cy 292 4 ess nel E ai B Pour i de 1 m faire Ci m TA c1 Le 0 Ci 1 m ag c1 ai B Retourner C 3 2 2 Algorithme de multiplication de Karatsuba L algorithme de Karatsuba se base sur une jolie astuce Avec P a1 X ao et Q b X bo on a le produit P Q a X ao b1 X bo ab X aob1 X boai X aobo Page 7 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR Avec cette formule on calcule quatre produits C est beaucoup trop En bridant on peut r duire le produit trois multiplications seulement P Q aib X ar ao b1 bo LE aobo o ab X aobo De mani re r cursive on parvient tendre cette propri t n importe quel polyn me donc l criture d un nombre sur n importe quelle base La mise en uvre de cet algorithme est la suivante Algorithm 6 Multiplication de deux grands nombres par l algorithme de Karatsuba en complexit O n 53 Entr e deux grands nombres A 3 a 23 t et B 5 i282 Sortie un grand nombre C Do qi 2321 On pose a
14. mp resultat 22 23 Tout s est bien pass 24 return Q 25 Sympathique n est ce pas 4 Perspectives d am liorations D autres optimisations auraient pu tre impl ment es tant au niveau de l utilisation du mat riel utilisation des extensions SSE3 utilisation des capaci t s des GPU des cartes graphiques r centes sous r serve d une impl mentation des op rations en pr cision arbitraire sur des nombres flottants que de l occu pation m moire supprimer l utilisation de m moire de mani re r cursive dans la fonction d criture en divide and conquer ou des algorithmes utilis s par 1 mais tout de m me long Page 12 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR exemple division de Burnikel et Zieger CBJ7 trouv e en 1998 ou encore le tout dernier algorithme de multiplication de F rer Le programme d exemple aurait pu tre un vrai invite de commandes dyna mique mais les semaines sont courtes Au niveau de l utilisation de la librairie des efforts pour en faire un vrai module sont encore faire mais cela d passe le cadre du projet Conclusion Il a t b n fique de r aliser ce projet tant au niveau math matique et th o rique que technique D utilisation de l assembleur AT amp T a t pour certains une d couverte et pour d autres un retour aux sources La recherche effr n e de l optimisation et de l efficacit fut une entreprise int ressant
15. n ConvToArpn char nombreUtilisateur Convertit une cha ne de caract res en grand nombre en base 23 arr te le programme s il y a une erreur unsigned char ConvToString_predc arpn nombre Convertit un grand nombre en cha ne de caract res arpn addition_naive arpn ni arpn n2 Additionne deux grands nombres Page 11 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR arpn multiplication_naive arpn ni arpn n2 Multiplie deux grands nombres arpn factorial_naive unsigned long nombre Calcule la factorielle d un petit nombre La liste ne s arr te pas l mais le reste est explorer seul ou entre ami e s Un petit programme d exemple supposant qu on le place dans le r pertoire de la librairie dans ce cas enlevez le fichier main c sinon il y aura deux fonctions main include ARPL h 1 2 3 Addition de 123 et de 1000 4 int main 5 On prend le premier nombre 6 arpn nombrel ConvToArpn 123 7 On prend le deuri me 8 9 arpn nombre factorial naive 1000 On fait l addition 10 arpn resultat addition naive nombrel nombre2 11 12 On convertit le r sultat en cha ne de caract res 13 unsigned char xresultatString ConvToString predc resultat 14 15 On imprime ce r sultat l cran 16 printf s n resultatString 17 18 Important il faut tout lib rer 19 freenb amp nombrel 20 freenb amp nombre2 21 freenb a
16. rg1 gt lt arg2 gt Les op rations possibles sont les suivantes factorial Factorielle classique Utilisable de la fa on suivante arpcalc factorial 1000 add Addition na ve en Assembleur Utilisable de la fa on suivante arpcalc add 1 2 add_c Addition na ve en C Utilisable de la fa on suivante arpcalc add_c 1 2 multiply Multiplication na ve en Assembleur Utilisable de la fa on suivante arpcalc multiply 1 2 multiply _c Multiplication na ve en C Utilisable de la fa on suivante arpcalc multiply_c 1 2 test Le test ultime calculer 1000 fois 1000 puis mettre le dernier r sultat dans un fichier resultat txt Utilisable de la fa on suivante arpcalc test Le programme donne le r sultat et les temps temps avec conversion en repr sentation utilisateur et temps sans cette conversion Nous n avons pas cru bon de mettre disposition les multiplications avec l algorithme de Karatsuba pour des raisons de convivialit pour tester l algo rithme efficacement des nombres d au moins quelques milliers de chiffres sont n cessaires Bon amusement 3 2 Utiliser la librairie Vous souhaitez utiliser cette librairie dans votre programme Voici la liste des fonctions utiliser avec leurs param tres allocnb arpn xnombre unsigned long taille Alloue un grand nombre de taille donn e freenb arpn nombre Lib re un grand nombre A utiliser sans mod ration arp
17. v rifier la bonne marche de la librairie et d effectuer des corrections de derni re minute Voici un ordre de grandeur des r sultats obtenus avec le programme sur un Pentium M cadenc 1 70 GHz 1000 Sans conversion 0 402296 ms avec conversion 1 918406 ms 10000 Sans conversion 52 178376 ms avec conversion 205 057436 ms 100000 Sans conversion 6 123453 sec avec conversion 28 773915 sec Page 9 RAPPORT DE PROJET IE4A J ACEITUNO B ALBAR 2 R partition des t ches Recherche bibliographique sur papier Jonathan ACEITUNO Recherche bibliographique sur le plan algorithmique rapports de recherche de diff rents instituts Boris ALBAR Mise au point de la structure de donn es et de la repr sentation Jona than ACEITUNO et Boris ALBAR Ecriture des fonctions na ves C et ASM Jonathan ACEITUNO Ecriture des fonctions non na ves C et ASM avec MMX SSE SSE2 Boris ALBAR R daction du rapport Jonathan ACEITUNO et Boris ALBAR R daction de l annexe Boris ALBAR et Jonathan ACEITUNO pour la mise en page Ecriture de la fonction main et de l outil tools cpuspeed Jonathan ACEITUNO 3 Mode d emploi 3 1 Utiliser le programme d exemple Ce projet est fait pour tre ex cut et tudi sous environnement compatible UNIX Si vous avez une distribution Linux tant mieux et si vous tes allergique essayez tout de m me Sur Windows un

Rapport

Contents

Download Pdf Manuals

Related Search

Related Contents