NumérationP. ÉzéquelRésuméCe do ument rassemble les notes de ours, les TD et ertains TP d'un enseigne-ment donné en première année de DEUG s ienti�que. Cet enseignement se veut uneinitiation aux on epts de l'algorithmique, via l'arithmétique et la représentation desnombres, entiers ou pas. L'obje tif pédagogique est triple : d'une part, rassembler dela manière la plus ohérente possible diverses façons qu'ont trouvées les mathémati- iens (et les autres !) d'é rire les nombres ; ensuite, de présenter les solutions retenuespar les informati iens pour représenter les nombres en ma hine, en n'oubliant pas demontrer les limitations inhérentes à une telle représentation, e qui me semble devoirfaire partie de la ulture de base de tout futur s ienti�que né essairement amené, au ours de sa vie professionnelle, à utiliser de telles représentations dans la modélisationdu monde réel ; en�n, e qui de mon point de vue est le plus important, pro�ter de eque les objets et on epts manipulés soient su�samment familiers aux étudiants pourintroduire une véritable démar he algorithmique, 'est-à-dire on evoir, prouver, etdans ertains as mesurer et omparer des algorithmes ensés résoudre des problèmespré is (un le teur attentif pourra ompter une vingtaine d'algorithmes di�érents dansle do ument, que e soit dans le texte ou dans les exer i es).

1

TABLE DES MATIÈRES 2Table des matières1 Introdu tion 32 É riture des nombres entiers 42.1 Changement de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Un as parti ulier très important . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Un peu d'exotisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.1 Base Fibona i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.2 Systèmes d'Avizienis . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3.3 Le système Bi-Binaire . . . . . . . . . . . . . . . . . . . . . . . . . . 12Exer i es de la partie 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 É riture des nombres non entiers 193.1 Changement de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.1 Cas des rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.2 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Exer i es de la partie 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Représentation des entiers 254.1 Prin ipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25Exer i es de la partie 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 Représentation des réels (TD) 275.1 Prin ipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Erreur sur la représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Soustra tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.4 Arrondi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 Additions 296.1 Algorithme � lassique � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.2 Algorithme d'Avizienis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Exer i es de la partie 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 Multipli ations 347.1 L'algorithme � lassique � . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.2 La multipli ation des paysans russes (TD) . . . . . . . . . . . . . . . . . . . 35Exer i es de la partie 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1 INTRODUCTION 31 Introdu tionHistoriquement, les ordinateurs sont avant tout des ma hines à al uler : 'est d'ailleurslà l'unique utilisation qui a été faite du premier d'entre eux, l'ENIAC. Il semble don naturelde démarrer un ours d'initiation à l'informatique par une étude de la représentation desnombres (entiers ou pas), ainsi que des algorithmes fondamentaux de manipulation quesont l'addition et la multipli ation.Obje tifsL'obje tif de e ours est double :1. onnaître (et omprendre) divers systèmes de représentation des nombres, ainsi queles tradu tions d'un système à l'autre. Ce i in lut non seulement les représentations�abstraites�, ou de haut niveau, omme par exemple la représentation Fibona i, quine sont pas naturellement elles hoisies pour représenter les nombres en ma hine,mais aussi les représentations � on rètes�, 'est-à-dire elles qu'une ma hine peututiliser ave plus ou moins de pro�t (et on verra notamment ertains des problèmesposés par la représentation des réels en virgule �ottante).2. introduire des rudiments d'algorithmique, par le biais des opérations de base sur lesnombres (addition et multipli ation prin ipalement, mais d'autres aussi, f les diversexer i es). Ce i in lut les notions de preuve (de orre tion ou d'arrêt) d'algorithme,ainsi que des notions de omplexité, par l'estimation, la plus pré ise possible, dunombre d'opérations élémentaires e�e tuées par un algorithme en fon tion de la taillede ses données d'entrée.Note aux étudiantsAutant que faire se peut, j'ai essayé de rédiger le plus lairement possible les preuves desa�rmations ontenues dans le texte (théorèmes et autres). La le ture de es preuves n'estpas né essaire à la ompréhension des notions exposées, mais elle est évidemment fortementen ouragée (ne serait- e que par l'utilisation qui est faite de te hniques de preuve auxquellesvous n'êtes pas a outumés).Con ernant les exer i es, la plupart sont originaux ; d'autres font partie du folklore (parexemple les jeux d'allumettes). Ils sont, dans leur grande majorité, relativement fa iles :il s'agit de simples appli ations du ours, et sinon quelques minutes de ré�exion devraientsu�re. Quelques-uns sont par ontre beau oup plus retors, et ils sont alors indiqués parune ou deux étoiles, selon leur degré de di� ulté.BibliographieLes prin ipales sour es que j'ai utilisées sont les suivantes :1. David GOLDBERG, What Every Computer S ientist Should Know About Floating-Point Arithmeti , ACM Computing Surveys, Vol. 23, No 1, Mar h 1991, pp 5�48 ;2. Ronald GRAHAM, Donald KNUTH, Oren PATASHNIK, Con rete Mathemati s : AFoundation for Computer S ien e, Addison-Wesley ;3. Donald KNUTH, The Art of Computer Programming, volume 2, �Seminumeri alAlgorithms�, Addison-Wesley ;4. Jean-Marie MULLER, Arithmétique des ordinateurs, Masson.

2 ÉCRITURE DES NOMBRES ENTIERS 42 É riture des nombres entiersPour représenter les entiers (et les nombres de façon plus générale), il va nous fal-loir diviser. Le premier résultat, élémentaire (puisqu'il est enseigné à l'é ole élémentaire), on erne la division dite �eu lidienne� :Théorème 2.1 Soient a et b deux entiers positifs, b > 1. Il existe un unique ouple d'en-tiers (q, r) véri�ant(1) a = b.q + r

