Représentation des nombres

Algo & Prog avec R

Arnaud Malapert
28 septembre 2022
Université Côte d’Azur, CNRS, I3S, France
[email protected]
Cours en AUTOFORMATION

Représentation des nombres

I Système positionel : binaire, décimal, octal, et héxadécimal.
I Nombre non signé seulement (positif).
I Représentation en machine des entiers naturels seulement !

Prérequis
Savoir additionner, soustraire, multiplier, et diviser ! Surtout par 2 !

Évaluation : Gagner un max de points en peu de temps !

I 3 points du même QCM dans le contrôle terminal.
I Exercices de programmation autour des algorithmes de conversion.
I Activité de programmation d’une appli web de conversion.

1/32
Table des matières

1. Système positionnel
Entiers naturels
Nombres fractionnaires

2. Multiplication et division égyptiennes

3. Arithmétique binaire

4. Représentation des nombres en machine

2/32
Système positionnel
Représentation des nombres

On représente les nombres grâce à des symboles.

Représentation unaire : un symbole de valeur unique.

I I=1, II = 2, III = 3, Iet IIIIIIIII = 10.
I Le calcul est facile.
I I + III = IIII ;
I II × III = II II II = IIIIII

I mais cela devient vite incompréhensible

Chiffres Romains : plusieurs symboles ayant des valeurs différentes.

I Le nombre de symboles est théoriquement infini.
I I=1, V=5, X = 10, L = 50 . . ..

I Le calcul est impossible.

3/32
Représentation des nombres

Système positionnel : symboles dont la valeur dépend de la position

I 999 = 900 + 90 + 9
I À Babylone, système sexagésimal (60) (IIe millénaire av J-C).
I Transmission de l’orient vers l’occident avec le zéro (env.
825 ap. J-C) 1

Un brin de cynisme
Les hommes sont comme les chiffres, ils n’acquièrent de la valeur
que par leur position.
Napoléon Bonaparte

1. « Al-jabr wa’l-muqâbalah » Muhammad ibn Müsä al-Khuwärizmï

4/32
Système positionnel

Utilisation d’une base b

I Les nombres sont représentés à l’aide de b symboles distincts.
I La valeur d’un chiffre dépend de la base.

Un nombre x est représenté par une suite de symboles :

x = an an−1 . . . a1 a0 .

Décimale (b = 10), ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Binaire (b = 2), ai ∈ {0, 1}
Hexadécimale (b = 16), ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F }
√
5−1
Les bases les plus utilisées sont : 10, 2, 3, 2k , 12, 16, 60, 2 ...
Notation
(x )b indique que le nombre x est écrit en base b.
5/32
Système positionnel

Entiers naturels
Représentation des entiers naturels

En base b
n
X
x = an an−1 . . . a1 a0 = ai b i
i=0

I a0 est le chiffre de poids faible,

I an est le chiffre de poids fort.

En base 10
(1998)10 = 1 × 103 + 9 × 102 + 9 × 101 + 8 × 100 .

En base 2

(101)2 = 1 × 22 + 0 × 21 + 1 × 20
= 4 + 0 + 1 = 5.

6/32
Traduction vers la base 10

Méthode simple
I On applique simplement la formule.
I Cela revient donc à une simple somme.
I En pratique, on peut utiliser la multiplication égyptienne.

Schéma de Horner
I Méthode générale pour calculer l’image d’un polynôme en un point.
I Moins d’opérations que la méthode simple.
I Plus efficace pour une machine, pas nécessairement pour un humain.

7/32
Schéma de Horner

Une reformulation judicieuse de l’écriture en base b

n
X
an an−1 . . . a1 a0 = ai b i
i=0

= ((. . . ((an b + an−1 )b + an−2 ) . . .)b + a1 )b + a0

Algorithme simple et efficace

I Initialiser l’accumulateur : v = 0.
I Pour chaque chiffre ai en partant de la gauche : v ← (v × b) + ai .

8/32
Schéma de Horner

Algorithme simple et efficace

I Initialiser l’accumulateur : v = 0.
I Pour chaque chiffre ai en partant de la gauche : v ← (v × b) + ai .

(10110)2 = (22)10 (12021)3 = (142)10

ai v Calcul de v ai v Calcul de v
1 1 2×0+1 1 1 3×0+1
0 2 2×1+0 2 5 3×1+2
1 5 2×2+1 0 15 3×5+0
1 11 2 × 5 + 1 2 47 3 × 15 + 2
0 22 2 × 11 + 0 1 142 3 × 47 + 1

