Numeration positionnelle et conversion de base

De
Publié par

CHAPITRE IV Numeration positionnelle et conversion de base Algorithms + Data Structures = Programs Niklaus Wirth Objectifs ? Reviser la numeration en base b≥ 2 et l'algorithme de changement de base. ? Implementer une application surprenante : le calcul de e et de pi a une precision arbitraire. ? Preparer le terrain pour le calcul arrondi (chap. XV) et le calcul arrondi fiable (chap. XVI) Ce chapitre explique d'abord comment convertir la representation d'un nombre de la base 10 a la base 2, puis comment convertir entre deux bases quelconques. L'idee est simple, mais les applications sont etonnantes : avec tres peu d'analyse, cette methode permet de calculer quelques milliers de decimales de e = 2,71828 . . . Le projet traitera ensuite le calcul de pi = 3,14159 . . . Sommaire 1. Numeration positionnelle. 1.1. Un premier exemple : la conversion de la base 10 a la base 2. 1.2. Representation en base b. 1.3. Conversion de base. 2. Representation factorielle. 2.1. Calcul de e a 10000 decimales. 3. Quelques conseils pour une bonne programmation. 1. Numeration positionnelle 1.1. Un premier exemple : la conversion de la base 10 a la base 2. Rappelons d'abord la division euclidienne des entiers : pour tout a,b ? Z avec b 6= 0 il existe une unique paire (q,r) ? Z?Z telle que a = bq+ r et 0≤ r < |b|.

  • representation factorielle

  • representations au debut de la jeme iteration

  • base factorielle

  • application ?·?


