La biblioth`eque GMP
Contents
1. 2 5 complexit On remarque que la d croissance dans les entiers est l g rement plus rapide que dans la version r elle gr ce aux arrondis Ceci permet d tendre le r sultat sur l excellente convergence de la m thode de Newton notre calcul dans les entiers 3 Impl mentation et tests empiriques Remarque 3 1 approximation grossi re Au d but de l algorithme IIL3 il faut choisir une valeur initiale x tel que x gt y Bien s r on pourrait prendre x y mais pour acc l rer il vaut mieux choisir une valeur proche de la racine 4 y mais bien entendu plus grande que celle ci Il y a plusieurs m thodes de le faire de mani re efficace En s inspirant de la recherche dichotomique on pourrait crire Integer x 1 while puissance x n lt y x 2 Il existe une variante plus rapide qui profite du fait que l entier y soit stock en base 2 A nsi il est facile de d terminer sa longueur 1 log gt y qui n est rien d autre que le nombre de chiffres binaires int len const Integer amp y return mpz_sizeinbase y get_mpz_t 2 int log2 const Integer amp y return len y 1 Ensuite on calcule ais ment x 2 lllog2y 7 en syst me binaire il ne s agit que d un d calage Integer x Integer 2 lt lt log2 y n d calage bit par bit V rifier que x y tout en assurant x gt y comme exig dans l algorithme V rifier que cette astuce s applique galement l2. aux fonctions standard 1 2 3 4 xxx Attention compiler avec g lgmpxx 5 include lt gmpxx h gt acc der la biblioth que gmp pour C 6 typedef mpz_class Integer Integer semble plus parlant que gmp_class 7 8 int main 9 4 10 cout lt lt Entrez deux entiers svp 11 Integer a b 12 cin gt gt a gt gt b 13 cout lt lt a lt lt a lt lt endl lt lt b lt lt b lt lt endl 14 lt lt a b lt lt a b lt lt endl lt lt a b lt lt a b lt lt endl 15 lt lt axb lt lt axb lt lt endl 16 if b 0 cout lt lt a b lt lt a b lt lt endl 17 lt lt a b lt lt ab lt lt endl 18 else cout lt lt La division par z ro n est pas d finie lt lt endl 19 1 On acc de la biblioth que GMP pour le C en incluant la directive include lt gmpxx h gt qui effectue les d clarations n cessaires Ensuite la compilation s effectue avec l option 1gmpxx pour tablir le lien vers les d finitions de cette biblioth que Sinon le compilateur mettra une longue liste d erreurs r clamant undefined reference to Comme vous voyez dans le programme III 1 nous avons renomm la classe mpz_class en Integer ce qui semble plus parlant Si jamais vous voulez remplacer mpz_class par une future classe nouveau_modele il suffit de modifier une seule ligne condition bien s r que nouveau modele impl mente les entiers
3. la suite r currente ug1 1 n z Lux au converge vers la racine r a Pour k gt 1 on a convergence monotone up N r Sym triquement pour vk alu ona vx r On obtient ainsi des encadrements explicites vg lt r lt ux de plus en plus fins vi Lva lt V3 L e Kr lt lt u3 lt u lt u Ajoutons que pour ug proche de la racine r la convergence est exponentielle chaque it ration le nombre de d cimales valables double peu pr s C est la convergence exponentielle qui fait de ce th or me un outil tr s puissant si vous avez calcul un encadrement vg ug 1072 pr s disons l it ration suivante ne laissera qu un cart 1074 celle d apr s 1078 puis 1076 etc Pour la racine ni me enti re d un nombre naturel il reste mettre en uvre un algorithme qui donne le r sultat exact en n utilisant que l arithm tique des nombres entiers Pour ceci on imite la r cursion ci dessus en rempla ant les nombres r els par les entiers Proposition 2 2 Soient y xo Z4 deux entiers positifs On d finie une suite r currente xx Z4 par Xr L Cr 1 xx ya n On a alors le comportement suivant Six lt y alors Xk41 gt Xk Six gt y alors xx41 lt xx ma s toujours 1 xx41 gt y On conclut qu une valeur initiale x v rifiant x gt y donne une suite initialement d croissante xo gt x gt ce gt Xk 1 gt Xk lt Xk t que xk y est la va
4. personne se comporter d une fa on plus adapt e la machine est souvent consid r e avec raison comme offensive Bjarne Stroustrup Le langage C Le but de ce paragraphe est de d velopper une fonction qui soit capable de lire et d valuer de telles expressions et qui soit raisonnablement commode utiliser Ceci n introduit aucun nouveau concept math matique il s agit surtout d un exercice de programmation 2 1 Notations Il y a plusieurs conventions possibles pour l criture d une expression alg brique on choisira ici le compromis d une notation qui soit la fois commode utiliser et facile programmer Notation infixe On est habitu l criture 10 00 949 qui correspond 107100 949 o le sym bole repr sente l op rateur de puissance C est ce que l on appelle la notation infixe parce que les op rateurs binaires figurent entre leurs op randes Notation pr fixe Pour les fonctions on utilise traditionnellement la notation pr fixe comme a ou f x y Ici la fonction pr c de les param tres Notation postfixe Dans certains domaines math matiques comme la th orie des groupes on pr f re la notation postfixe comme a ou ag C est aussi le cas pour la factorielle n o le param tre pr c de la fonction videmment toutes ces notations sont quivalentes entre elles dans le sens que l on peut traduire l une l autre au lieu d crire 107100 949 en
5. s la fiabilit et l efficacit la robustesse sera tr s appr ci e par l utilisateur R utilisabilit Comme la programmation soigneuse n cessite un investissement important il convient de r utiliser si possible le code source d j d velopp Bien s r on ne veut r utiliser que de code qui soit fiable clair et efficace Si ces qualit s sont satisfaites tout programmeur appr ciera la possibilit de s en servir Reconnaissons ce propos que nous avons d j profit des superbes biblioth ques STL et GMP Pour un d veloppement durable il est donc important de pr voir les r utilisations possibles dans d autres contextes Documentation Pour qu un logiciel soit utile dans un contexte plus large l utilisateur souhaitera une documentation ind pendante de l impl mentation Elle s adresse l utilisateur envisag que ce soit un programmeur qui r utilise certaines composantes ou un usager qui se sert du logiciel comme application toute faite Dans la pratique une utilisation intuitive et une documentation de qualit sont souvent cruciales Il va sans dire qu on devrait appliquer ces crit res tout logiciel non seulement dans ce cours Avouons cependant que ces exigences draconiennes sont rarement satisfaites soit par manque de temps soit tout simplement par n gligence En tenant compte des crit res ci dessus essayez de r examiner et d optimiser votre impl mentation Est elle
6. Numbers have neither substance nor meaning nor qualities They are nothing but marks and all that is in them we have put into them by the simple rule of straight succession Hermann Weyl 1885 1955 Mathematics and the Laws of Nature CHAPITRE III La biblioth que GMP Ce chapitre pr sente une solution industrielle du probl me des grands entiers en C la bi blioth que GMP Par rapport notre impl mentation faite maison elle se distingue seulement par son niveau d optimisation une journ e de programmation pour notre classe Naturel contre plusieurs ann es de d veloppement pour la biblioth que GMP En contrepartie nous sommes oblig s d accepter une telle biblioth que comme une bo te noire on apprendra facilement son interface mais non son fonctionnement int rieur Vous pouvez lire sa documentation en ligne si cela vous int resse Sommaire 1 Une impl mentation professionnelle des nombres entiers 1 1 Avant propos 1 2 Les entiers de la biblioth que GMP 1 3 Exemple pratique calcul de coefficients binomiaux 2 valuation d expressions alg briques 2 1 Notations 2 2 valuation en notation postfixe 1 Une impl mentation professionnelle des nombres entiers On discutera dans ce chapitre l utilisation d une classe Integer issue de la biblioth que GMP GNU Multiple Precision Library qui mod lise les grands entiers c est dire les nombres entiers sans limit
7. a recherche dichotomique o il faut trouver r s tels que r lt 4 y lt s Integer r Integer 1 lt lt log2 y n s r lt lt 1 d calages bit par bit Exercice P 3 2 Impl menter la recherche dichotomique algorithme TII 2 et la m thode de Newton H ron algorithme II 3 afin de calculer y Ici y sera de type Integer tandis que pour n le type int suffira Pourquoi Tester les deux fonctions sur des exemples de plus en plus grands Il sera int ressant de faire afficher les tapes interm diaires du calcul Les r sultats sont ils identiques comme il se doit Exercice P 3 3 Comment d terminer quelle m thode est plus efficace Comme la comparaison des co ts exacts s av re difficile on fait recours aux tests empiriques Calculer Var pour n 1 1000 Calculer Var pour n 1 1000 Vous pouvez mesurer le temps d ex cution avec le programme racine cc Formulez vos observations puis essayez d en tirer une conclusion ou une r gle heuristique pour choisir la meilleure m thode MAE 22 juin 2009 68 Projet IH Calcul de la racine ni me 4 Crit res de qualit d un logiciel En guise de conclusion et afin de clarifier les termes explicitons les qualit s que l on souhaiterait de tout logiciel Plus l application envisag e est importante plus les crit res suivants deviennent cruciaux Pensez par exemple un logiciel de pilotage d un avion ou la conduite d un m tro
8. ation de taille Contrairement au chapitre pr c dent nous ne tentons pas ici une impl mentation nous m mes mais nous nous servirons d une biblioth que toute faite 1 1 Avant propos Les biblioth ques les plus courantes offrent des solutions certains probl mes omnipr sents dans la programmation Il est tr s commode de s en servir pour ne pas r inventer la roue Ainsi utiliser une biblioth que de haute qualit offre des avantages importants Les fonctions sont soigneusement impl ment es et bien test es en particulier elles sont plus fiables et plus efficaces qu une solution ad hoc elles fournissent une fonctionnalit assez compl te et standardis e le code de votre application ainsi cr sera plus concis et plus lisible De mani re g n rale le partage de biblioth ques de qualit permet de mutualiser des impl mentations prouv es de minimiser des r impl mentations inutiles et de se concentrer sur l essentiel S Bref les biblioth ques c est bon mangez en Z En contrepartie avouons qu il existe aussi des inconv nients L utilisation d une biblioth que demande bien videmment comme investissement initial la lecture du mode d emploi plus ou moins complexe D o l int r t des biblioth ques bien construites et d utilisation intuitive Pour ce cours de programmation l autre inconv nient est d ordre p dagogique on utilise souvent une bibliot
9. conform ment notre sp cification Remarque 1 1 Pour utiliser le type Integer avec des constantes vous pouvez bien videmment utiliser les constantes litt rales du type int et les convertir en Integer Pour les constantes plus grandes ce n est plus jouable Essayez d expliquer pourquoi On fait alors appel aux cha nes de caract res Integer a 12345 ok constructeur partir d un int Integer b 98765432109876543210 ok constructeur partir d une cha ne a Integer 98765432109876543210 ok conversion explicite a 123456789012345678901234567891 ok conversion implicite 123456789012345678901234567890 constante litt rale trop longue a Dans le m me esprit o est l erreur logique dans le calcul suivant Comment le rectifier Integer f 1 2 3 4 xD x6 7 8 x9 x10 x11 12 x13 x14 x15 16 x17 x18 x19 20 Quels sont les principes de cette impl mentation Rappelons que le chapitre I partant du type int fut lourdement orient e machine il fallait d abord comprendre la r alisation du type int sur la machine et ensuite en se demandait dans quelles limites ce type pourrait bien servir pour nos calculs L approche orient e objet proc de dans le sens inverse on sp cifie d abord les propri t s et op rations n cessaires pour mod liser une classe d objets math matiques ou autres et ensuite on cherche les satisfaire par une impl mentation convenable C est cette deuxi me a
10. e commande Apr s compilation avec g postfixe cc lgmpxx o postfixe on peut ainsi crire gt postfixe 1 5 ce qui calcule 1 5 121 Il s agit donc d une calculette en miniature Ajouter d autres fonctions qui vous semblent int ressantes pgcd ppem factorisation test de primalit etc MAE 22 juin 2009 I only took the regular course What was that enquired Alice Reeling and Writhing of course to begin with the Mock Turtle replied and then the different branches of Arithmetic Ambition Distraction Uglification and Derision Lewis Carroll Alice s Adventures in Wonderland PROJET II Calcul de la racine ri me Objectifs gt tudier deux algorithmes importants la recherche dichotomique et la m thode de Newton gt D velopper une preuve de correction pour un algorithme non trivial Ce projet vous propose d impl menter deux m thodes afin de calculer la racine ni me enti re a pour des nombres naturels a assez grands Pour cela nous n aurons besoin que des op rations l mentaires impl ment es au pr alable nous nous servirons ici de la biblioth que GMP En principe notre impl mentation du type Naturel marcherait aussi mais elle serait plus lente Pour un probl me difficile on est d j content de trouver une solution S il peut tre r solu par plusieurs m thodes on a tout int r t en choisir la plus efficace Dans ce projet o
11. ent binomial cherch leur temps d ex cution peut diff rer Pour les petits nombres n et k c est binomial2 qui gagne tandis que pour les grands nombres la fonction binomial3 semble la plus efficace Bien videmment on ne peut comparer que les m thodes que l on conna t Question naturelle existe t il des m thodes encore meilleures ou des astuces d optimisation Strat gie g n rale plus on sait sur la fonction calculer plus de m thodes se pr sentent En voici un exemple Exercice P 1 7 V rifier d abord que votre fonction binomial3 calcule ais ment 19090 mais elle bloque sur onr Comment expliquer ce comportement En quoi la sym trie c A 2 peut elle tre utilis e pour optimiser le calcul L impl menter en une fonction binomial4 V rifier qu ainsi les calculs interm diaires n exc dent jamais la valeur AU 2 valuation d expressions alg briques Jusqu ici on ne peut entrer des entiers qu en num ration d cimale Or entrer un grand entier comme 10100 949 par son criture d cimale de 101 chiffres n est pas tr s commode Il sera plus naturel justement d utiliser une expression semblable 10100 949 La lecture des donn es en entr e constitue souvent la partie la plus n glig e d un pro gramme Ce dernier devant communiquer avec une personne il doit faire face aux fantaisies aux conventions et aux erreurs apparemment al atoires de celle ci Toute tentative pour forcer la
12. es vecteurs vector que nous avons regard e au chapitre I La STL offre aussi d autres structures de donn es qui sont fr quemment utilis es et tr s utiles suivant l application envisag e les listes List les listes bidirectionnelles deque les piles stack les files queue les files de priorit priority queue les ensembles set et d autres encore Pour en savoir plus vous pouvez consultez la page www sgi com st1 Il existe galement d excel lentes introductions la STL consultez votre biblioth que universitaire La biblioth que GMP Le GNU Multiple Precision Project a d velopp la biblioth que GMP pour des calculs efficaces en pr cision arbitraire en C C Elle offre des classes pour les nombres entiers et rationnels et les nombres virgule flottante en pr cision arbitraire Vous pouvez consultez le site of ficiel www swox com gmp o vous trouverez une ample documentation La biblioth que GMP se trouve galement sur le site de GNU www gnu org manual gmp Avec votre installation sous GNU Linux vous pouvez galement taper info gmp C pour lire la documentation locale en ligne Que faut il pour mod liser les entiers En tenant compte de nos exp riences pr c dentes pr cisons nos exigences On souhaite disposer d un type Integer qui mod lise les entiers dans le sens suivant Repr sentation et entr e sortie Tout d abord on veut que tout nombre entier puisse tre repr sent com
13. est significatif La repr sentation interne n est pas en base 10 mais en base 2 plus pr cis ment en base 2 pour profiter pleinement de la structure du microprocesseur La conversion en base 10 se fait uniquement l entr e sortie consid r e comme peu fr quente et n gligeable devant les calculs M me pour la GMP le principe de base reste incontournable plus les nombres sont grands plus ils occupent de m moire et plus les op rations s effectuent lentement Mis part ce constat la repr sentation interne ne nous regardera pas dans la suite l essentiel est que mpz_class fonctionne suivant la sp cification ci dessus Tests empiriques Les r sultats sont assez impressionnants vous pouvez regardez le programme gmp chrono cc pour comparer la performance de la classe mpz_class et notre candidat Naturel Re marquez ce propos que notre addition semble comp titive un facteur constant pr s mais la complexit quadratique de la multiplication scolaire se r v le catastrophique pour les nombres de plus en plus grands La GMP par contre utilise les meilleurs algorithmes connus et arrive ainsi une complexit quasi lin aire 1 3 Exemple pratique calcul de coefficients binomiaux Apr s les op rations de base regardons une fonction un peu moins l mentaire le coefficient binomial Zx Z Z d fini par 5 y is TANI S0 lt k lt n et Qi 0 sinon M me pour de tels calculs tr s simples
14. fiable Le v rifier sur beaucoup d exemples triviaux et non triviaux Enfin peut on prouver sa correction Le code source est il clair et bien comment Essayez de lire et v rifier la solution de quel qu un d autre Le logiciel s ex cute t il rapidement Majorer si possible la complexit th orique puis ef fectuez de nombreux tests empiriques Est il robuste dans des circonstances impr vues Soyez m chant et essayez de provoquer une erreur grave puis invitez quelqu un d autre le faire R agit il toujours de mani re aimable envers l utilisateur Le tester sur un non sp cialiste L usage dans d autres programmes sera t il facile revoir dans des applications ult rieures plus tard pendant ce semestre MAE 22 juin 2009
15. h que comme une bo te noire c est dire on apprend sa fonctionnalit externe en par ticulier l interface mais on n apprend pas comment elle est construite on particulier on ignore souvent la structure des donn es et les algorithmes utilis s Afin de rem dier ces d fauts dans le cas des grands entiers nous le chapitre IT discute les l ments d une impl mentation assez compl te dans notre exemple Naturel On ferra pareil dans des chapitres plus avanc s permutations au chap VI quelques anneaux au chap XII puis des polyn mes au chap XIII par exemple Bien qu il existe de biblioth ques ad quates on peut ainsi apprendre en d tail le d veloppement math matique souvent int ressant en lui m me Pour une application non p dagogique on utilisera plut t une biblioth que professionnelle si possible 59 60 Chapitre III La biblioth que GMP La biblioth que STL Le C vient d j avec une biblioth que standard elle fait partie du C et n est donc souvent pas remarqu e comme biblioth que part enti re La biblioth que la plus connue est sans doute la STL Elle fut d velopp e par Hewlett Packard Company partir de 1994 puis par Silicon Graphics Computer Systems partir de 1996 Elle fut standardis e et accept e comme partie int grante du langage C en 1998 tout syst me conforme ce standard fournit donc une version de la STL La STL offre une classe g n rique pour mod liser l
16. il y a en g n ral plusieurs m thodes possibles Elles sont bas es sur les m mes op rations l mentaires elles aboutissent toutes au r sultat cherch mais elles passent par des calculs interm diaires bien diff rents Tr s souvent nous devons choisir la m thode la plus efficace parmi celles qui sont notre disposition Dans notre exemple il y a au moins quatre m thodes diff rentes qui viennent l esprit Exercice P 1 2 La d finition o TE se traduit litt ralement en une m thode de calcul L impl menter en deux fonctions factorielle et binomial1 Quel mode de passage des param tres convient le mieux Combien d op rations arithm tiques effectuent elles multiplications et divisions confondues pour calculer C Quel est le plus grand entier qui apparaisse dans les calculs interm diaires Est ce une m thode efficace pour calculer 77 Exercice P 1 3 La fraction simplifi e sugg re une deuxi me m thode on calcule d abord le num rateur puis on divise par le d nominateur Expliquer bri vement en quoi cette m thode est avantageuse puis l impl menter en une fonction binomial2 n n _ n n 1 n k 1 n _ n n k 1 si Exercice P 1 4 La formule gt k Peut tre lue comme gt a avec condition initiale o 1 Ceci donne lieu une troisi me m thode de calcul une boucle o multiplications et divi sions sont effectu es en alternance Expliquer bri vement en
17. leur cherch e MAE 22 juin 2009 83 Impl mentation et tests empiriques 67 Exercice 2 3 crire un programme qui affiche la suite r currente d finie dans la proposition afin de v rifier empiriquement ces affirmations et pour motiver l algorithme II 3 ci dessous Montrer la correction de cet algorithme en admettant la proposition tablir d abord la terminaison puis la correction du r sultat en suivant les commentaires dans la description de la m thode Algorithme III 3 Racine ni me enti re d apr s Newton H ron Entr e deux entiers y gt 1 etn gt 2 Sortie Tunique entier r gt 1 v rifiant r lt y lt r 1 choisir une valeur initiale x tel que x gt y I voir la remarque 3 1 plus bas r p ter TX x 4 n 1 x J variante enti re de la r cursion de Newton H ron jusqu x gt r condition d arr t motiv e ci dessus retourner r Exercice M 2 4 Si vous tes courageux vous pouvez essayez de prouver la proposition Indication Dans la version r elle on it re la fonction f R R donn e par f x 1 n 1 x y Elle est strictement croissante sur 4 y elle v rifie y y lt f x lt x pour tout x gt 4 y ainsi que f 4 9 4 y ceci est donc le seul point fixe et il est attractif Le d tailler Dans la version enti re nous it rons g Z Z d finie par g x n 1 x y x 7 n V rifier que g x f x pour tout x Z Remarque
18. mani re naturelle de sorte que a b quivaille a a b etc De m me pour les op rateurs et pour les quels on exige que a quivaille a a 1 etc L int r t pourra tre une meilleure lisibilit et ventuellement une plus grande performance Cela d pend du niveau d optimisation Ces op rations l mentaires d crivent alors la base requise pour travailler avec des entiers sur ordi nateur D autres fonctions seraient galement souhaitables comme factorielle binomial racine pgcd ppcm est premier factoriser etc On en d veloppera quelques unes dans la suite mais tout d veloppement ult rieure sera bas sur les op rations l mentaires ci dessus 1 2 Les entiers de la biblioth que GMP Comme on a vu au chapitre I impl menter l arithm tique des nombres entiers est faisable mais tr s laborieux Heureusement il existe d j de telles impl mentations soigneusement test es et optimis es Nous utiliserons par la suite la classe mpz_class de la biblioth que GMP GNU Multiple Precision Library Elle satisfait toutes nos exigences ci dessus et de plus les calculs s effectuent tr s rapidement Son utilisation est assez intuitive MAE 22 juin 2009 81 Une impl mentation professionnelle des nombres entiers 61 Programme II 1 Exemple d utilisation de la classe Integer gmp exemple cc include lt iostream gt d clarer l entr e sortie standard using namespace std acc s direct
19. me une valeur de type Integer Les op rateurs d entr e gt gt et de sortie lt lt permettent de lire et d crire ces valeurs ils traduisent alors entre la repr sentation externe l criture d cimale et la repr sentation interne que nous ignorons Op rateurs d affectation On voudra utiliser l op rateur d affectation avec la syntaxe et la s mantique usuelle il prend deux arguments une variable de type Integer gauche et une valeur de type Integer droite puis il affecte la valeur la variable Conversion de type La conversion devra permettre d affecter une valeur du type int une variable var de type Integer On pourra donc crire var Integer 1 pour une conversion explicite ou bien var 1 pour une conversion implicite Op rateurs de comparaison On voudra utiliser les op rateurs de comparaison ainsi que lt lt gt gt avec la syntaxe usuelle savoir ils prennent deux arguments de type Integer et renvoient un r sultat de type bool qui correspond la comparaison dans Z Op rateurs arithm tiques On voudra utiliser les op rateurs arithm tiques 4 avec la syntaxe usuelle savoir ils prennent deux arguments de type Integer et renvoient un r sultat de type Integer Quant leur s mantique on exige que le r sultat corresponde au r sultat de l op ration respective sur Z Op rateurs mixtes Les op rateurs x devront s utiliser d une
20. n regardera la situation suivante Lemme 0 1 Soit f N N une application v rifiant 0 f 0 lt f 1 lt f 2 lt avec sup f Alors pour tout y N il existe un unique x N de sorte que f x lt y lt f x 1 En appliquant ce lemme f x x on voit que le nombre cherch est x RE C est bon savoir qu il existe et qu il est unique mais comment le trouver efficacement Sommaire Recherche dichotomique La m thode de Newton H ron Impl mentation et tests empiriques Crit res de qualit d un logiciel BE D 1 Recherche dichotomique Exercice 1 1 Commen ons par la solution la plus vidente Montrer que l algorithme IIL 1 est correct Pourquoi s arr te t il Pourquoi renvoie t il la valeur cherch e V rifier qu il n cessite x 1 valuations de la fonction f Algorithme IIL1 Encadrement f x lt y lt f x 1 par une recherche lin aire Entr e une fonction croissante f N N comme ci dessus et un nombre naturel y N Sortie Tunique x N tel que f x lt y lt f x 1 r 0 1 1 On commence par r 0 donc f r lt y tant que f r 1 lt y faire r r 1 On assure f r lt y apr s chaque it ration retourner r On sait finalement f r lt y lt f r 1 donc r x Le co t lin aire de l algorithme II 1 est prohibitif pour des exemples r alistes o x peut tre tr s grand l instar de la recherche dichotomique discu
21. notation infixe on peut crire 10 100 949 en notation pr fixe ou encore 10 100 949 en notation postfixe Question 2 1 Pourquoi la notation infixe n cessite t elle des parenth ses alors que les notations pr fixe et postfixe peuvent s en passer Expliquer comment transformer les diff rentes critures lin aires en un arbre et r ciproquement comment transformer un arbre en chacune des critures lin aires On ne poursuivra pas cette approche ici mais elle sera indispensable pour correctement stocker analyser valuer des expressions d une mani re plus approfondie 63 MAE 22 juin 2009 64 Chapitre III La biblioth que GMP Dans la suite on d veloppera une fonction eval postfix qui value une expression en notation postfixe On obtient ainsi une sorte de calculette quoique modeste qui permet de commod ment calculer avec des grands entiers On mettra les fonctions de calcul dans le fichier integer cc et les fonctions d entr e sortie dans le fichier eval postfixe cc amp Au del de son but court terme ce projet s inscrit dans un d veloppement durable tout le long ce semestre nous commen ons ici le travail sur le fichier integer cc qui augmentera fur et mesure si vous le maintenez comme souhait bien s r Chaque fois que vous programmez une fonction d int r t g n ral pour la classe Integer elle devrait tre plac e dans integer cc Id alement vous inclurez ce fichier dans vos
22. ns aussi efficace que son concurrent dichotomique pour x 2 et x 4 il est m me l g rement sup rieur Mais d j partir de x 6 la recherche dichotomique s amortit lin aire 1 2 3 4 5 7 dichotomique 1 2 4 4 6 6 Pour x grand la recherche dichotomique est nettement plus efficace que la recherche lin aire Pour x 106 par exemple elle ne n cessite que 40 valuations alors que l algorithme lin aire en n cessite un million Pour x 10 c est 60 contre un milliard Exercice 1 4 On peut appliquer les m thodes pr c dentes la fonction f N N f x xb et une valeur a N afin de trouver l unique q N v rifiant gb lt a lt q 1 b On obtient ainsi le quotient q de la division euclidienne de a par b avec reste r a qb D tailler pourquoi la recherche lin aire revient la m thode des soustractions it r es alors que la recherche dichotomique correspond la division scolaire en num ration binaire Voir chapitre II 81 7 2 La m thode de Newton H ron La recherche dichotomique s applique toute fonction croissante f N N Peut on faire mieux dans le cas sp cifique o la fonction est donn e par f x x Pour ceci on s inspire du r sultat suivant que vous reconnaissez de votre cours d analyse Th or me 2 1 Calcul de la racine ni me d apr s Newton H ron Soit n gt 2 un entier et a gt 0 un nombre r el Pour toute valeur initiale u gt 0
23. pproche que nous poursuivons ici et notre impl mentation du type Naturel en tait un premier exemple En gros la classe mpz_class est impl ment e comme notre exemple Naturel en particulier elle utilise un tableau de taille adaptable pour stocker les chiffres d un nombre entier La principale diff rence entre mpz class et notre candidat Naturel est la performance En effet les programmeurs de la bi blioth que GMP ont fait un norme effort d optimisation Au niveau algorithmique la biblioth que GMP impl mente les meilleurs algorithmes connus ce jour De nombreuses variantes ont t test es et optimis es puis les meilleures ont t retenues MAE 22 juin 2009 62 Chapitre III La biblioth que GMP Sile choix de l algorithme le mieux adapt d pend des donn es ce choix se fait au moment de T ex cution typiquement en fonction de la taille des donn es Pour la multiplication notamment on choisira entre scolaire et Karatsuba puis d autres encore que nous n avons pas pr sent s ici Les fonctions les plus fr quentes comme l addition ou la soustraction ou d autres routines de base sont cod es en langage machine et non en C C afin d utiliser le plus efficacement les instructions fournies par le microprocesseur Cette approche est tr s laborieuse car on doit r impl menter ces fonctions sur chaque type de processeur Ceci n est justifi que dans les rares cas ou le gain esp r
24. programmes ult rieurs pour avoir toute la facilit d une mini biblioth que bien crite et bien test e si vous suivez les r gles de l art 2 2 valuation en notation postfixe Pr cisons d abord ce que nous voulons faire On souhaite dis poser d une fonction d entr e avec au moins les possibilit s suivantes On peut entrer un entier en num ration d cimale Exemple l entr e 123 produit la valeur 123 On peut entrer toute une expression d limit e de parenth ses et Exemple l entr e 5 donne la valeur 120 On peut empiler plusieurs entiers s par s d espaces La commande del efface le dernier entier il le d pile Le passage la ligne la touche return fait afficher la pile Exemple l entr e 123 456 789 del lt return gt affiche 123 456 de sorte que l on puisse contr ler le r sultat interm diaire et continuer l entr e On peut entrer le nom d une fonction ou un op rateur arithm tique comme en notation postfixe Une telle fonction d pile ses arguments puis empile son r sultat Exemple l entr e 123 456 lt return gt affiche 579 D autres fonctions seront faciles ajouter fur et mesure Exemple l entr e 100 20 binomial calculera le coefficient binomial 2 Exercice P 2 2 Vous trouvez le d but d une impl mentation dans le fichier eval postfixe cc Lire le code source le compiler pui
25. quoi cette m thode pourrait tre avantageuse puis l impl menter en une fonction binomial3 Exercice P 1 5 La propri t Ci H j donne lieu une r currence qui vite toute multiplication en se basant sur les valeurs initiales o C 1 L impl menter en une fonction r cursive binomial0 Comme avant veillez que 5 0pourk lt 0 ouk gt n Exercice P 1 6 crire un programme qui lit au clavier deux entiers n et k puis affiche les r sultats des fonctions binomial3 binomial2 binomiali binomialO dans cet ordre ci Tester soigneusement les fonctions pour quelques petites valeurs puis pour des exemples plus grandes Les r sultats co ncident ils comme il se doit Si oui on veut alors comparer leur performance MAE 22 juin 2009 2 valuation d expressions alg briques 1 Calculer 4 y o g EH Qu observez vous Comment expliquer le ralentissement de la fonc tion binomial0 Vous pouvez arr ter le programme avec CTRL c 2 En excluant binomial0O calculer e EA kr ue Qu observez vous Comment expliquer le ralentissement de la fonction binomial1 3 En utilisant seulement binomial3 et binomial2 calculer 000 Errai oooi Au d but il n y a pas de diff rence significative puis binomial2 devient plus lente que binomial3 Comment expliquer cette diff rence Justifiez ainsi la conclusion suivante bien que les quatre fonctions calculent toutes le coeffici
26. s le tester Regarder en particulier l usage de la pile Compl ter l impl mentation en incluant les op rations arithm tiques l addition la soustraction la multiplication la division euclidienne le reste de la division En chaque instance on r cup re les deux op randes de la pile puis on y remet le r sultat du calcul Veillez l ordre des op randes ainsi qu d ventuelles erreurs par exemple la division par z ro Exercice P 2 3 crire une fonction binomial dans integer cc issue de vos exp riences en 81 3 et la rendre disponible dans eval_postfixe cc via la commande binomial Exercice P 2 4 crire une fonction Integer puissance Integer base Integer exp dans integer cc et la rendre disponible dans eval postfixe cc via l op rateur Ajouter Integer puissance Integer base Integer exp const Integer amp mod qui calcule la puissance modulaire c est dire le reste modulo mod Discuter le mode de passage des param tres La rendre disponible via l op rateur ternaire Remarque Cette approche vous semblera peut tre redondante Essayons donc de le justifier En quoi la puissance modulaire peut elle tre plus efficace que la puissance ordinaire suivie d une r duction modulaire Si possible optimisez vos fonctions puis tester leur performance On y reviendra dans le projet VIII Exercice P 2 5 Le programme postfixe cc permet d valuer une expression pass e par la ligne d
27. sans conducteur Fiabilit Un programme est fiable s il fait toujours exactement ce pour quoi il est fait en parfaite conformit avec ses sp cifications Cette qualit est indispensable Pour une application impor tante on n acceptera pas un logiciel qui marche 9 fois sur 10 Clart Dans le souci de fiabilit on doit insister sur un code source clair et net Un programme embrouill ou incompr hensible est inutilisable d abord on n arrive pas se convaincre de sa fiabilit puis il sera difficile voire impossible de le maintenir ou modifier Que vaut un pro gramme qui semble marcher mais on ne comprend pas pourquoi Efficacit Un programme efficace s ex cute rapidement et utilise conomiquement la m moire et toute autre ressource de l ordinateur videmment cette qualit est assez importante dans la pratique que vaut une r ponse correcte si elle arrive trop tard L efficacit ne doit tre recherch e qu apr s satisfaction de deux exigences pr c dentes qui sont primordiales que vaut une r ponse rapide si elle est fausse Robustesse Un programme fiable travaille correctement dans les situations pr vues par sa sp cification Il est robuste si de plus il r agit de mani re raisonnable dans des situations impr vues Par exemple si l utilisateur entre des donn es hors domaine le logiciel au lieu de d railler les refuse poliment et propose une mani re de rectifier la situation Apr
28. t e au chapitre V l algorithme suivant met en uvre une variante astucieuse qui am liore consid rablement la performance Exercice 1 2 Prouver que l algorithme II 2 est correct montrer d abord la terminaison puis la correction en suivant les commentaires dans la description de la m thode Exercice 1 3 V rifier pour x 0 que l algorithme II 2 n effectue qu une seule valuation de f Pour x gt 1 d terminer le nombre exact d valuations de f effectu es dans la premi re puis la seconde boucle Indication Vous pouvez commencer par les cas x 1 8 et ainsi v rifier le tableau suivant 65 66 Projet IHI Calcul de la racine ni me Algorithme IIL2 Encadrement f x lt y lt f x 1 par une recherche dichotomique Entr e une fonction croissante f N N comme ci dessus et un nombre naturel y N Sortie Tunique x N tel que f x lt y lt f x 1 r0 s1 On commence par r 0 donc f r lt y tant que f s lt y faire rs s 2s On assure ainsi que f r lt y lt f s tant que s r gt 1 faire Tant que l intervalle n est pas r duit un point m lt 1 1 on divise l intervalle au milieu et si f m lt y alors r m sinon sm II on assure nouveau que f r lt y lt f s fin tant que I finalement s r 1 et f r lt y lt f s retourner r On conclut que r x Conclusion Pour des valeurs minuscules x lt 5 l algorithme lin aire est au moi
Download Pdf Manuals
Related Search