(2) 0 ≤ r < bPreuve : elle est en deux parties. On démontre d'abord l'existen e d'un tel ouple, puisson uni ité.Existen e : si a = 0, il su�t de prendre q = 0 et r = 0. Sinon, 0 < a, et onsidéronsl'ensemble d'entiers Q = {n ∈ IN | b.n ≤ a}. Q est non vide, puisque 0 en est l'un deséléments. Il est de plus borné, ar les relations 1 < b et 0 < a impliquent que a < a.b, quiimplique à son tour que tous les éléments n de Q véri�ent n < a. Il est don �ni, et admet(d'après les propriétés bien onnues de IN ) un plus grand élément, notons-le q. On note rla di�éren e entre a et b.q : par onstru tion, a = b.q + r et 0 ≤ r. Il reste à montrer quer < b : supposons au ontraire que b ≤ r ; alors (par dé�nition de ≤ 1 ) il existe un entieri ≥ 0 tel que r = b + i ; on aurait alors

a = b.q + r = b.q + b + i = b.(q + 1) + i, e qui implique (par dé�nition de ≤) que b.(q + 1) ≤ a, 'est-à-dire que q ne serait pas leplus grand élément de Q, e qui est ontraire aux hypothèses.Uni ité : supposons qu'il existe deux ouples, (q, r) et (q′, r′), véri�ant les deux pro-priétés. On aurait alorsb.q + r = b.q′ + r′puisque les deux expressions sont, d'après (1), toutes deux égales à a, et don , par del'algèbre simple,b.(q − q′) = r′ − r 'est-à-dire que r′ − r est un multiple de b. Comme r et r′ véri�ent tous deux (2), leurdi�éren e véri�e−b < r′ − r < bOr le seul multiple de b stri tement ompris entre −b et b est 0 : on a né essairement

r′ − r = 0, don r = r′, et par onséquent q = q′ �L'entier q s'appelle le quotient de a par b, r est le reste de la division. On note aussiq = adiv b et r = a mod b. Remarquons que, si a > 0, q < a. Le résultat suivant (dontnous donnerons deux preuves) appelé théorème de numération, donne une représentationdes entiers :Théorème 2.2 Soit b > 1. Pour tout x ∈ IN , il existe un unique k ≥ 0 et une uniquesuite d'entiers x0, . . . , xk tels que

(1) x =

k∑

i=0

xibi

(2) ∀i ∈ {0, . . . , k}, 0 ≤ xi < b1Soient x et y deux entiers ; x ≤ y si et seulement si il existe e ≥ 0 tel que x + e = y

2 ÉCRITURE DES NOMBRES ENTIERS 5Preuves : nous allons voir deux preuves de e théorème. Comme souvent en informatique, ha une des preuves va donner lieu à un algorithme qui nous permettra de trouver lareprésentation d'un entier dans une base quel onque.Preuve 1 : ette preuve, bien que valable pour tout b > 1, donne lieu à un algorithmebien adapté au as où b = 2, et beau oup moins pratique dans les autres as. Distinguonsdeux as :1. x < b : alors il su�t de prendre k = 0, x0 = x et le tour est joué.2. b ≤ x : alors, grâ e à des propriétés bien onnues de N, il existe k ≥ 1 tel quebk ≤ x < bk+1On onsidère la suite de ouples (xi, ri) dé�nie pour 0 < i ≤ k par

{(xk, rk) est la division eu lidienne de x par bkpour1 ≤ i < k, (xi, ri) est la division eu lidienne de ri+1 par biet on pose x0 = r1. Notons que les xi sont uniques (puisqu'ils sont des quotientseu lidiens, ou un reste pour x0), et qu'ils véri�ent bien (2) : e i résulte de e que,par onstru tion, ri < bi, et du fait que l'on ne manipule que des nombres positifs. Ilreste à montrer (1). On va se servir de la propriété suivante : pour tout i ∈ {1, . . . , k},

ri =

i−1∑

j=0

xj .bjMontrons-la par ré urren e sur i :� on a r1 = x0 = x0.1 = x0.b

0, et la propriété est véri�ée au rang 1 ;� supposons la propriété vraie au rang i < k, et montrons-la au rang i + 1 :ri+1 = xi.b

i + ri (par dé�nition)= xi.b

i +

i−1∑

j=0

xj .bj (par hypothèse de ré urren e)

=

i∑

j=0

xj.bjIl ne nous reste plus qu'à véri�er (1) :

x = xk.bk + rk (par dé�nition)

= xk.bk +

k−1∑

i=0

xi.bi (propriété i-dessus au rang k)

=

k∑

i=0

xi.biPreuve 2 : ette deuxième preuve est elle qui est en général utilisée pour trouverl'é riture d'un nombre dans une base quel onque. En ore une fois, distinguons deux as :1. x < b : alors il su�t de prendre k = 0, x0 = x et le tour est joué.2. b ≤ x : on onsidére la suite de ouples d'entiers (qi, xi)i∈N dé�nie par

(q0, x0) est la division eu lidienne de x par b

2 ÉCRITURE DES NOMBRES ENTIERS 6et, pour i ≥ 1,

(qi, xi) est la division eu lidienne de qi−1 par bCette suite est stationnaire, de valeur (0, 0), à partir d'un ertain rang, et il existeun rang, notons-le k, tel que qk = 0 et xk > 0 (la preuve de es assertions est laisséeen exer i e). La propriété (2) est bien véri�ée, puisque les xi sont des restes dedivisions eu lidiennes. De même, les xi sont uniques, d'après le théorème pré édent.Il reste maintenant à prouver la propriété (1). À et e�et, on va montrer que, pouri ∈ {0, . . . , k},

qi =

i+1∑

j=k

xj .bj−(i+1)La preuve se fait par ré urren e des endante sur i :� ommençons par le as de base i = k : on a, puisque l'intervalle [k + 1, k] est vide,

qk =

k+1∑

j=k

xj.bj−i = 0� supposons la propriété vraie pour i > 0, et montrons que la relation est en orevéri�ée pour i − 1 :

qi−1 = b.qi + xi par dé�nition= b.

i+1∑

j=k

xj.bj−(i+1) + xi par hypothèse de ré urren e

=

i+1∑

j=k

xj.bj−(i+1)+1 + xi.b

0

=

i+1∑

j=k

xj.bj−((i−1)+1) + xi.b

i−((i−1)+1)

=

(i−1)+1∑

j=k

xj .bj−((i−1)+1)qui est la formule que l'on voulait obtenir.À l'aide de ette relation entre les qi et les xi, on va pouvoir maintenant démon-trer (1) : on a

x = b.q0 + x0 par dé�nition de (q0, x0)

= b.

1∑

j=k

xj.bj−1 + x0 d'après la propriété pré édente, é rite pour i = 0

=1∑

j=k

xj .bj + x0.b

0

=

k∑

j=0

xj .bj

� La suite �nie (x0, . . . , xk) s'appelle représentation de x en base b ou é riture de x enbase b. Les xi sont les hi�res de x en base b. Le poids d'un hi�re est son indi e. On é rit x

2 ÉCRITURE DES NOMBRES ENTIERS 7en général à l'envers, en donnant les hi�res de poids fort en premier, et en terminant parle hi�re des unités x0. On peut, si le ontexte le justi�e, indi er ette é riture par la base,pour souligner la base de représentation dans le as où l'on utilise simultanément plusieursbases. Remarquons que, d'après le point (2) du théorème de numération, les hi�res enbase b sont les entiers 0,1,. . . ,b − 1 : il y en a exa tement b. Si b > 10, il va nous falloirdes hi�res supplémentaires : l'usage veut qu'on prenne les lettres à partir de A. Ainsi les hi�res en base 16 sont0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,C,D,E, F.Remarque : nous sommes habitués à manipuler des nombres é rits en base 10. Il vanous falloir distinguer entre di�érentes représentations des nombres. Nous adopterons la onvention suivante, dans toute la suite de e do ument : une é riture normale d'un nombreindiquera qu'il est é rit en base 10. Ainsi par exemple 1253 dénote bien l'entier mille deux ent inquante trois. Pour é rire un nombre en base b, on indi era sa représentation par labase. Par exemple, 12537 désigne le nombre dont la représentation en base 7 omporte 4 hi�res, le plus lourd étant 1 et le plus léger 3.Exemples :1. Reprenons le nombre 12537. Quelle est sa représentation en base 10 ? Il su�t dereprendre la formule donnée dans le théorème de numération. La notation 12537désigne en fait la formule

k∑

i=0

xibidans laquelle k = 3, b = 7, x0 = 3, x1 = 5, x2 = 2 et x3 = 1, e qui donne (si oné rit en base 10)

∑ki=0 xib

i = 3.70 + 5.71 + 2.72 + 1.73

= 3.1 + 5.7 + 2.49 + 1.343= 3 + 35 + 98 + 343= 4792. onsidérons le nombre dénoté par 1001102. On a k = 5 et b = 2, et sa valeur en base10 est donnée par

∑ki=0 xib

i = 0.20 + 1.21 + 1.22 + 0.23 + 0.24 + 1.25

= 0.1 + 1.2 + 1.4 + 0.8 + 0.16 + 1.32= 0 + 2 + 4 + 0 + 0 + 32= 382.1 Changement de baseIl nous faut maintenant répondre à une question ru iale : omment obtient-on lareprésentation d'un nombre dans une base donnée ? Supposons, pour ommen er, que l'ondispose d'un nombre n é rit en base 10. L'algorithme de passage dans une base b > 1 leplus général est elui donné dans la deuxième preuve du théorème de numération : on faitdes divisions su essives, d'abord de n par b, puis des quotients obtenus (par b toujours),jusqu'à tomber sur un quotient nul. L'é riture de n en base b est alors la suite des restes,prise en sens inverse. Illustrons e i par un exemple : quelle est la représentation de 479en base 7 ?� on a 479 = 7.68 + 3, don le dernier hi�re de 479 en base 7 est 3 ;

2 ÉCRITURE DES NOMBRES ENTIERS 8� on a 68 = 7.9 + 5, don le hi�re de poids 1 de 479 en base 7 est 5 ;� on a 9 = 7.1 + 2, don le hi�re de poids 2 de 479 en base 7 est 2 ;� on a 1 = 7.0 + 1, don le hi�re de poids le plus élevé de 479 en base 7 est 1.En prenant es hi�res dans l'ordre inverse, on obtient479 = 12537En pratique, on dispose les al uls de la façons suivante :

479 = 7 × 68 + 368 = 7 × 9 + 59 = 7 × 1 + 21 = 7 × 0 + 1On arrête dès que le quotient devient nul, et la représentation de n en base b se lit de basen haut.Le as parti ulier de la base 2 : La première preuve du théorème donne un algorithmequi est e� a e pour trouver la représentation en base 2 d'un entier, dès lors que l'on onnaît bien les puissan es de 2 ( e qui est le as de n'importe quel informati ien dignede e nom. . . ). En e�et, les quotients des divisions eu lidiennes su essives (qui sont les hi�res du nombre en base 2) ne peuvent prendre que les valeurs 0 ou 1. Il su�t don de soustraire les puissan es de 2, en ommençant par la plus grande inférieure à n, et de ontinuer jusqu'à e qu'on arrive à 0. Le hi�re de poids i de l'é riture de n en base 2 sera1 si l'on a soustrait 2i, et 0 sinon. Trouvons par exemple la représentation en base 2 de479. Pour simpli�er, on va ommen er par é rire les puissan es de 2 :

k 0 1 2 3 4 5 6 7 8 9 . . .

2k 1 2 4 8 16 32 64 128 256 512 . . .On a alors :479 − 256 = 223 et le hi�re de poids 8 est don 1223 − 128 = 95 et le hi�re de poids 7 est don 1

95 − 64 = 31 et le hi�re de poids 6 est don 131 − 16 = 15 et le hi�re de poids 4 est don 115 − 8 = 7 et le hi�re de poids 3 est don 17 − 4 = 3 et le hi�re de poids 2 est don 13 − 2 = 1 et le hi�re de poids 1 est don 11 − 1 = 0 et le hi�re de poids 0 est don 1Tous les autres hi�res sont 0, et l'é riture de 479 en base 2 est 1110111112Nous savons don omment passer de la représentation en base 10 à n'importe quellebase et vi e-versa. Mais omment fait-on pour passer d'une représentation à une autre,dans le as où au une des deux bases n'est 10 ? Supposons que l'on veuille l'é riture enbase 3 du nombre (é rit en base 5) 4315. Il y a deux manières de faire :1. on trouve l'é riture en base 10 de 4315 en utilisant la formule du théorème de nu-mération, puis on e�e tue les divisions né essaires pour trouver l'é riture en base3 : ∑k

i=0 xibi = 4.52 + 3.51 + 1.50

= 4.25 + 3.5 + 1.1= 100 + 15 + 1= 116

2 ÉCRITURE DES NOMBRES ENTIERS 9puis116 = 3 × 38 + 238 = 3 × 12 + 212 = 3 × 4 + 04 = 3 × 1 + 11 = 3 × 0 + 1et on a 4315=110223.2. on peut être plus rapide, et se passer de la transformation en base 10 en e�e tuantles divisions dire tement en base 5 : pour ela, il faut onnaître ( omme en base 10 !)ses tables d'addition et de multipli ation en base 5. On obtient alors :4315 = 35 × 1235 + 251235 = 35 × 225 + 25225 = 35 × 45 + 0545 = 35 × 15 + 1515 = 35 × 05 + 15et on retrouve, en lisant les hi�res de bas en haut, 4315=110223.2.2 Un as parti ulier très importantIl s'agit des passages entre les bases b et bk, pour k > 1. Soit n un entier.Passage de la base b à la base bk :On dé oupe la représentation de n en base b en tran hes de k hi�re, en ommençantpar la droite et en rajoutant des 0 à gau he si le nombre de hi�res de n n'est pas unmultiple de k. Chaque tran he de k hi�res est alors transformée en un hi�re en base bk.Ces hi�res, é rits dans et ordre, onstituent l'é riture de n en base bk.Par exemple, soit 10221023 à é rire en base 9 = 32. On le oupe en tran hes de k = 2 hi�res, à partir de la droite, en rajoutant un 0 au début puisque le nombre de hi�resn'est pas un multiple de 2 : 10221023 = 01 02 21 02On é rit haque tran he omme un hi�re en base 9 :013=19, 023=29, 213=79, 023=29.L'é riture de 10221023 en base 9 est don 12729Passage de la base bk à la base b :C'est la transformation inverse ; il su�t d'exprimer haque hi�re en base bk omme unnombre é rit en base b sur k hi�res, en rajoutant des 0 si l'é riture du nombreobtenu omporte moins de k hi�res en base b.Par exemple, on souhaite obtenir l'é riture en base 2 du nombre E80116. 16 = 24, et ilfaut traduire haque hi�re en base 16 par un nombre de 4 hi�res en base 2. On aE16=11102, 816=10002, 016=02=00002, 116=12=00012.On a don E80116 = 1110.1000.0000.00012 (les points ont été ajoutés dans un sou i delisibilité, ils ne sont pas né essaires).

2 ÉCRITURE DES NOMBRES ENTIERS 102.3 Un peu d'exotismeJusqu'i i on a parlé d'é riture des entiers, dans un adre standard. Il existe beau oupd'autres façons de représenter des nombres, et nous allons en voir trois :� la représentation en �base Fibona i� : omme son nom l'indique, elle utilise lesvaleurs de la élèbre suite de Fibona i. Cette représentation est peu pratique pourles al uls (par exemple l'addition en base Fibona i est loin d'être triviale, pourne pas parler de la multipli ation). On la retrouve ependant dans de nombreuxproblèmes, où le simple fait d'é rire les nombres manipulés dans ette base rend larésolution évidente.� les systèmes d'Avizienis : il s'agit d'une représentation standard dans laquelle les hi�res peuvent être négatifs. Une des onséquen es importantes de l'introdu tion de hi�res négatifs est l'existen e d'un algorithme très e� a e d'addition, omme on leverra plus loin.� en�n, pour égayer un peu le ton un peu austère de e do ument, nous parleronsdu système de numération dit � Bi-Binaire �, que nous devons au regretté BobyLapointe.2.3.1 Base Fibona iOn rappelle la dé�nition de la suite de Fibona i :F0 = 0, F1 = 1, et pour n > 1, Fn = Fn−1 + Fn−2Les premières valeurs de ette suite sont

k 0 1 2 3 4 5 6 7 8 9 . . .

Fk 0 1 1 2 3 5 8 13 21 34 . . .Les nombres de Fibona i sont présents dans quantité de domaines, qu'ils soient de na-ture mathématique, informatique, voire biologique. Comme l'a dit un de leurs dé ouvreurs,La suite de Fibona i possède des propriétés nombreuses fort intéressantes2La propriété qui nous intéresse i i est le sujet du théorème suivant, dit �de Ze kendorf� :Théorème 2.3 Tout entier stri tement positif n a une unique représentation de la formen = Fk1

+ Fk2+ · · · + Fkrvéri�ant les propriétés1. pour i ∈ {1, . . . , r − 1}, ki ≥ ki+1 + 22. kr ≥ 2Ce théorème donne un nouveau système de numération : l'é riture d'un nombre en baseFibona i est une suite de 0 et de 1, omme en base 2, sauf que d'après la ondition (1)on ne peut avoir deux 1 onsé utifs : en e�et, la somme de deux nombres de Fibona i onsé utifs est un nombre de Fibona i, par dé�nition. On a alors (les bi représentent soit0 soit 1)

n = (bmbm−1 . . . b2)F ⇐⇒ n =

m∑

i=2

biFi2Édouard Lu as, Théorie des nombres, Gauthier-Villars, Paris, 1891. Cité dans Graham, Knuth, Pata-shnik, Con rete Mathemati s, A Foundation for Computer S ien e, Addison-Wesley, 1992.

2 ÉCRITURE DES NOMBRES ENTIERS 11Donnons un exemple : quelle est la représentation Fibona i de 30 ? On a30 = 21 + 8 + 1 = 1.F8 + 0.F7 + 1.F6 + 0.F5 + 0.F4 + 0.F3 + 1.F2et l'é riture de 30 en base Fibona i est 1010001F ( omme de outume, les hi�res de poidsforts sont à gau he).2.3.2 Systèmes d'AvizienisPourquoi restreindre les hi�res de l'é riture en base b à être dans l'ensemble {0, . . . , b−

1} ? Que se passe-t-il si l'on s'autorise des hi�res négatifs ? Ce sont les questions auxquellesnous allons répondre.Dé�nition 2.1 Soit b > 1. Un système de numération d'Avizienis de base b est la donnéed'un ensemble de hi�res C tel que1. C = {−a,−a + 1, . . . , 0, . . . , a − 1, a}2. a ≤ b − 13. b + 1 ≤ 2aL'ensemble C est l'ensemble des hi�res que l'on va utiliser pour é rire les nombres enbase b. Les onditions sur C sont très peu ontraignantes, mais on peut noter que les deuxdernières ex luent l'usage de la base 2 : les systèmes d'Avizienis ne sont utilisables que pourdes bases stri tement plus grandes que 2. On utilise en général les ensembles de hi�resC1

b = {−(b − 1), . . . , 0, . . . , b − 1}ou bien, en arrondissant (b + 1)/2 à l'entier immédiatement inférieur,C2

b = {−(b + 1)/2, , . . . , 0, . . . , (b + 1)/2}Les hi�res négatifs sont é rits ave une barre au-dessus : ainsi 7 désigne le hi�re −7.Exemples :1. Considérons le système d'Avizienis de base 10 dont les hi�res sontC1

10 = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Dans e système, le nombre 7 admet omme é riture 7 ( omme on pouvait s'y at-tendre !), mais aussi 13 ( ar 7 = 10 − 3), mais aussi 193 ( ar 7 = 100 − 93), et, defaçon générale, toute é riture de la forme 19 . . . 93 représente 7.2. Toujours en base 10, on prend omme ensemble de hi�resC2

10 = {5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5}Trouvons une représentation de 63 : on a 63 = 100 − 37, et 37 = 40 − 3, don 63 = 100 − 40 + 3 et une représentation de 63 dans ette base est 143.3. Dans le système d'Avizienis de base 5 et de hi�res

C25 = {3, 2, 1, 0, 1, 2, 3}les nombres de 1 à 20 peuvent s'é rire

1 = 15A 6 = 115A 11 = 215A 16 = 315A

2 = 25A 7 = 125A 12 = 225A 17 = 325A

3 = 35A 8 = 135A 13 = 235A 18 = 335A

4 = 115A 9 = 215A 14 = 315A 19 = 1115A

5 = 105A 10 = 205A 15 = 305A 20 = 1105A

2 ÉCRITURE DES NOMBRES ENTIERS 12I i aussi, on remarque que 12, par exemple, a plusieurs é ritures :� 225A, ar 12 = 2 × 5 + 2 ;� 335A, ar 12 = 3 × 5 − 3 ;� et 1235A, ar 12 = 1 × 52 − 2 × 5 − 3.L'un des avantages des systèmes d'Avizienis, qui en fait un andidat intéressant pour lareprésentation en ma hine, est que le passage de n à −n se fait simplement en hangeant lessignes des hi�res, e qui implique qu'il su�t de savoir additionner pour savoir soustraire, etdon que le même algorithme va servir aussi bien pour l'addition que pour la soustra tion.Ce i a un prix, visible sur les exemples : on ne peut plus garantir que la représentationd'un nombre soit unique.2.3.3 Le système Bi-BinaireLe système de numération Bi-Binaire a été mis au point par Boby Lapointe dans lesannées 60 (1969). Il s'agit moins d'un système de numération que d'une façon d'é rire lesentiers, la motivation prin ipale étant de pouvoir énon er des nombres, aussi grands soient-ils, sans qu'il soit besoin d'inventer des mots (une autre motivation, tout aussi importante,est de se donner la possibilité d'euphonies et d'allitérations qui sont la marque distin tivede l'÷uvre de Boby Lapointe, et dont on peut raisonnablement penser qu'elles fournirontla matière à quantité de alembours et autres � lape-près �. . . ).On onsidère la base 16. Dans ette base, il y a 16 hi�res, de 0 à F ; si l'on é rit es hi�res en base 2, ha un est représenté par quatre hi�res. Ainsi 5 s'é rit 01012, et D s'é rit11012. Si l'on dé oupe es é ritures en base 2 en deux groupes de deux hi�res binairespar le milieu, e qui n'est pas à onseiller, on obtient deux moitiés de hi�re hexadé imal,et deux bits d'un �té, et deux bits de l'autre. Les deux bits de gau he s'appellent (par onséquent ?) les bits de poids forts3, les deux bits de droite onstituant les poids faibles.Le système Bi-Binaire onsiste à faire orrespondre à ha un de es groupes une lettre,selon les tableaux suivants :Poids forts00 H01 B10 K11 D Poids faibles00 O01 A10 E11 ILes hi�res en base 16 se traduisent don de la façon suivante :Base 16 Base 2 Bi-binaire Base 16 Base 2 Bi-binaire0 0000 HO 8 1000 KO1 0001 HA 9 1001 KA2 0010 HE A 1010 KE3 0011 HI B 1011 KI4 0100 BO C 1100 DO5 0101 BA D 1101 DA6 0110 BE E 1110 DE7 0111 BI F 1111 DIAinsi, 31, qui s'é rit 1F16, devient HADI, et KAHABA dénote l'entier qui s'é rit 915 enbase 16, 'est-à-dire 2325 en base 10. L'entier 1000, quant à lui, s'é rit HIDEKO. En�n,3et 'est i i que nous devons abandonner la �guitare sommaire �

2 ÉCRITURE DES NOMBRES ENTIERS 13si un ommerçant peut parler d'HAHIKIDO quotidien, il ne s'agit pas d'arts martiaux,mais simplement de son hi�re d'a�aire (Exer i e : al uler du oup son hi�re d'a�aireannuel).

2 ÉCRITURE DES NOMBRES ENTIERS 14Exer i es de la partie 22.1 - Quels sont les hi�res en base 13 ?2.2 - Donner la représentation des nombres 45, 128, 91, 1654 en base 3, 5, 7, 13.2.3 - E�e tuer les opérations suivantes, sans repasser par la base 10 :1. (base 7) 456 601 143+ 15 - 142 * 252. (base 4) 112 331 231+ 13 - 12 * 122.4 - (Passages entre les bases 2, 4, 8 et 16)1. Donner la représentations des nombres suivants (é rits en base 2) dans les bases4, 8 et 16 : 10011101 100110011001100 101011100011100111001110012. Donner la représentations des nombres suivants (é rits en base 8) dans les bases2, 4 et 16 : 50234 254120 15473. Donner la représentations des nombres suivants (é rits en base 4) dans les bases2 et 16 : 10232 203012 2223304. Donner la représentations des nombres suivants (é rits en base 16) dans les bases2 et 4 : 4E0F 1FF8 ABCD2.5 - Programmer l'algorithme de hangement de base ave un tableur (de la base 10 versune base b quel onque, puis l'inverse).2.6 - Véri�er que, en base 4, 6 = 2 × 3 s'é rit 12, 9 = 32 s'é rit 21. Véri�er de même que12 = 2×6 et 36 = 62 s'é rivent respe tivement 15 et 51 en base 7, et que 30 = 2×15et 225 = 152 s'é rivent 1E et E1 en base 16.Généraliser : soit b un entier plus grand que 4. Montrer que le double de b− 1 s'é rit1(b-2) en base b, et que, dans ette même base, son arré s'é rit (b-2)1.2.7 - Trouvez la ou les bases dans ha un des as suivants. Justi�ez votre réponse.1. 34 (é rit en base 5) s'é rit 31 en base b. Trouvez b.2. 482 (é rit en base 10) s'é rit 742 en base b′. Trouvez b′.

2 ÉCRITURE DES NOMBRES ENTIERS 153. Un nombre s'é rit 42 en base b1 et 31 en base b2. Un autre nombre s'é rit 14 enbase b1 et 12 en base b2. Trouvez b1 et b2.2.8 - Autrefois, lorsque les al ulatri es de po he n'existaient pas, on utilisait des tru s etastu es divers (des algorithmes) pour al uler. Ainsi, on utilisait l'algorithme suivantpour élever au arré les nombres entiers dont l'é riture en base 10 se termine par 5 :� soit à élever au arré le nombre n5 (prenons par exemple 65) ;� on multiplie n par n+1 pour obtenir le nombre m : i i, on obtient m= 6 × 7 = 42 ;� le arré her hé est la on aténation de m et 25 : i i, on obtient 652 = 4225, equ'on peut fa ilement véri�er.1. Justi�er et algorithme, 'est-à-dire montrer que le résultat est toujours orre t,quel que soit l'entier (�nissant par 5) hoisi.2. Généraliser : donner et justi�er un algorithme simple permettant d'obtenir l'é ri-ture en base 2b du arré d'un nombre dont l'é riture dans ette base se terminepar b.2.9 - Soit x un nombre é rit en base 6. Comment re onnaît-on que x est pair ? Que x estmultiple de 3 ?Plus généralement, en base a.b, omment re onnaît-on simplement qu'un nombreé rit dans ette base est un multiple de a ou de b ?2.10 - Jeu de NIM : e jeu se joue à 2 joueurs. On dispose au départ d'un nombre quel onqued'allumettes, réparties en un nombre quel onque de tas. Chaque joueur à son tourenlève 0 ou 1 allumette à haque tas, mais au moins une allumette (on peut don enlever, à haque tour, un nombre d'allumettes ompris entre 1 et le nombre de tas onstituant la position). Le gagnant est elui qui enlève la dernière allumette.1. Parmi les positions suivantes, lesquelles sont gagnantes ?(1 1 1 1) (2 2 2) (1 1 2 2) (5 2 6 4 8) (3 9 11 7 15)2. Cara tériser les positions gagnantes, et montrer en parti ulier qu'il est toujourspossible de passer d'une position gagnante à une position perdante, mais quel'inverse est impossible.2.11 - Jeu de NIM : e jeu se joue à 2 joueurs. On dispose au départ d'un nombrequel onque d'allumettes, réparties en un nombre quel onque de tas. Chaque joueurà son tour enlève entre 1 et toutes les allumettes d'un seul tas. Le gagnant est eluiqui enlève la dernière allumette.1. Donner, parmi les positions suivantes, elles qui sont gagnantes :(5 3 9 10) (8 2 5 15) (1 5 3 2) (1 3 5 7)2. Montrer que le jeu de Nim est un as parti ulier du jeu pré édent, et en déduireune ara térisation des positions gagnantes au jeu de Nim.2.12 - La dernière du tas : e jeu se joue à 2 joueurs. On onstitue un tas ontenant unnombre quel onque d'allumettes. Chaque joueur à son tour enlève entre 1 et 2 fois

2 ÉCRITURE DES NOMBRES ENTIERS 16le nombre d'allumettes enlevées par le joueur pré édent. Par exemple, si l'adversairevient d'enlever 3 allumettes, on peut enlever 1, 2, 3, 4, 5 ou 6 = 2× 3 allumettes. Lepremier joueur enlève 1 ou 2 allumettes. Le gagnant est elui qui enlève la dernièreallumette.1. Pour ha un des tas de départ suivant, indiquer lequel, du premier ou dudeuxième joueur, a une ligne de jeu gagnante : 1, 2, 3, 5, 8, 13. Ces nombresvous rappellent-ils quelque hose ?2. Donner un algorithme qui mène, lorsque 'est possible, à une vi toire ontretoute défense.Solution de la dernière du tas : Soit d le nombre d'allumettes enlevées au ouppré édent (on pose d = 1 pour le premier joueur), et N le nombre d'allumettes restantdans le tas. L'é riture de N en base Fibona i est un mot é rit ave des 0 et des 1,et se terminant par la haîne 10k (un 1 suivi de k 0) : autrement dit, le plus petitnombre de Fibona i intervenant dans l'é riture de N est Fk+2. Alors de deux hosesl'une :� soit d <

⌈Fk+2

2

⌉ : la position est perdante, quel que soit le nombre d'allumettesque l'on enlève ;� soit d ≥⌈

Fk+2

2

⌉ : la position est gagnante, il su�t d'enlever Fk+2 allumettes.Exer i e subsidiaire di� ile : démontrer es allégations, surtout la première.Pour la deuxième, soit A le joueur qui enlève Fk+2 allumettes, et B son adversaire.De deux hoses l'une :1. soit il n'y a plus d'allumettes et A a gagné ;2. soit il en reste, et on va montrer par indu tion que B est dans une positionperdante. On avait au mieux N = N ′+Fk+4+Fk+2. Il reste N ′+Fk+4 allumettes,et il su�t de montrer queFk+2 <

⌈Fk+4

2

⌉

.Or e i est une banalité, ar on sait que Fn < Fn+1, e qui implique que 2Fn <Fn + Fn+1 = Fn+2. L'expression �au mieux� prend tout son sens si le nombrede Fibona i suivant Fk+2 dans l'é riture de N est plus grand que Fk+4.2.13 - Donner la représentation dans le système d'Avizienis de base 10 qui a pour hi�res

{−5,−4,−3,−2,−1, 0, 1, 2, 3, 4}des entiers de 0 à 30.2.14 - On onsidère le système d'Avizienis de base 10 qui a pour hi�res{−9, . . . , 0, . . . , 9}Donner toutes les représentations des nombres de 1 à 10.2.15 - On se propose d'étudier ertaines représentations d'Avizienis de base 10.1. Si a = 6, donner toutes les représentations des entiers de 1 à 20. Quel estle plus petit nombre à deux hi�res positifs qui admet deux représentations ?Et à 3 hi�res ? Montrer qu'au un entier inférieur à 1000 n'admet plus de 2représentations dans ette base.

2 ÉCRITURE DES NOMBRES ENTIERS 172. On onsidère maintenant a = 9. Donner le plus petit nombre à deux hi�respositifs admettant une in�nité de représentations, puis le plus petit à 3 hi�respositifs.2.16 - On se propose de trouver (et de justi�er) un algorithme simple permettant de dé-terminer si un nombre é rit dans une base b donnée est pair ou impair. On pourrait al uler la représentation en base 10 de e nombre, puis regarder le dernier hi�repour dé ider. Cependant, il est inutile de passer par la base 10 pour e i, et le butde l'exer i e est de trouver un moyen plus simple d'y parvenir.1. Donner l'é riture en base 3 de tous les nombres ompris entre 20 et 30 (20 et30 in lus). Même question pour la base 4.2. En s'inspirant de l'exemple de la base 4, trouver et prouver un ritère de paritédes nombres é rits dans une base paire.3. En s'inspirant de l'exemple de la base 3, trouver et prouver un ritère de paritédes nombres é rits dans une base impaire.2.17 - Soit x un nombre é rit en base 16. Comment sait-on, à la vue de son é riture en base16, que x est pair ? Que x est multiple de 4 ? Que x est multiple de 8 ?Plus généralement, en base bn, omment re onnaît-on simplement qu'un nombreé rit dans ette base est un multiple de bk (ave 0 < k ≤ n) ?2.18 - Justi�er la méthode de hangement de représentation entre les bases b et bk, et enparti ulier montrer qu'un nombre de k hi�res en base b est toujours stri tementinférieur à bk.2.19 - Soient b1 et b2 deux entiers plus grands que 1, tels que b2 < b1. On dit que les basesb1 et b2 sont amies s'il existe un entier qui s'é rit xy en base b1 et yx en base b2 (x ety doivent être di�érents de 0, et on a né essairement x 6= y). Par exemple, les bases5 et 3 sont amies ar 7 s'é rit 12 en base 5 et 21 en base 3. On dit d'un tel entierqu'il est le témoin de l'amitié de b1 et b2.1. Donner tous les témoins pour les base 3 et 5, 4 et 7 et 6 et 11.2. Montrer que si b1 = 2b2 − 1 alors b1 et b2 sont amies.3. Plus généralement, montrer que si b1 = kb2 − (k − 1) alors b1 et b2 sont amies(on dit que b1 est amie d'ordre k de b2). Donner la plus petite base ayant uneamie d'ordre k.2.20 - On se propose d'étudier ertaines propriétés de la base−2. Dans ette base, omme enbase 2, les hi�res sont 0 et 1. La notation xnxn−1 . . . x1x0 où pour tout i ∈ {0, . . . , n},x1 est le hi�re 0 ou le hi�re 1, désigne l'entier

n∑

i=0

xi.(−2)i

2 ÉCRITURE DES NOMBRES ENTIERS 18Par exemple,11011101 = 1.(−2)7 + 1.(−2)6 + 1.(−2)4 + 1.(−2)3 + 1.(−2)2 + 1.(−2)0

= −128 + 64 + 16 − 8 + 4 + 1

= −51On voit sur l'exemple que les entiers négatifs sont naturellement représentables dans ette base.1. Donner les représentations des entiers de −10 à 10.2. Énon er une méthode simple permettant de trouver l'é riture de −x (en base−2) à partir de elle de x (en base −2).3. On note Xn (ave n ≥ 1) le nombre dont l'é riture en base (−2) est omposéede n fois le hi�re 1 (par exemple X1 = 1, et X3 = 111). Montrer que

X2k+1 =1

3

(

22k+1 + 1)Que vaut X2k ? Et omment s'é rit −X2k en base -2 ?

3 ÉCRITURE DES NOMBRES NON ENTIERS 193 É riture des nombres non entiersPar dé�nition, un nombre x est non entier s'il existe un entier n tel quen < x < n + 1.

n est appelé la partie entière par défaut de x, notée⌊x⌋

n + 1 est appelé la partie entière par ex ès de x, notée⌈x⌉Le nombre x − n, noté {x}, appartient à l'intervalle [0, 1[. On a don toujours

x = ⌊x⌋ + {x}et la représentation de x est elle de ⌊x⌋, qui est un entier, suivie du ara tère �,� (ou �.�pour les anglo-saxons), suivi de la représentation de {x}. Comme on sait déjà représenterun entier, il reste à savoir omment représenter un élément de l'intervalle [0, 1[ : toute lasuite de la se tion est onsa rée à la représentation des nombres ompris entre0 (au sens large) et 1. C'est l'objet du résultat suivant :Théorème 3.1 Soit b > 1. Pour tout x ∈ [0, 1[, il existe une unique suite d'entiers(f1, f2, . . . , fn, . . .)véri�ant1. x =

∞∑

i=1

fi.b−i = f1.b

−1 + f2.b−2 + . . . =

f1

b+

f2

b2+ . . .2. pour tout i ≥ 1, 0 ≤ fi < bComme pour les nombres entiers, les hi�res utilisés pour é rire x en base b sont 0, 1,. . . ,

b − 1. On appelle parfois la suite (f1, f2, . . .) développement de x en base b. Remarquonsque la suite des hi�res fi est in�nie par dé�nition : elle peut éventuellement se terminerpar une in�nité de 0. Dans un tel as, on é rit seulement la partie ��nie� de la suite.Exemples :1. Le rationnel 1

2s'é rit 0, 5 en base 10 (tous les autres hi�res sont nuls), et 0, 1 enbase 2.2. Le même nombre s'é rit 0, 11111 . . . en base 3 (tous les hi�res sont égaux à 1).3.1 Changement de baseNous allons voir deux algorithmes de passage d'une base dans une autre, pour lesnombres non entiers, selon la forme de la suite des hi�res (f1, f2, . . .) qui onstitue leuré riture. Il y a deux sortes de nombres non entiers :1. les nombres rationnels, dont l'é riture est �ultimement périodique� : à partir d'un ertain rang, le même motif se répète. Par exemple, en base 10, 0, 234234234... (lemotif 234 se répète indé�niment), ou bien en ore 0, 2453535353... (les deux premiers hi�res sont 2 puis 4, et le motif 53 se répète indé�niment). Rentrent dans ette atégorie les nombres dont le développement en base b est �ni (le motif qui se répèteest 0 !). Les rationnels sont les résultats de la division d'un entier par un autre. Ainsi,

0, 234234234... est le résultat de la division de 26 par 111 (nous verrons plus loin om-ment l'on obtient les deux termes de la division). C'est don aussi le développementen base 10 du rationnel 26/111.

3 ÉCRITURE DES NOMBRES NON ENTIERS 202. les irrationnels, que l'on ne peut pas obtenir en divisant un entier par un autre.Dans ette atégorie, et parmi les plus onnus, on trouve √2, π ou en ore e. Pour es nombres, l'é riture (dans une base quel onque) ne présente pas de motifs qui serépètent indé�niment.Nous allons don voir deux méthodes de hangement de base, selon que l'on a a�aire àun rationnel ou à un irrationnel. Notons toutefois que la méthode pour les irrationnels estgénérale, en e qu'elle peut être appliquée quelle que soit la nature (rationnel ou irrationnel)du nombre dont on veut hanger la base de représentation. On dispose don de 2 méthodesdistin tes pour hanger la base de représentation d'un rationnel, et on hoisit en généralla plus rapide.Notation : dans le as d'un rationnel, on notera

0, x1x2 . . . xn p1p2 . . . pm︸ ︷︷ ︸le rationnel dont le développement ommen e par les hi�res x1, x2,. . . , xn et se poursuitave la répétition indé�nie du motif p1p2 . . . pm.3.1.1 Cas des rationnelsSoit le nombre (é rit en base b)

0, x1x2 . . . xn p1p2 . . . pm︸ ︷︷ ︸dont on veut trouver le développement en base b′. On a le résultat suivant (ave desnotations évidentes) :Théorème 3.2 Soit x = 0, x1x2 . . . xn p1p2 . . . pm

︸ ︷︷ ︸;1. si m = 0,

x = 0, x1x2 . . . xn =x1x2 . . . xn

bn2. si n = 0,x = 0, p1p2 . . . pm

︸ ︷︷ ︸=

p1p2 . . . pm

bm − 13. si n > 0 et m > 0,x = 0, x1x2 . . . xn p1p2 . . . pm

︸ ︷︷ ︸=

x1x2 . . . xn

bn+

1

bn.p1p2 . . . pm

bm − 1Preuve : le point 1 est évident (simple exploitation de la dé�nition), le point 3 est une onséquen e dire te des 2 points pré édents. Reste à prouver le point 2 : dire que l'é riturede x est périodique, de période m, revient à dire que les hi�res de numéro km + i, ave k ≥ 0 et 1 ≤ i ≤ m, sont égaux à pi. On a don

x = 0, p1p2 . . . pm︸ ︷︷ ︸

=

∞∑

k=0

m∑

i=1

pi

(1

b

)km+iDans la somme intérieure, on peut fa toriser par b−km, qui ne dépend pas du paramètrede sommation i :x =

∞∑

k=0

[(1

b

)km m∑

i=1

pi

(1

b

)i]

3 ÉCRITURE DES NOMBRES NON ENTIERS 21On remarque alors que la somme intérieure ne dépend pas du paramètre de sommation kde la somme extérieure, on peut don la fa toriser ; de plus, (1/b)km = (1/bm)k. On obtientx =

[m∑

i=1

pi

(1

b

)i]

·[

∞∑

k=0

(1

bm

)k]Or b > 1, du oup 0 < 1/bm < 1, et on a, pour 0 < α < 1,

∞∑

k=0

αk = limn→∞

n∑

k=0

αk = limn→∞

1 − αn+1

1 − α=

1

1 − αOn applique ette identité à la deuxième somme pour obtenirx =

[m∑

i=1

pi

(1

b

)i]

· 1

1 − 1/bm=

[m∑

i=1

pi

(1

b

)i]

· bm

bm − 1On fait alors rentrer le terme bm dans la somme pour obtenir �nalementx =

∑mi=1 pib

m−i

bm − 1et la formule ∑mi=1 pib

m−i dénote, bien sûr, l'entier qui s'é rit p1p2 . . . pm en base b. �Par exemple, prenons b = 10 et x = 0, 234︸︷︷︸

. On a n = 0, m = 3 et le théorème nous ditque0, 234︸︷︷︸

=234

103 − 1=

234

999=

9 × 26

9 × 111=

26

111 omme annon é pré édemment. On aurait pu aussi s'arrêter à la deuxième étape, 234/999.L'algorithme de passage de la base b à la base b′ est le suivant :1. Trouver, à l'aide du théorème, quelle est la fra tion, é rite en base b, qui orrespondà x (bm − 1 est une suite de m hi�res tous égaux à b − 1, de même qu'en base 1010m − 1 est une suite de m hi�res tous égaux à 10 − 1 = 9).2. Changer la représentation du numérateur et du dénominateur de la base b à la baseb′ omme vu pré édemment pour les entiers.3. E�e tuer la division en base b′.Exemple : Prenons b = 3, b′ = 4, et x = 0, 12

︸︷︷︸. On a n = 0, m = 2 et le théorème nousdit que

x =123

223Or 123=114 et 223=204, et 114 : 204 = 0,224don le développement de x en base 4 est 0,224.3.1.2 Cas généralSoit le nombre (é rit en base b) 0, f1f2 . . . dont on veut trouver le développement enbase b′. L'algorithme de passage est le suivant :1. Multiplier x par b′ (é rit en base b) ;2. le nombre à gau he de la virgule, traduit en base b′, est le hi�re suivant du dévelop-pement en base b′ de x ;

3 ÉCRITURE DES NOMBRES NON ENTIERS 223. ontinuer ave la partie fra tionnaire, et s'arrêter si elle est nulle.Exemple : Prenons b = 2, x = 0, 01101 et b′ = 10 ; on a 10 = 10102 et l'algorithme donne(les nombres sont é rits en base 2, et les al uls sont faits dans ette base)0,01101×1010 = 100 ,00010,0001×1010 = 0 ,10100,1010×1010 = 110 ,010,01×1010 = 10 ,10,1×1010 = 101 ,0 (la partie fra tionnaire est nulle, on s'arrête)et le développement de x en base 10 se lit de haut en bas, en traduisant les hi�res enbase 10 ; on obtient 0,011012 = 0,4062510Véri�ons en utilisant la première méthode, puisqu'on a a�aire à un rationnel :x = 0,011012 =

110121000002=

13

32et ette fra tion est bien égale à 0,40625.Exer i es de la partie 33.1 - Donner la représentation en base 7 du nombre qui s'é rit 0, 142857︸ ︷︷ ︸

en base 10.3.2 - Donner les dé imales numéro 1724555, 125698548754 et 12545215489658745323 del'é riture en base 16 de 1

113.3 - Donner la représentation en base 2 de e = 2, 7182818 . . . et π = 3, 1415926 . . . (10 hi�res signi� atifs).3.4 - Un nombre s'é rit 0, 2 en base b3, et 0, 6︸︷︷︸

en base b4. Trouvez b3 et b4.3.5 - On se propose d'expliquer une urieuse propriété des bases 2, 5 et 10.1. Remplir la table suivante :n 1 2 3 4 5

2n

5n

1

2n

1

5n2. Expliquer le phénomène observé. Qu'en déduisez-vous sur l'é riture en base 10des nombres réels dont l'é riture en base 2 ou 5 est �nie ?3.6 - Donner la représentation en base b de 1

b + 1et 1

b − 1.

3 ÉCRITURE DES NOMBRES NON ENTIERS 233.7 - Etudier les représentations de 1

2et 1

3.3.8 - Soient a et b deux entiers stri tement plus grands que 1.1. Quelle est l'é riture de 1

aen base ab ? En déduire les é ritures de 1

2, 1

4et 1

8enbase 16.2. Quelle est l'é riture de 1

aen base ab + 1 ? En déduire les é ritures de 1

3et 1

5enbase 16.3. Quelle est l'é riture de 1

ab + 2en base ab + 1 ?4. Quelle est l'é riture de 1

a − 1en base a3 − 1 ?3.9 - Donner l'é riture en base 8 du nombre 456

5. Quel est son132165498756251433265585252558874512-ième hi�re après la virgule ?3.10 - Trouver la représentation en base 3 du nombre qui s'é rit 0, 407

︸︷︷︸en base 10. Mêmequestion ave les nombres (toujours en base 10) 0, 148

︸︷︷︸et 0, 259

︸︷︷︸. Que remarquez-vous ?Plus généralement, montrer que le nombre (é rit en base 10) 0, abc

︸︷︷︸a un développe-ment en base 3 �ni si abc est un multiple de 37.3.11 - On se propose d'étudier le hangement de la base b à la base bk pour les nombresnon entiers.1. Exprimer ha un des nombres suivants (é rits en base 2) dans les bases 4 et 8 :0,11 0,0111 0,10011 0,1011011112. Dé rire en quelques mots (et si possible justi�er !) une méthode pour passer dela base b à la base bk, pour les nombres à virgule.3.12 - Soit un nombre N qui s'é rit c0, c1c2c3c4 sous forme dé imale en base 10. On peutaussi é rire e nombre sous la forme suivante, appelée forme de Horner :

N = c0 +1

10(c1 +

1

10(c2 +

1

10(c3 +

1

10(c4))))Par exemple, le nombre N = 1.739 s'é rit :

N = 1 +1

10(7 +

1

10(3 +

1

10(9)))On remarque que ette é riture n'est pas limitée aux nombres dont l'é riture dé imaleest �nie et ainsi le nombre 1/3 s'é rit :

N = 0 +1

10(3 +

1

10(3 +

1

10(3 +

1

10(...))))Dans l'é riture sous la forme de Horner, on remarque que le fa teur qui permet depasser à la dé imale suivante est 1

10 . Ce i est normal puisque l'on travaille en base10. Cependant rien ne nous oblige à rester en base 10.

3 ÉCRITURE DES NOMBRES NON ENTIERS 241. Si on rempla e 110 par 1

a, ave 1 < a, quelle est la valeur du nombre qui s'é rit2,22222... (... désigne une suite in�nie de 2) ?2. Plus généralement, on peut é rire un nombre N sous forme de Horner de lamanière suivante :

N = t0 + b0(t1 + b1(t2 + b2(t3 + b3(...))))La suite (b0, b1, b2, b3, ...) est appelé base de Horner et la séquen e [t0, t1, t2, t3, ...]est la représentation de N dans ette base. Dans le premier exemple, la basede Horner est onstante de valeur 110 et la représentation dans ette base dunombre 1/3 est [0,3,3,3,3,...℄. Dans ette base de Horner, la représentation detout nombre N orrespond à son é riture dé imale en base 10.On dé�nit maintenant la base de Horner suivante :

B = (1

1,1

2,1

3,1

4, ...)Donner l'é riture de e (base du logarithme népérien) sous la forme de Hornerave ette base. En déduire la représentation de e dans ette base de Horner.Rappel ( ?) :

e = limn→∞

n∑

k=0

1

k!3. La formule d'Euler nous donne π omme somme de la série suivante :π = 2

∞∑

n=0

2n(n!)2

(2n + 1)!Donner la 56765364986ème dé imale de la représentation de π dans la base deHorner dé�nie parB = (

2

3,4

5,18

7, . . . ,

2n2

2n + 1, . . .)

4 REPRÉSENTATION DES ENTIERS 254 Représentation des entiersL'é riture des entiers vue dans la se tion pré édente s'appelle représentation simple deposition. Ce n'est pas tout à fait elle hoisie pour représenter les nombres en ma hines.En e�et, il se pose le problème de la représentation des entiers négatifs. La solution utiliséedans le langage mathématique ourant onsiste à utiliser un symbole (+ ou −), pla é de-vant le nombre, indiquant s'il est positif ou négatif ; e système de représentation est appeléreprésentation simple de position ave bit de signe. Bien que d'usage ourant, e systèmeimplique qu'il faut deux algorithmes di�érents, l'un pour soustraire, l'autre pour addition-ner, et ela n'est ni souhaitable, ni né essaire, omme nous allons le voir. Le mé anisme dereprésentation des entiers en ma hine que nous allons maintenant détailler s'appelle repré-sentation simple de position, en omplément à la base, et permet, lui, d'utiliser le mêmealgorithme pour l'addition omme pour la soustra tion.4.1 Prin ipeClassiquement, et pour des raisons te hniques, les entiers manipulés par les ma hinessont limités en taille, 'est-à-dire en nombre de hi�res. Soit N le nombre de hi�res dispo-nibles : si la ma hine � travaille en base b �, elle peut manipuler tous les nombres omprisentre 0 et bN − 1, en représentation simple de position. Le prin ipe de la représentationsimple de position en omplément à la base onsiste à utiliser la moitié de et intervallede représentation pour représenter les nombres négatifs, selon la dé�nition suivante : soitR(x) la représentation de l'entier x, et supposons b pair ( 'est toujours le as, en généralb = 2, 4, 8, 16 ou 10)� si x ∈ [0,

bN

2− 1], alors R(x) = x.� si x ∈ [−bN

2, 0[, alors R(x) = x + bN .et les entiers (en ma hine) de bN

2à bN − 1 représentent les entiers négatifs de −bN

2à −1 .Exemple : prenons b = 10 et N = 2. Les entiers représentables vont de −bN

2= −102

2=

−50 à bN

2− 1 =

102

2− 1 = 49 et, par exemple, R(−16) = −16 + 100 = 84.4.2 OpérationsL'addition et la soustra tion sont assurées par le même algorithme, puisque les positifset les négatifs ont des représentations � ohérentes�. Notons ⊕ un algorithme d'addition( f se tion 6), supposé orre t ( 'est-à-dire donnant toujours le bon résultat) ; on dé�nitl'addition par

R(x + y) = R(x) ⊕ R(y)dont on ne garde que les N derniers hi�res.Exemple : prenons en ore une fois b = 10 et N = 2. On aR(25 + 13) = R(25) ⊕ R(13) = 25 ⊕ 13 = 38 = R(38)qui est bien le résultat. Si on onsidère les négatifs :

R(−16 − 25) = R((−16) + (−25)) = R(−16) ⊕ R(−25) = 84 ⊕ 75 = 159

4 REPRÉSENTATION DES ENTIERS 26que l'on tronque à 59 ; or 59 = −41 + 100 et don 59 = R(−41) et le résultat est en oreune fois exa t. En�n voyons la soustra tion :R(45 − 37) = R(45 + (−37)) = R(45) ⊕ R(−37) = 45 ⊕ 63 = 108que l'on tronque à 08 qui est la représentation de 8, résultat de la soustra tion de 37 à 45.Que se passe-t-il si l'on dépasse les bornes de représentation, 'est-à-dire si le résultatd'une addition est stri tement inférieur à −bN/2 ou stri tement supérieur à bN/2 − 1 ( eque l'on nomme un dépassement de apa ité) ? Examinons e as sur un exemple (toujoursen supposant b = 10 et N = 2) : soit à additionner 38 et 42. L'algorithme d'addition vadonner 80, qui est en fait la représentation de -20 ! Dans l'autre sens, si l'on additionnedeux nombres négatifs dont la somme est trop grande (en valeur absolue), on va obtenirun nombre positif :

R(−30 − 35) = R(−30) ⊕ R(−35) = 70 ⊕ 65 = 135tronqué à 35, qui est la représentation de 35 ! Résumons :� le résultat de l'opération 38 + 42 est −20 ;� le résultat de l'opération −30 − 35 est 35.La on lusion est la suivante : un dépassement de apa ité se traduit par un résultatde signe di�érent des opérandes. Il n'y a pas de dépassement de apa ité si les opérandessont de signes di�érents.Exer i es de la partie 44.1 - Montrer que si les opérandes d'une addition sont de signes di�érents, il ne peut pasy avoir de dépassement de apa ité.4.2 - La base est 4, le nombre de hi�res est 3. Donner tous les entiers représentables, etleur représentation.4.3 - La base est 10, le nombre de hi�res est 10. Donner les bornes de la représentation,et les représentations de −17914 et 59819.4.4 - La base est 10, le nombre de hi�res est 4. E�e tuer les opérations suivantes :4977 − 1728 3285 + 4827 1724 − 30214.5 - Étudier les di�érentes façons de représenter les négatifs en base 2.

5 REPRÉSENTATION DES RÉELS (TD) 275 Représentation des réels (TD)5.1 Prin ipeLes réels sont représentés par les nombres en virgule �ottante Soit b > 1 la base de lareprésentation, et soit p ≥ 1. Un nombre en virgule �ottante de base b et de pré ision pest un nombre de la forme±c0, c1 . . . cp−1 × beoù, pour i = 0, . . . , p − 1, 0 ≤ ci < b et emin ≤ e ≤ emax. La quantité e est appeléel'exposant. Le nombre c0, c1 . . . cp−1 est appelé la mantisse. Le signe est indiqué par unbit de signe, pla é devant la mantisse ou l'exposant (on n'utilise don pas la méthode du omplément à la base, ni pour la mantisse, ni pour l'exposant). On dit que la représentationest normalisée lorsque c0 6= 0, e que l'on supposera dans toute la suite.I - On pose b = 2, p = 3, emin = −1 et emax = 2. Donner tous les nombres �ottantspositifs de e système. Les dessiner sur un axe gradué. Que remarquez-vous ?II - La norme IEEE 754 (format simple) impose aux onstru teurs d'ordinateurs que b = 2,

p = 24, emin = −126 et emax = 127. Quel est le plus petit entier positif représentable ? Leplus grand positif ?Dans toute la suite de la se tion, on supposera b = 10 et p = 35.2 Erreur sur la représentationOn représente de façon interne un réel z par le nombre �ottant le plus pro he (notons-leR(z)). L'erreur relative ommise par ette représentation est

ER(z) =| z − R(z) |

z,que l'on peut exprimer en pour entage en multipliant par 100.III - Quelle est l'erreur relative ommise en représentant π = 3, 141592 · · · par le �ottant

3, 14 × 100 ?5.3 Soustra tionOn se pose le problème de al uler x− y. On supposera toujours que y < x et que x ety sont positifs.IV - Une première façon de faire est la suivante : on aligne les virgules de x et de y, onfait la soustra tion, et on prend le �ottant le plus pro he du résultat. Par exemple, si

x = 3, 14 × 108 et y = 2, 05 × 10−6,l'alignement et l'opération donneront3 , 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ×108

− 0 , 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 5 ×108

3 , 1 3 9 9 9 9 9 9 9 9 9 9 9 7 9 5 ×108représenté par le �ottant x = 3, 14 × 108. Le résultat est le plus exa t possible, mais etteméthode n'est jamais utilisée. Pouvez-vous voir pourquoi ?V - Plut�t qu'aligner y exa tement, on ne garde que p hi�res. Sur l'exemple pré édent, ela donne3 , 1 4 ×108

− 0 , 0 0 ×108

3 , 1 4 ×108

5 REPRÉSENTATION DES RÉELS (TD) 28E�e tuer l'opération pour x = 1 et y = 0, 999. Cal uler l'erreur relative sur le résultat.Qu'en pensez-vous ? Montrer que l'erreur relative peut être aussi grande que b−1 (et don ,elle peut être de 100 % si b = 2, et de 900 % si b = 10 !).VI - Supposons que l'on garde de façon interne un hi�re ( a hé à l'utilisateur) supplémen-taire. Refaire l'opération, et al uler l'erreur relative sur le résultat. Que onstatez-vous ?5.4 ArrondiAve le hi�re a hé, né essaire pour borner l'erreur relative ommise lors d'une sous-tra tion, se pose le problème d'arrondir un nombre (en l'o urren e la mantisse). La mé-thode lassique est d'arrondir inférieurement quand le hi�re a hé est dans l'ensemble{0, 1, 2, 3, 4}, et supérieurement quand le hi�re a hé est dans {5, 6, 7, 8, 9}. Ainsi 1, 452s'arrondit à 1, 45, tandis que 2, 088 s'arrondit à 2, 09 et que 3, 145 s'arrondit à 3, 15.Une autre façon de faire est la suivante : si le hi�re a hé est di�érent de 5, onfait omme la méthode pré édente. Ainsi, omme pré édemment, 1, 452 s'arrondit à 1, 45et 2, 088 s'arrondit à 2, 09. Cependant, quand le dernier hi�re est 5, au lieu d'arrondirsupérieurement de façon systématique, on arrondit au hi�re pair le plus pro he (méthodedite du tie breaks even). Ainsi 3, 145 s'arrondit à 3, 14, et 5, 255 s'arrondit à 5, 26.Pour départager obje tivement les deux méthodes d'arrondi, al uler les premiers termesdes deux suites (un)n≥0 et (vn)n≥0 dé�nies par

u0 = x, un = (un−1 − y) + y

v0 = x, vn = (vn−1 − y) + yoù x = 1 et y = 0, 055. Les opérations se font de façon exa te, ave arrondi à la suite de haque opération, et arrondi étant lassique pour u, et en utilisant le tie breaks evenpour v. Que onstatez-vous ? Si vous étiez banquier, quelle méthode hoisiriez-vous ?

6 ADDITIONS 296 AdditionsIl existe ertainement une foultitude d'algorithmes d'addition. Nous allons en voir deux,l'algorithme lassique tel qu'il est enseigné à l'é ole élémentaire, et l'algorithme d'Avizienis,basé sur la représentation des entiers dans les systèmes d'Avizienis.Le problème résolu par ha un des deux algorithmes est le suivant : obtenir la repré-sentation en base b de la somme de deux entiers x et y, en utilisant leurs représentations enbase b (dont nous supposerons qu'elles omportent ha une k + 1 hi�res). Les opérationsde bases, ou élémentaires, 'est-à-dire elles que l'on suppose onnues du pro esseur quiexé utera l'algorithme, sont les suivantes :� omparaisons entre entiers,� addition de deux hi�res en base b, le résultat étant un entier é rit en base b (lesfameuses tables d'addition),� soustra tion de b.6.1 Algorithme � lassique �Soient don à additionner deux entiers x et y, ave x =

k∑

i=0

xi.bi ; y =

k∑

i=0

yi.biTout le monde est ensé onnaître l'algorithme, qui onsiste à ajouter les hi�res de mêmepoids, des poids faibles vers les poids forts, en propageant éventuellement une � retenue �vers le rang suivant lorsque la somme des deux hi�res dépasse la base de la représentation.Nous allons l'étudier en détail, d'abord pour le justi�er, ensuite pour se familiariser ave une présentation que nous utiliserons dans les se tions suivantes.On dé�nit les suites (ri)i=0,...,k+1 et (ci)i=0,...,k+1 (r pour retenue et c pour hi�re) par

r0 = 0, et pour i ∈ {0, . . . , k}, ri+1 =

{0 si xi + yi + ri < b1 si xi + yi + ri ≥ b(la première retenue est nulle, et la retenue au rang i + 1 vaut 0 ou 1 selon que l'additionau rang i est inférieure ou égale à la base). Pour les hi�res : le hi�re de poids fort dela somme est égal à la dernière retenue, et les autres hi�res de la somme sont obtenusen ajoutant les hi�res orrespondant des nombres x et y et la retenue, et en enlevant bsi le total dépasse b. Plus mathématiquement : si 0 ≤ i ≤ k, ci = xi + yi + ri − b.ri+1 et

ck+1 = rk+1. On a alorsx + y = s =

k+1∑

i=0

ci.bi (1)Justi�er et algorithme va se faire en deux étapes : d'abord montrer que les ci sont biendes hi�res en base b, 'est-à-dire que, pour tout i ∈ {0, . . . , k+1}, ci ∈ {0, . . . , b−1}, en�nmontrer que l'égalité (1) est véri�ée.Commençons par montrer que pour tout i ∈ {0, . . . , k + 1}, ci ∈ {0, . . . , b − 1} : toutd'abord, on a par dé�nition ck+1 = rk+1, e qui montre que ck+1 ∈ {0, 1} ⊆ {0, . . . , b− 1}.Soit maintenant i ∈ {0, . . . , k}. On doit montrer que ci ∈ {0, . . . , b − 1}, 'est-à-dire que

0 ≤ ci ≤ b − 1. Deux as se présentent, selon la valeur de ri+1 :1. ri+1 = 0 : alors ci = xi + yi + ri, et don , puisque ri+1 = 0, ci ≤ b − 1. Par ailleurs, omme par hypothèse 0 ≤ xi, 0 ≤ yi et 0 ≤ ri, on a aussi 0 ≤ ci, en additionnant es3 inégalités membre à membre.

6 ADDITIONS 302. ri+1 = 1 : alors ci = xi+yi+ri−b. Si ri+1 = 1, 'est que, par dé�nition, xi+yi+ri ≥ b,et don 0 ≤ ci. Par ailleurs, on a xi ≤ b − 1, yi ≤ b − 1 et ri ≤ 1, don ci = xi + yi + ri − b (par dé�nition de ci)

≤ b − 1 + b − 1 + 1 − b (en utilisant les majorations i-dessus)= b − 1Montrons maintenant l'égalité (1) :

s =k+1∑

i=0

ci.bi (par dé�nition)

= rk+1.bk+1 +

k∑

i=0

ci.bi (par dé�nition de ck+1)

= rk+1.bk+1 +

k∑

i=0

(xi + yi + ri − b.ri+1).bi (par dé�nition de ci)

=

k∑

i=0

xi.bi +

k∑

i=0

yi.bi + rk+1.b

k+1 +

k∑

i=0

ri.bi −

k∑

i=0

ri+1.bi+1

= x + y +k+1∑

i=1

ri.bi −

k+1∑

i=1

ri.bi ( ar r0 = 0)

= x + yNous allons maintenant nous intéresser au oût de et algorithme, 'est-à-dire au nombred'opérations élémentaires à exé uter pour additionner deux entiers de k+1 hi�res en baseb. Commençons par le al ul des retenues : le al ul de r0 ne nous oûte rien, et, d'aprèsla dé�nition, le al ul de ri+1, pour i ∈ {0, . . . , k}, nous oûte deux additions de hi�resen base b plus un test, 'est-à-dire 3 opérations élémentaires. En tout, le al ul de toutesles retenues prend 3(k + 1) opérations élémentaires.En e qui on erne les hi�res : le al ul de ck+1 ne nous oûte rien (puisqu'il est égal àrk+1, déjà al ulé). Pour i ∈ {0, . . . , k}, on n'a, au pire, qu'une seule soustra tion, puisquela somme xi + yi + ri a déjà été al ulée pour ri+1. En tout, le al ul de tous les hi�resnous oûte k + 1 opérations, au pire. Résumons :Théorème 6.1 L'algorithme d'addition lassique e�e tue au plus 4k opérations élémen-taires pour additionner deux entiers de k hi�res.6.2 Algorithme d'AvizienisLa représentation d'Avizienis permet d'utiliser un algorithme d'addition très rapide,puisqu'il peut être exé uté en parallèle sur les hi�res des opérandes. Le temps pris pouradditionner deux nombres ne dépend don pas de leurs tailles, il est onstant. C'est ettepropriété qui rend ette représentation intéressante, et e�e tivement utilisée dans ertains opro esseurs dits �mathématiques�.Soit b > 1 la base de la représentation,

{−a, . . . , 0, . . . , a}

6 ADDITIONS 31l'ensemble des hi�res, ave a ≤ b − 1 et b + 1 ≤ 2.a. On veut additionner x et y, ave x =

k∑

i=0

xi.bi ; y =

k∑

i=0

yi.biOn dé�nit les suites (ri)i=0,...,k+1 et (ci)i=0,...,k+1 (r pour retenue et c pour hi�re) par

r0 = 0, et pour i ∈ {0, . . . , k}, ri+1 =

1 si xi + yi < −a + 10 si −a + 1 ≤ xi + yi ≤ a − 11 si xi + yi > a − 1Pour les hi�res : si 0 ≤ i ≤ k, ci = xi + yi − b.ri+1 et ck+1 = 0. On dé�nit en�n lasuite (si)i=0,...,k+1 (ave s pour somme) par si = ci + ri. On a alors (la preuve est dans lethéorème i-dessous)

x + y = s =k+1∑

i=0

si.biJusti�ons au passage l'allégation du début de la se tion, selon laquelle on peut al uler enparallèle la somme x + y : on a

si = ci + ri = xi + yi − b.ri+1 + riet ri est déterminé par les valeurs de xi−1 et de yi−1. Don , pour al uler si, il su�t de onnaître xi, yi, xi−1 et yi−1.Exemple et disposition pratique des al uls : posons b = 10, a = 9, x = 397, y = 418et don , puisqu'il y a 3 hi�res, k = 2. L'addition s'é rit omme suit :Indi e 3 2 1 0

xi 3 9 7

yi 4 1 8

ri 0 0 1 0

ci 0 1 8 5

si 0 1 9 5soit x + y = 195. Véri�ons : x = 397 = 300 − 97 = 203, y = 418 = −400 + 10 − 8 = −398et x + y = 203 − 398 = −195. Sur et exemple, le résultat est orre t. . . On a en fait lerésultat suivant :Théorème 6.2 Ave les notations pré édentes :1. ∀i ∈ {0, . . . , k + 1}, si ∈ {−a, . . . , a} ;2. s =k+1∑

i=0

si.bi = x + yPreuve :1. On a ck+1 = 0 par dé�nition, et rk+1 ∈ {−1, 0, 1} don sk+1 ∈ {−1, 0, 1} ⊆

{−a, . . . , a} ; pour i ∈ {0, . . . , k}, si = ci + ri ave ri ∈ {−1, 0, 1} : il su�t don de montrer que ci ∈ {−a + 1, . . . , a − 1}, 'est-à-dire que −a + 1 ≤ ci ≤ a− 1. Il y atrois possibilités, selon la valeur de ri+1 :

6 ADDITIONS 32(a) ri+1 = 1 : montrons tout d'abord que ci ≤ a − 1. Si ri+1 = 1, 'est que, pardé�nition de ri+1, xi +yi < −a+1, d'où l'on déduit ci = xi +yi+b < −a+1+b.Comme, par hypothèse, b + 1 ≤ 2a, on a −a + 1 + b ≤ −a + 2a = a, et partransitivité, ci < a 'est-à-dire ci ≤ a − 1.Montrons maintenant que −a + 1 ≤ ci. Les assertions −a ≤ xi, −a ≤ yi etci = xi + yi + b entraînent l'inégalité −2a+ b ≤ ci. Comme a ≤ b− 1, on a aussia + 1 ≤ b, et on peut minorer la quantité −2a + b par −2a + a + 1 = −a + 1, e qui implique par transitivité que −a + 1 ≤ ci.(b) ri+1 = 0 : 'est que, par dé�nition de ri+1, −a+1 ≤ xi + yi ≤ a− 1. Le résultatdé oule de e que, par dé�nition, ci = xi+yi−b.ri+1, et de l'hypothèse ri+1 = 0.( ) ri+1 = 1 : la preuve est similaire au as où ri+1 = 1, elle est don laissée enexer i e au le teur.2.

s =

k+1∑

i=0

si.bi

=

k+1∑

i=0

(ci + ri).bi par dé�nition de si

=k+1∑

i=0

ci.bi +

k+1∑

i=0

ri.bi

=k∑

i=0

ci.bi +

k+1∑

i=1

ri.bi ar ck+1 = 0 et r0 = 0

=

k∑

i=0

(xi + yi − b.ri+1).bi +

k+1∑

i=1

ri.bi par dé�nition de ci

=

k∑

i=0

xi.bi +

k∑

i=0

yi.bi −

k∑

i=0

ri+1.bi+1 +

k+1∑

i=1

ri.bi

= x + y −k+1∑

i=1

ri.bi +

k+1∑

i=1

ri.bi

= x + y

�Exer i es de la partie 66.1 - Programmer l'algorithme lassique d'addition ave un tableur.6.2 - E�e tuer les additions suivantes (b désigne la base, a désigne le plus grand hi�repositif) :� b = 10, a = 9 : 2541 + 9878� b = 10, a = 6 : 2541 + 5665� b = 10, a = 9 : 2541 + 5665� b = 10, a = 7 : 1643 + 6542� b = 4, a = 3 : 23313 + 3203� b = 16, a = 9 : 6879 + 8658

6 ADDITIONS 33� b = 16, a = F : 6879 + 86586.3 - Cal uler le oût, en nombre d'opérations élémentaires, de l'algorithme d'Avizienis.6.4 - Programmer l'algorithme d'Avizienis ave un tableur.6.5 - Donner un algorithme d'addition pour la � base � de Fibona i.6.6 - Donner un algorithme d'addition pour la base −2.

7 MULTIPLICATIONS 347 Multipli ationsPour la multipli ation, il existe aussi de multiples algorithmes. Nous allons en voirdeux, l'algorithme lassique enseigné à l'é ole élémentaire, et un algorithme dont l'origine,lointaine, est ontroversée : ertains prétendent qu'il nous vient de l'antiquité égyptienne,d'autres prétendent qu'il a été inventé (ré-inventé ?) et utilisé dans les grandes plainesrusses ( es deux expli ations ne sont pas ontradi toires : l'algorithme a pu être dé ouvertune première fois dans l'antiquité, oublié, puis retrouvé).L'� avantage � du deuxième algorithme sur le premier est qu'il né essite très peu de onnaissan es arithmétiques pour être exé uté : savoir additionner deux nombres, multiplierpar deux ( e qui revient à une addition), diviser par deux, savoir re onnaître un nombrepair. Ces deux dernières ompéten es ne semblent pas très di� iles à a quérir, surtoutquand la base de représentation des nombres utilisée est paire, e qui, à ma onnaissan e,a toujours été le as dans l'histoire.Le adre est le même que pour l'addition : on a deux nombres x et y de k + 1 hi�resé rits en base b, et on her he leur produit, é rit lui aussi en base b. Les opérations de basesne sont pas les mêmes pour les deux algorithmes, nous les pré iserons dans haque as.7.1 L'algorithme � lassique �Les opérations de bases sont i i� la multipli ation de deux hi�res en base b, le résultat étant un entier é rit en baseb ( e qu'on appelle les tables de multipli ation),� l'addition de deux entiers,� la division eu lidienne par b d'un nombre é rit en base b,� et la multipli ation par bk (pour k ≥ 0), e qu'on appelle le dé alage arithmétique.Soient don deux entiers x et y é rits en base b à multiplier, ave

x =k∑

i=0

xi.bi , y =

k∑

i=0

yi.biOn peut é rire

x.y = x.

(k∑

i=0

yi.bi

)

=

k∑

i=0

x.yi.biet le problème de multiplier x et y revient à elui de multiplier un entier par un hi�re enbase b, puisque, par hypothèse, nous savons additionner deux entiers é rits en base b, etmultiplier par bi.Nous allons don résoudre le problème suivant : étant donnés un nombre, x, de k + 1 hi�res en base b, et un hi�re, f , de la base b, donner la représentation en base b de leurproduit. À et e�et, on dé�nit, omme d'habitude, deux suites, (ri)i=0,...,k+1 et (ci)i=0,...,k+1(r pour retenue et c pour hi�re), de la façon suivante :

r0 = 0 et, pour i ∈ {0, . . . , k}, ri+1 = (xi.f + ri) div bck+1 = rk+1 et, pour i ∈ {0, . . . , k}, ci = xi.f + ri − b.ri+1On a alors (les preuves sont laissées en exer i e)

∀i ∈ {0, . . . , k + 1}, ci ∈ {0, . . . , b − 1} (2)x.f =

k+1∑

i=0

ci.bi (3)

7 MULTIPLICATIONS 357.2 La multipli ation des paysans russes (TD)Le adre est le même que pré édemment : soient à multiplier deux entiers x et y, é ritsen base b. Les opérations de bases sont i i� additionner deux entiers ;� multiplier par 2 ;� diviser par 2 (en fait trouver le quotient de la division eu lidienne par 2) ;� déterminer si un entier est pair.On dé�nit les suites (xi)i≥0, (yi)i≥0 et (zi)i≥0 omme suit :{

x0 = x

xn+1 =⌊xn

2

⌋

{y0 = yyn+1 = 2.yn

z0 = 0

zn+1 =

[zn + yn si xn est impairzn sinon7.1 - Faire tourner l'algorithme ave x = 13 et y = 7. Que onstatez-vous sur la suite

(xi)i≥0 ? Et sur la suite (zi)i≥0 ?7.2 - Montrer que la suite (xi)i≥0 est stationnaire à partir d'un ertain rang (noté n0 dansla suite). Quelle est sa limite ? Montrer que zn0= x × y (indi ation : onsidérerl'é riture de x en base 2).7.3 - E�e tuer, en utilisant et algorithme, les opérations suivantes :153 x 26 52 x 74 1542 x 43Exer i es de la partie 77.1 - Montrer que la multipli ation d'un entier de k hi�res (en base b) par un hi�re dela base b produit un entier ayant au plus k + 1 hi�res en base b.7.2 - Prouver l'algorithme lassique de multipli ation.7.3 - Combien d'opérations élémentaires l'algorithme lassique e�e tue-t-il pour multiplierdes entiers de k hi�res ?7.4 - Programmer et algorithme ave un tableur.7.5 - (Problème issu de Jeux & Stratégies, no 43, Février-Mars 1987 ) Trouver le hi�redésigné par un � ? � dans l'opération i-dessous, e�e tuée en base 10 (au un nombrene ommen e par 0) :

. . .× 7 .

. . 1 .8 . .

. . . ?7.6 - Combien d'opérations élémentaires l'algorithme des paysans russes e�e tue-t-il pourmultiplier des entiers de k hi�res ?7.7 - Programmer et algorithme ave un tableur.

7 MULTIPLICATIONS 367.8 - Comparer les deux algorithmes, en nombre d'opérations élémentaires. Examiner enparti ulier le as où b = 2.