Publié le : lundi 18 juin 2012
Lecture(s) : 65
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 12
Voir plus Voir moins
CHAPITRE IV
Algorithms + Data Structures = Programs Niklaus Wirth
Num´erationpositionnelleetconversiondebase
Objectifs Reviser la nume´ration en base b 2 et l'algorithme de changement de base. ´ Imple´menter une application surprenante : le calcul de e et de ϑ a une pre´cision arbitraire. Pr´eparerleterrainpourlecalcularrondi(chap.XV)etlecalcularrondiable(chap.XVI) Ce chapitre explique d'abord comment convertir la repre´se ntation d'un nombre de la base 10 a la base2,puiscommentconvertirentredeuxbasesquelconques.L'id´eeestsimple,maislesapplicationssont ´etonnantes:avectrespeud'analyse,cettem´ethodepermetdecalculerquelquesmilliersded´ecimalesde e = 2 71828    Le projet traitera ensuite le calcul de ϑ = 3 14159    Sommaire 1.Num´erationpositionnelle. 1.1. Un premier exemple : la conversion de la base 10 a la base2. 1.2.Repr´esentationenbase b . 1.3. Conversion de base. 2. Repre´sentation factorielle. 2.1. Calcul de e a10000d´ecimales. 3. Quelques conseils pour une bonne programmation. 1. Nume´ration positionnelle 1.1. Un premier exemple : la conversion de la base 10 alabase 2 . Rappelons d'abord la division euclidienne des entiers : pour tout a b Z avec b 6 = 0 il existe une unique paire ( q r ) Z × Z telle que a = bq + r et 0 r < | b | . Dans la suite on utilisera la notation a div b : = q pour le quotient, et a mod b : = r pour le reste d'une telle division euclidienne. Exemple 1.1. Commenttrouverlarepr´esentationbinairedunombre11 6875 dec ? C'est facile pour la partie entiere 1 d 1 ec = 1 2 3 + 0 2 2 + 1 2 1 + 1 2 0 = 1011 bin .Ced´eveloppements'obtientparunedivision euclidienneit´er´eeselonlesche´masuivant: 11 mod 2 = 1 et 11 div 2 = 5 5 mod 2 = 1 et 5 div 2 = 2 2 mod 2 = 0 et 2 div 2 = 1 1 mod 2 = 1 et 1 div 2 = 0 Pareil pour la partie fractionnaire 0 6875 dec = 1 2 1 + 0 2 2 + 1 2 3 + 1 2 4 = 0 1011 bin . Ici on multiplie par 2 au lieu de diviser, on extrait la partie entiere et continue avec la partie fractionnaire : 0 6875 2 = 1 3750 0 3750 2 = 0 7500 0 7500 2 = 1 5000 0 5000 2 = 1 0000 Exercice/M 1.2. V´erierlaconversionde31 9 dec en binaire donne´e en chapitre I, page 12. Cette fois-ci onobtientunerepre´sentationbinairequiestp´eriodique.(Pourquoi?) 69
70
ChapitreIV—Num´erationpositionnelleetconversiondebase
1.2.Repr´esentationenbase b . Lesbases10et2n'ontriendeparticulier,apartleurusagefr´equent, et nous regarderons dans la suite une base b quelconque, avec b N , b 2. Explicitons d'abord les deux algorithmessous-jacentsauxexemplespre´c´edents. Algorithme IV.1 Repre´sentation d'un nombre naturel a 0 en base b Entre´e: Un nombre naturel x N et un entier b 2 Sortie: L'unique suite ( x n      x 0 ) dans [ 0 b [ telle que x = å 0 k = n x k b k et x n 6 = 0 Initialiser n ← − 1 tant que x > 0 faire n n + 1, x n x mod b , x x div b retourner ( x n      x 0 )
Exercice/M 1.3. V´erierquel'algorithmeIV.1estcorrect.Plusexplicitement:´etantdonne´s x N et b 2, pourquoi produit-il une suite ( x n      x 0 ) dans [ 0 b [ v´eriant x = å 0 k = n x k b k ? Pourquoi cette suite est-elle unique ? Ceci justie d'appeler x k le k ieme chiffre de x dans le de´veloppement en base b . Algorithme IV.2 Repre´sentation d'un nombre re´el r 0 en base b Entr´ee: Unnombrer´eel x 0 et deux entiers b 2, p 0 Sortie: L'unique suite ( x n      x 0      x p ) dans [ 0 b [ avec x n 6 = 0 v´eriant x = å kp = n x k b k + Α p avec un reste 0 Α p < b p Trouverd'abordlarepr´esentation ( x n      x 0 ) de la partie entiere x . pour k de 1 a p faire x x − ⌊ x , x bx , x k ← ⌊ x retourner ( x n      x 0      x p )
Exercice/M 1.4. Ve´rier que l'algorithme IV.2 est correct : e´tant donne´s x 0 et b 2 et p 0, pourquoi produit-il une suite ( x n      x 0      x p ) dans [ 0 b [ ? Pourquoi a-t-on x = å kp = n x k b k + Α p avec un reste 0 Α p < b p ? Pourquoi cette suite est-elle unique ? Exercice/M 1.5. Montrer que l'algorithme IV.2 est stable danslesenssuivant:augmenterlapr´ecision de p a p + 1 ajoute unchiffresanschangerleschiffrespre´c´edents.Onpeutainsi,pour p υ , obtenir un d´eveloppementinni en base b .D´enircequec'estetexpliquerpourquoiiln'yaplusunicit´e.Quels nombresadmettentplusd'und´eveloppementinni?L'algorithmeci-dessusn'enproduitqu'un,lequel? Remarque 1.6. Dansl'algorithmeIV.2nousignoronscommentestdonne´lenombrer´eel x , c'est-a-dire commentilestrepre´sent´econcretementsurmachine.Laseulechosequ'ilfautsavoirestd'effectuerdeux ope´rations´el´ementaires:multiplicationpar b , puis se´paration des parties entiere et fractionnaire. Bien qu'e´le´mentaires,cesop´erationsnesontpastoujoursfaciles:pourvousenconvaincre,essayezd'appliquer l'algorithme IV.2 a 7 ou a ln 2 ou  R a 01 e x 2 2 dx outoutautrenombrer´eelquivousviental'esprit. Par conse´quent, dans toutes les applications suivantes, nous supposons que x est lui-mˆeme donne dans ´ une nume´ration positionnelle, c'est-a-dire par une somme x = å x k v k oules x k sont les « chiffres » ,ponde´r´es par des valeurs positionnelles v k , choisies convenablement selon le contexte. Ce cadre est sufsamment g´ene´ralpourˆetreinteressant,etenmˆemetempsilseprˆetebienaucalcul. ´ 1.3. Conversion de base. Ceparagrapheexpliquecommentconvertirund´eveloppementenbase b en une autre base c . La partie entiere se traite comme ci-dessus et ne pose aucun probleme. Nous nous concentrerons donc sur la partie fractionnaire uniquement. Autrement dit, nous allons imple´menter des calculs avec des nombres avirgule xe , c'est-a-dire avec des de´veloppements de la forme x 0 x 1 x 2 x 3    x m en base b Unetellerepr´esentationn'estriend'autrequeladonne´ed'unesuitedechiffres x 0 x 1      x m . An d'avoir une notation commode nous introduisons l'applicat ion hi b : Z m + 1 Q qui associe a chaque suite nie x = ( x 0 x 1      x m ) le nombre rationnel h x i b : = å km = 0 x k b k ainsirepr´esent´e.C'estuneapplication Z -lin´aire, dont l'image consiste de tous les nombres ratio nnels de la forme z b m avec z Z . e MAE 22 juin 2009
§ 1—Nume´rationpositionnelle
71
D´enition1.7. On dit que q Q est repre´sent´e par x Z m + 1 en base b si h x i b = q .Unetellerepr´esentation est appele´e normale (par rapport a b ) si 0 x k < b pour tout k = 1 2      m . Pour simplier nous n'exigeons pas que 0 x 0 < b ; l'entier x 0 joue le r ˆole de la partie entiere et peut prendre n'importe quelle valeur dans Z .Cesontleschiffresapreslavirgulequinousinte´ressetnici. + Danstoutcechapitrenousallonsutilisercesd´eveloppementsdits a virgule x . e -Notons d'abord que la normalisation est toujours possible : si par exemple x m ne ve´rie pas 0 x m < b , on effectue une division euclidienne x m = qb + x m avec quotient q = x m div b et un reste x m = x m mod b v´eriant0 x m < b . On remplace alors x m par x m et ajoute la retenue q a x m 1 .Enite´rantceproce´d´epour k = m 1      1onobtientler´esultatsuivant: Proposition 1.8 (normalisation) . Toute representation x Z m + 1 peuteˆtrenormalis´eeparrapportalabase ´ b, c'est- a-dire qu'il existe une repr e´sentation normale x ¯ Z m + 1 telle que h x ¯ i b = h x i b . L'algorithme IV.3 ci-dessous construit une telle repre´sentation normale apartir de x . Algorithme IV.3 Normalisation par rapport a une base b Entre´e: Un vecteur x = ( x 0 x 1      x m ) Z m + 1 repr´esentant x ¯ = h x i b en base b 2 ( x 0 x 1      x m ) Z m + 1 epr´esentant¯ Sortie: Le vecteur normal x = r x en base b 2 pour k de m a 1 faire // l'indice k parcourt de droite a gauche x k 1 x k 1 + ( x k div b ) // ajouter la retenue a x k 1 x k x k mod b //r´eduire x k modulo b n pour retourner ( x 0 x 1      x m ) Nous allons prouver la proposition 1.8 en montrant que l'algorithme est correct : Lemme 1.9 (correction) . L'algorithme IV.3 est correct. Plus explicitement, la valeur repre´sente´e h x i b ne changepasdurantl'ex´ecutiondel'algorithme,etlevecteurrenvoy´exestnormalise´. ´ ´ oujours apres m ite´rations). Ve´rions d' bord D EMONSTRATION . Evidemment l'algorithme se termine (t a l'invariance. Par de´nition on a h x i b = å km = 0 x k b k . La division euclidienne donne x k = b q + x k tel que 0 x k < b et q 0. Si l'on pose x k 1 = x k 1 + q on voit aise´ment que h x i b = h x i b . (Le de´tailler.) Montronsparr´ecurrencequelere´sultatestnormalis´e.Supposonsqu'avantl'ite´ration k les chiffres x k + 1      x m sont normalise´, c'est-a-dire que 0 x j < b pour tout j = k + 1      m . Ces chiffres-la ne changentpaslorsdel'it´eration k , et apres le chiffre x k v´erie0 x k < b par construction. C'esttoujoursuneexcellenteid´eedemajorerlescalculsinterm´ediaires:explosent-ilsourestent-ils borne´s ? Plus concretement, on peut se demander si les petits entiers (de type int ) sufront pour imple´menter l'algorithme. Le lemme suivant en donne la re´ ponse : Lemme 1.10 (majoration) . Dans l'algorithme IV.3, si tous les x k satisfont initialement 0 x k < cb, avec une constante c N ,alorslaretenuened´epassejamais 2 c. D ´ EMONSTRATION . Pour k > m la retenue est nulle, il n'y donc rien a montrer. Supposons que la retenueajout´eea x k ae´t´einfe´rieurea2 c . Alors 0 x k < c ( b + 2 ) . La division euclidienne x k = bq + x k donne donc 0 x k < b et 0 q < 2 c car b 2. On conclut par re´currence Lelemmesuivantconrmequetronquerunerepr´esentationenbase b donne la partie entiere. Lemme 1.11 (unicite´) . Si x Z m + 1 est normale par rapport ala base b, alors x 0 ≤ h x i b < x 0 + 1 . Si x y Z m + 1 sont normales par rapport ala base b, alors h x i b = h y i b entraˆnex = y. D ´ MONSTRATION .´Evidemment h x i b = å km = 0 x k b k x 0 car tous les termes de la somme å km = 1 x k b k E sont positifs ou nuls. D'autre part å km = 1 x k b k å km = 1 ( b 1 ) b k = 1 b m < 1. Supposons maintenant que x y Z m + 1 sont normales et que h x i b = h y i b . Tout d'abord on constate que ⌊h x i b = x 0 et ⌊h y i b = y 0 , ce qui implique x 0 = y 0 . Ensuite b h x i b = bx 0 + x 1 et b h y i b = by 0 + y 1 , ce qui implique x 1 = y 1 .Onconclutainsiparr´ecurrence. MAE 22 juin 2009
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.