8/32
Traduction entre des puissances de 2

Du binaire vers une base 2k

Regrouper les bits par k en partant de la droite et les traduire.
D’une base 2k vers le binaire
Traduire chacun des symboles en un nombre binaire.
Du binaire vers l’héxadécimal (24 )
Regrouper les bits par 4 en partant de la droite.
(00)10 0101 1110 0001 1101 1111
2 5 E 1 D F
Du binaire vers l’octal (23 )
Regrouper les bits par 3 en partant de la droite.
(00)1 001 011 110 000 111 011 111
1 1 3 6 0 7 3 7
D’une base 2k vers une base 2p
1. Passer par le binaire : (x )2k → (x )2 → (x )2p .
2. Généraliser la méthode précédente si k est un diviseur/multiple de p.
3. Appliquer un algorithme de traduction vers une base quelquonque. 9/32
Traduction vers une base quelquonque

Nombre entier
On procède par divisions euclidiennes successives :

I On divise le nombre par la base,

I puis le quotient par la base,
I ainsi de suite jusqu’à obtenir un quotient nul.

La suite des restes obtenus correspond aux chiffres de a0 à an dans la

base visée.

(44)10 = (101100)2 (44)10 = (1122)3

44 = 22 × 2 + 0 a0 =0 44 = 14 × 3 + 2 a0 =2
22 = 11 × 2 + 0 a1 =0 14 = 4 × 3 + 2 a1 =2
11 = 5 × 2 + 1 a2 =1 4 = 1×3+1 a2 =1
5 = 2×2+1 a3 =1 1 = 0×3+1 a3 =1
2 = 1×2+0 a4 =0
1 = 0×2+1 a5 =1 10/32
Traduction depuis une base quelquonque

Il faut diviser dans la base d’origine.

Les calculs sont donc difficiles pour un humain !

(101100)2 = (1122)3
101100 = 1110 × 11 + 10 a0 =2
1110 = 100 × 11 + 10 a1 =2
100 = 1 × 11 + 1 a2 =1
1 = 0 × 11 + 1 a3 =1
Passez par le décimal !
(x )b → (x )10 → (x )b 0 .

11/32
Exercices

I Traduire (10101)2 en écriture décimale.

I Traduire (10101101)2 en écriture décimale.
I Traduire (10101001110101101)2 en écriture hexadécimale.
I Traduire (1AE 3F )16 en écriture binaire.
I Traduire (1AE 3F )16 en écriture octal.
I Traduire (927)10 en écriture binaire.
I Traduire (1316)10 en écriture binaire.

12/32
Système positionnel

Nombres fractionnaires
Représentation des nombres fractionnaires

En base b
La formule est la même, mais il existe des exposants négatifs.
n
X
x = an an−1 . . . a1 a0 , a−1 a−2 . . . a−k = ai b i
i=−k

En base 10
19.98 = 1 × 101 + 9 × 100 + 9 × 10−1 + 8 × 10−2 .

En base 2

(101, 01)2 = 1 × 22 + 0 × 21 + 1 × 20 + 0 × 2−1 + 1 × 2−2

= 4 + 0 + 1 + 0 + 0.25 = 5, 25.

13/32
Traduction vers une base quelquonque

Nombre fractionnaire
I On décompose le nombre en partie entière et fractionnaire si x > 0 :

x = E [x ] + F [x ].

I On convertit la partie entière par la méthode précédente :

E [x ] = an an−1 . . . a1 a0 .

I On convertit la partie fractionnaire :

F [x ] = 0, a−1 a−2 . . . a−m .

I Finalement, on additionne la partie entière et fractionnaire :

x = an an−1 . . . a1 a0 , a−1 a−2 . . . a−m . . . .

14/32
Traduction vers une base quelquonque

Partie fractionnaire
I on multiplie F [x ] par b. Soit a−1 la partie entière de ce produit,
I on recommence avec la partie fractionnaire du produit pour obtenir
a−2 ,
I et ainsi de suite . . .
I on stoppe l’algorithme si la partie fractionnaire devient nulle.

(0, 734375)10 = (0, BC )16

0, 734375 × 16 = 11, 75 a−1 = B
0, 75 × 16 = 12 a−2 = C

15/32
Traduction de 0,3 en base 2

(0, 3)10 = (0, 01001100110011 . . .)2

