Numeration positionnelle et conversion de base

Niklaus Wirth

Description

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 ?·?

Sujets

• multiplication
• exercice
• mathe
• cours
• exercices

Informations

• Publié par: pefav
• Nombre de lectures: 68
• Langue: Français

Extrait

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 a  labase 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