ELEMENTS SIMPSON (VII)
NUMÉRATION EN BASE b
Examinons quelques entiers naturels : 3; 47; 265; 1987; 21005
Sans le crier sur les toits, ils sont écrits en base 10, c'est-à-dire qu'ils sont codés conventionnellement comme sommes de puissances de 10.
On sait la convention : 100 = 1 (valable pour tout entier b non nul : b0 = 1)
On sait : 101 = 10; 102 = 10x10 = 100; 103 = 10x10x10 = 1000; etc.
On peut alors remarquer que :
3 = 3x100
47 = 4 x 101 + 7 x 100
265 = 2 x 102 + 6 x 101 + 5 x 100
1987 = 1 x 103 + 9 x 102 + 8 x 101 + 7 x 100
21005 = 2 x 104 + 1 x 103 + 0 x 102 + 0 x 101 + 5 x 100
etc.
Il me semble que le codage s'installe assez clairement tout seul.
Ainsi, le nombre entier M, avec :
M = C x 105 + D x 104 + E x 103 + F x 102 + G x 101+H x 100
Et : 0<C<10 ; 0≤ { D,E,F,G,H} <10
S'écrit, en base 10 : CDEFGH
Que représentent C,D,E,F,G,H pour M?
Ou : comment les obtient-on à partir de M?
Il suffit de procéder par divisions (euclidiennes) successives.
Rappel de la division euclidienne :
a et b étant deux entiers naturels quelconques, b étant différent de 0, il existe et d'une seule façon deux entiers naturels q et r tels que : a = bxq+r , avec 0≤r<b ; q est le quotient, r est le reste.
Dans l'égalité de la division euclidienne, a est le dividende et b est le diviseur.
Ainsi, ici, on commencera par diviser M par 10, obtenant : M = 10Q1 + H
Il suffit pour s'en persuader de remarquer que tel que donné ci-dessus:
M = 10(C x 104 + D x 103 + E x 102 + F x 101 + G) +H
Etc.
La division euclidienne de Q1 par 10 donnera: Q1 = 10Q2 + G
La division euclidienne de Q2 par 10 donnera : Q2 = 10Q3 + F
La division euclidienne de Q3 par 10 donnera : Q3 = 10Q4 + E
La division euclidienne de Q4 par 10 donnera : Q4 = 10Q5 + D
La division euclidienne de Q5 par 10 donnera : Q5 = 10x0 + C
C,D,E,F,G,H sont donc les restes successifs de divisions euclidiennes, poursuivies jusqu'à obtenir un quotient égal à 0: division de M par 10, puis du quotient par 10, puis du nouveau quotient par 10, etc.
CAS GÉNÉRAL, BASE b .
On peut sur le même principe, étant choisi un entier non nul b, essayer de le décomposer en combinaison de {1=b0, b=b1, b2, b3, b4, …..}.
Ainsi, le nombre entier M, avec :
M = C x b5 + D x b4 + E x b3 + F x b2 + G x b1+H x b0
Et : 0<C<b ; 0≤ { D,E,F,G,H} <b
S'écrit, en base b : CDEFGH
Comment obtient-on { C,D,E,F,G,H} à partir de M?
Il suffit de procéder par divisions (euclidiennes) successives comme pour la cas de la base 10. Le principe est exactement le même.
Ainsi, ici, on commencera par diviser M par b, obtenant : M = bQ1 + H
Il suffit pour s'en persuader de remarquer que tel que donné ci-dessus:
M = b(C x b4 + D x b3 + E x b2 + F x b1 + G) +H
Et donc : Q1 = C x b4 + D x b3 + E x b2 + F x b1 + G
Etc.
La division euclidienne de Q1 par b donnera: Q1 = bQ2 + G
La division euclidienne de Q2 par b donnera : Q2 = bQ3 + F
La division euclidienne de Q3 par b donnera : Q3 = bQ4 + E
La division euclidienne de Q4 par b donnera : Q4 = bQ5 + D
La division euclidienne de Q5 par b donnera : Q5 = bx0 + C
C,D,E,F,G,H sont donc les restes successifs de divisions euclidiennes, poursuivies jusqu'à obtenir un quotient égal à 0: division de M par b, puis du quotient par b, puis du nouveau quotient par b, etc.
Donnons un exemple.
Comment s'écrit en base 7, M qui s'écrit 1156 en base 10?
1156 = 7x165 + 1
165 = 7x23 + 4
23 = 7x3 + 2
3 = 7x0 + 3
Bilan, en base 7, M s'écrit : 3241
On pourrait noter, avec la base en indice terminal : 115610 = 32417
Autre exemple : toujours M mais en base 9 cette fois.
1156 = 9x128 + 4
128 = 9x14 + 2
14 = 9x1 + 5
1 = 9x0 + 1
Bilan : 115610 = 15249
Etc.
Ecriture en base 2 (binaire) .
Il est clair qu'en base, les restes calculés ne pourront être que 0 ou 1. Et donc, l'écriture en base 2 d'un nombre entier quelconque ne sera qu'une suite de 1 et de 0.
Ainsi :
1156 = 2x578 + 0
578 = 2 x 289 + 0
289 = 2 x 144 + 1
144 = 2 x 72 + 0
72 = 2 x 36 + 0
36 = 2 x 18 + 0
18 = 2 x 9 + 0
9 = 2 x 4 + 1
4 = 2 x 2 + 0
2 = 2 x 1 + 0
1 = 0 x 2 + 1 D'où finalement : 115610 = 100100001002
Ecriture en base 16 (Hexadécimale) .
On se heurte en base 16 au problème de la représentation des restes supérieurs ou égaux à 10 puisqu'ils peuvent prendre toute valeur de 0 à 15 et qu'on ne doit les coder que sur un seul symbole, naturellement un chiffre, de 0 à 9, mais après?
On tourne l'affaire avec une convention de codage allant chercher pour continuer les lettres de l'alphabet :
10=A; 11=B; 12=C; 13=D; 14=E; 15=F.
Essai avec 1156 :
1156 = 16x72 + 4
72 = 16x4 + 8
4 = 16x0 + 4 … et : 115610 = 48416
On n'a pas eu besoin de lettres. Mais, par exemple 4345810 ?
43458 = 16 x 2716 + 2
2716 = 16 x 169 + 12
169 = 16 x 10 + 9
10 = 16 x 0 + 10 … et : 4345810 = A9C216
La méthode de mise en place (l'algorithme) de l'écriture en base b telle que décrite se transpose facilement en programme pour calculatrice de type lycée (j'utilise une vieille TI 82).
Je reformalise l'algorithme en termes généraux. La traduction-machine se fera selon les modèles.
M, entier à transcrire (il sera saisi en base 10)
B, la base de numération retenue
L la liste des termes successifs de l'écriture de M en base b
Q, I, K entiers
Saisir M
Saisir B
Q reçoit M
I reçoit 1 (c'est un compteur; il rangera les restes successifs)
Tant que Q ≠ 0 Faire
Q reçoit Int(M/B)
L(I) reçoit M-BxQ (L(I) est le reste de la Iième division)
M reçoit Q
I reçoit I+1
Fin Tant que
I reçoit I-1 ( I a un cran de trop en sortie de boucle Tant que)
Pour K de I à 1, avec pas de -1, afficher L(K)
Fin Pour
On peut jouer à faire tourner tel quel le programme obtenu pour les bases de 2 à 9.
Les nombres étant donnés en base 10, on passe ... le programme fonctionne bien sûr et redonne ... la même écriture.
Il faut au-delà (B ≥11) , se donner les codes de notation pour les restes {10, …, B-1}. On a vu le cas de la numération hexadécimale. On peut vouloir généraliser. L'utilisation exhaustive de l'alphabet permet de traiter sur ce modèle les bases jusqu'à b=36. Mais il faut alors penser à introduire un répertoire des codes retenus. Ce n'est pas la mer à boire.
Contentons-nous de permettre à b les valeurs {11; 12; 13; 14; 15;16}
On introduit une liste P avec, de 1 à 10, P(i) = i-1, puis : P(11)=A, P(12)=B, P(13)=C, P(14)=D, P(15)=E, P(16)=F.
L'algorithme ci-dessus, deviendra:
M, entier à transcrire (il sera saisi en base 10)
B, la base de numération retenue
L la liste des termes successifs de l'écriture de M en base B
P la liste des codes
Q, I, K, R entiers
Saisir M
Saisir B
Q reçoit M
I reçoit 1 (c'est un compteur; il rangera les restes successifs)
Tant que Q ≠ 0 Faire
Q reçoit Int(M/B)
R reçoit M-BxQ (R est le reste de la Iième division)
L(I) reçoit P(R+1)
M reçoit Q
I reçoit I+1
Fin Tant que
I reçoit I-1 ( I a un cran de trop en sortie de boucle Tant que)
Pour K de I à 1, avec pas de -1, afficher L(K)
Fin Pour
On pourra s'amuser ainsi à contrôler rapidement, à l'aide du programme :
569810 = 212110013 = 422146 = 77319 = 336A12
/image%2F0404595%2F20240507%2Fob_ad8826_echec-scolaire-ok-0.jpg)
/image%2F0404595%2F20240312%2Fob_e012fa_niveau.png)
/https%3A%2F%2Fstorage.canalblog.com%2F85%2F76%2F87790%2F134452212_o.jpg)
/https%3A%2F%2Fstorage.canalblog.com%2F88%2F32%2F87790%2F134335726_o.png)