0, 3 × 2 = 0, 6 a−1 = 0
0, 6 × 2 = 1, 2 a−2 = 1
0, 2 × 2 = 0, 4 a−3 = 0
0, 4 × 2 = 0, 8 a−4 = 0
0, 8 × 2 = 1, 6 a−5 = 1
0, 6 × 2 = 1, 2 a−6 = 1
0, 2 × 2 = 0, 4 a−7 = 0
La conversion d’un nombre fractionnaire ne s’arrête pas toujours.
I En base b, on ne peut représenter exactement que des nombres
fractionnaires de la forme X /b k
I La conversion d’un nombre entier s’arrête toujours.

Il faudra arrondir . . .

16/32
Exercices

I Traduire (10101101)2 en écriture décimale.

I Traduire (10101001110101101)2 en écriture hexadécimale.
I Traduire (1AE 3F )16 en écriture décimale.
I Traduire (1AE 3F )16 en écriture binaire.
I Traduire (13.1)10 en écriture binaire.

17/32
Multiplication et division
égyptiennes
Multiplication égyptienne

Principe
I Décomposition d’un des nombres en une somme.
On décompose généralement le plus petit.
I Création d’une table de puissance pour l’autre nombre
I Très souvent, traduction du décimal vers le binaire.
Il existe des variantes en fonction de la complexité de l’opération.
I Il suffit de savoir multiplier par deux et additionner !

18/32
Multiplication égyptienne : x × y

I On construit la ligne i + 1 en multipliant par deux 2i et x × 2i tant

que 2i+1 < y .

189 × 21 = 3969
i ai 2i 189 × 2i
0 1 189
1 2 378
2 4 756
3 8 1512
4 16 3024

19/32
Multiplication égyptienne : x × y

I On construit la ligne i + 1 en multipliant par deux 2i et x × 2i tant

que 2i+1 < y .
I On traduit 21 en binaire en remontant dans le tableau.
I On calcule n0 ai (x × 2i ).
P

189 × 21 = 3969
i ai 2i 189 × 2i
0 1 1 189 X (1 -1 = 0)
1 0 2 378
2 1 4 756 X (5 -4 = 1)
3 0 8 1512
4 1 16 3024 X (21 -16 = 5)
3969

19/32
Méthode genérale

Des opérations plus complexes faisant intervenir par exemple des

fractions exigeaient une décomposition avec :
I les puissances de deux,
I les fractions fondamentales,
I les dizaines.

La technique est rigoureusement la même mais offre plus de liberté au

scribe quant à la décomposition du petit nombre.

1 7 1
243 × 27 = 6561 Papyrus Rhind : 14 × 4 = 8
1 243 1
1 14
2 486 1 1
2 28
4 972 1 1
20 4860 4 56
7 1
27 6561 4 8 ( 4+2+1
56 )

20/32
Division égyptienne : x ÷ y

Par quoi doit-on multiplier y pour trouver x ?

I On construit la ligne i + 1 en multipliant par deux 2i et y × 2i tant
que y × 2i+1 < x .

539 ÷ 7 = 77
i 2i 7 × 2i
0 1 7
1 2 14
2 4 28
3 8 56
4 16 112
5 32 224
6 64 448
21/32
Division égyptienne : x ÷ y

Par quoi doit-on multiplier y pour trouver x ?

I On construit la ligne i + 1 en multipliant par deux 2i et y × 2i tant
que y × 2i+1 < x .
I On décompose x par les y × 2i en remontant dans le tableau.
I On calcule la somme des 2i de la décomposition.

539 ÷ 7 = 77
i 2i 7 × 2i
0 1 7 X (7 − 7 = 0)
1 2 14
2 4 28 X (35 − 28 = 7)
3 8 56 X (91 − 56 = 35)
4 16 112
5 32 224
6 64 448 X (539 − 448 = 91)
77
21/32
Division dont le résultat est fractionnaire

234 ÷ 12 = 19.5
i 2i 12 × 2i

0 1 12
1 2 24
2 4 48
3 8 96
4 16 192

22/32
Division dont le résultat est fractionnaire

234 ÷ 12 = 19.5
i 2i 12 × 2i

0 1 12 X (6)
1 2 24 X (18)
2 4 48
3 8 96
4 16 192 X (42)

22/32
Division dont le résultat est fractionnaire

234 ÷ 12 = 19.5
i 2i 12 × 2i
1
-1 2 6 X (0)
0 1 12 X (6)
1 2 24 X (18)
2 4 48
3 8 96
4 16 192 X (42)
19.5

22/32
Exercices

1. Multipliez 187 par 11.

2. Multipliez 2012 par 1515 (indice : utilisez la méthode genérale).

23/32
Exercices

1. Multipliez 187 par 11.

2. Multipliez 2012 par 1515 (indice : utilisez la méthode genérale).

187 × 11 2012 × 1515

i ai 2i 11 × 2i 5 10060
0 1 1 187 10 20120
1 1 2 374 500 1006000
2 0 4 748 1000 2012000
3 1 8 1496 1515 3048180
11 2057

23/32
Arithmétique binaire
Représentation de l’information en machine

I Informations en général représentées et manipulées sous forme

binaire.
I L’unité d’information est le chiffre binaire ou bit (binary digit).
I Les opérations arithmétiques de base sont faciles à exprimer en
base 2.
I La représentation binaire est facile à réaliser : systèmes à deux états
obtenus à l’aide de transistors.

24/32
Addition binaire

Tables d’addition
I 0+0=0
I 1+0=1
I 0+1=1
I 1 + 1 = 10 (0 et on retient 1)

91 + 71 = 162
1 1 1 1 1 1
1011011
+1000111
1 0100010

25/32
Soustraction binaire

Tables de soustraction
I 0−0=0
I 1−0=1
I (1)0 − 1 = 1 (1 et on retient 1)
I 1−1=0

83 − 79 = 4
1 1
1010011
-1001111
1 1

0000100
Limitation : résultat négatif
On ne peut traiter x − y que si x ≥ y .

26/32
Multiplication binaire

Tables de multiplication
I 0×0=0
I 1×0=0
I 1×1=1

23 × 11 = 253
10111
× 1011
1 1 1 1 1
10111
+ 10111
+10111
11111101

27/32
Division binaire

Soustractions et décalages comme la division décimale

I sauf que les digits du quotient ne peuvent être que 1 ou 0.
I Le bit du quotient est 1 si on peut soustraire le diviseur, sinon il
est 0.

231 ÷ 11 = 21
1 1 1 0 0111 1011
−1 0 1 1 10101
1 1 01
−1 0 11
1011
−1011
0
Limitation : division entière
Pour l’instant, on ne peut pas calculer la partie fractionnaire.
28/32
Exercices

1. Traduire (1100101)2 et (10101111)2 en écriture décimale.

2. Calculez la somme (1100101)2 + (10101111)2 .
3. Calculez le produit (10101111)2 × (1100101).
4. Calculez la soustraction (10101111)2 − (1100101)2 .
5. Vérifier tous les résultat en les traduisant en écriture décimale.

29/32
Représentation des nombres en
machine
Représentation des nombres en machine

Précision finie
I Codés généralement sur 16, 32 ou 64 bits.
I Un codage sur n bits permet de représenter 2n valeurs distinctes.

Un ordinateur ne calcule pas bien !

I Pour un ordinateur, le nombre de chiffres est fixé.
I Pour un mathématicien, le nombre de chiffres dépend de la valeur
représentée.
I Lorsque le résultat d’un calcul doit être représenté sur plus de
chiffres que ceux disponibles, il y a dépassement de capacité.

30/32
Représentation des entiers en machine

Entiers naturels
I Un codage sur n bits : tous les entiers entre 0 et 2n − 1.
I La conversion d’un nombre entier s’arrête toujours.
I On ne peut traiter x − y que si x ≥ y .

Entiers relatifs : plusieurs représentations existent.

Valeur absolue signée ; complément à 1 ; complément à 2.

Tous les processeurs actuels utilisent le complément à 2.

I il y a un seul code pour 0 ;
I l’addition de deux nombres se fait en additionnant leurs codes ;
I et il est très simple d’obtenir l’opposé d’un nombre.
I les processeurs disposent de fonctions spéciales pour l’implémenter.

31/32
Représentation des nombres réels

I Les ressources d’un ordinateur étant limitées, on représente

seulement un sous-ensemble F ⊂ R de cardinal fini.
I Les éléments de F sont appelés nombres à virgule flottante.
I Les propriétés de F sont différentes de celles de R.
I Généralement, un nombre réel x est tronqué par la machine,
définissant ainsi un nouveau nombre fl(x ) qui ne coïncide pas
forcément avec le nombre x original.
Problèmes et limitations
I les calculs sont nécessairement arrondis.
I il y a des erreurs d’arrondi et de précision
I On ne peut plus faire les opérations de façon transparente

> 0.1 + 0.1 + 0.1 == 0.3

[1] FALSE
> 10^20 + 1 = = 10^20
[1] TRUE
32/32
 Questions?

Retrouvez ce cours sur le site web

www.i3s.unice.fr/~malapert/R

32/32