modif algo euclide

[cours-maths-dis.git] / arithmetique / representation.tex

\section{Introduction}


Pour des raisons évidentes, il est impossible de représenter exactement en machine un nombre réel dont le développement binaire, et a fortiori décimal, est infini.


\begin{Ex}
Par exemple 1/3, mais aussi 1/10 (dont le développement décimal 0,1 est fini, mais pas le développement binaire) ne sont pas exactement représentables.
\end{Ex}



Cette limitation interdit la représentation de tout nombre irrationnel, dont le dé\-ve\-lop\-pe\-ment est toujours infini et non périodique. On ne peut donc représenter que :
\begin{itemize}
\item des nombres rationnels,
\item et, parmi ceux-ci, seuls ceux qui admettent un développement binaire fini et \og pas trop long\fg{},
\end{itemize}
\noindent c'est-à-dire, au total, un nombre fini de nombres rationnels.\\



La représentation généralement adoptée est la représentation dite \og en virgule flottante\fg{}\index{représentation!en virgule flottante}, parce qu'elle permet de traiter de manière à peu près satisfaisante les opérations sur deux opérandes de grandeurs très différentes.

\begin{Ex}
En \og virgule fixe\fg{}, les limitations physiques des machines interdiraient de représenter simultanément, par exemple, $10^{100}$ et $10^{-100}$ , alors que la représentation en virgule flottante le permet. 
\end{Ex}




Bien entendu, l'addition de ces deux nombres donnera le premier (exactement) comme résultat, ce qui n'est pas gênant, mais leur multiplication donnera bien $1$ comme résultat (aux erreurs de représentation et de calcul près, car aucun de ces deux nombres n'est représentable exactement en machine).


\section{Les formats IEEE}

\subsection{La norme IEEE 754}

La représentation des nombres réels en machine (en \og virgule flottante\fg{} ) fait l'objet d'une norme (norme IEEE 754).\\

Cette norme reconnaît trois formats :
\begin{itemize}
 \item \og single\fg{} (réel représenté sur 32 bits),
\item \og double\fg{} (64 bits),
\item \og extended\fg{} (80 bits).
\end{itemize}

Les formats \og single\fg{} et \og double\fg{} sont analogues, à la taille des diverses composantes près.\\


Cette même norme prévoit un certain nombre de spécifications qui concernent les  calculs sur les réels représentés (indépendamment du format retenu) : aucune opération sur les réels ne doit provoquer, par
elle-même, d'interruption du déroulement normal du programme. Ni une
division par $0$, ni un dépassement de capacité, ni une tentative de
calcul impossible.\\

C'est au logiciel qui gouverne les calculs de vérifier le résultat et de provoquer, s'il le juge utile (et c'est ce que font en général les compilateurs), une interruption.\\

Néanmoins, il a fallu prévoir des représentations spéciales pour ces cas particuliers :
\begin{itemize}
 \item l'une s'appelle \og INF\fg{} (infini),
 \item l'autre \og NAN\fg{} (abréviation pour \og not a number\fg{} ).
\end{itemize}

\begin{Ex}
D'après ces spécifications, le résultat de $1/0$ (en réels) doit être INF, celui de $0/0$ doit être NAN.

On doit obtenir aussi $\sqrt{-1}=\rm{NAN}$, $\log{0}=-\rm{INF}$, $1/\rm{INF}=0$, mais  $\rm{INF}/\rm{INF}=\rm{NAN}$, de même que toute opération dont l'un des opérandes est NAN, par exemple $\sin(\rm {NAN})=\rm {NAN}$, $1+\rm{NAN}=\rm{NAN}$...
\end{Ex}


\begin{Rem}
Si vous voulez observer ces résultats, effectifs, vous serez obligés d'opérer depuis l'assembleur, aucun compilateur ne vous autorisera à tenter d'obtenir de pareilles horreurs!
\end{Rem}



Dans la représentation d'un nombre réel, on numérotera les bits à partir de 0 et à partir de la droite (bit \og le moins significatif\fg{} ) jusqu'à (respectivement) 31, 63 ou 79 (bit \og dominant\fg{} ).

\bigskip

\subsection{Format \og single\fg{}}\vskip 10pt

\begin{center} \begin{tabular}{|c|c|c|} \hline
s & \quad e \quad (8 bits) \quad & \quad m \quad (23 bits) \quad \\ \hline
\end{tabular}\end{center}\vskip 10pt

\noindent On retrouve la valeur du réel x représenté de la manière suivante :\\

\begin{itemize}
\item si $0 < e < 255$, alors $x=(-1)^s\cdot 2^{e-127}\cdot(1,m)$
\item si $e = 0$ et $m \not = 0$, alors $x=(-1)^s\cdot 2^{-126}\cdot(0,m)$
\item si $e = 0$ et $m = 0$, alors $x = 0$
\item si $e = 255$ et $m = 0$, alors $x = (-1)^s \cdot INF$
\item si $e = 255$ et $m \not = 0$, alors $x$ est un $NAN$

Comme, dans ce cas, $m$ peut prendre n'importe quelle valeur non nulle, il est possible de conserver de cette manière un code qui permet de reconnaître l'origine de l'erreur.
\end{itemize}


\subsection{Format \og double\fg{}} \vskip 10pt
\begin{center} \begin{tabular}{|c|c|c|} \hline
s & \quad e \quad (11 bits) \quad & \quad m \quad (52 bits) \quad \\ \hline
\end{tabular}\end{center}\vskip 10pt
On retrouve la valeur du réel x représenté de la manière suivante :\\

\begin{itemize}
\item si $0 < e < 2047$, alors $x=(-1)^s\cdot 2^{e-1023}\cdot(1,m)$
\item si $e = 0$ et $m \not = 0$, alors $x=(-1)^s\cdot 2^{-1022}\cdot(0,m)$
\item si $e = 0$ et $m = 0$, alors $x = 0$
\item si $e = 2047$ et $m = 0$, alors $x = (-1)^s \cdot INF$
\item si $e = 2047$ et $m \not = 0$, alors $x$ est un $NAN$
\end{itemize}


\subsection{Format \og extended\fg{}}\vskip 10pt
\begin{center} \begin{tabular}{|c|c|c|c|} \hline
s & \quad e \quad (15 bits) \quad & i & \quad m \quad (63 bits) \quad \\
\hline \end{tabular}\end{center}\vskip 10pt
On retrouve la valeur du réel x représenté de la manière suivante :\\

\begin{itemize}
\item si $0 \infeg e < 32767$, alors $x=(-1)^s\cdot 2^{e-16383}\cdot(i,m)$
\item si $e = 32767$ et $m = 0$, alors $x = (-1)^s \cdot INF$ (quelle que soit la valeur de
$i$)
\item si $e = 32767$ et $m \not = 0$, alors $x$ est un $NAN$ (quelle
que soit la valeur de $i$)
\end{itemize}


\subsection{D'une manière générale...}


\begin{enumerate}
\item s, représenté sur 1 bit, est le signe du nombre (0 pour +, 1 pour
-)\\

\item e est l'\og exposant biaisé\fg{}, \emph{i.e.} l'exposant translaté.

Cette translation a été introduite de manière à faciliter la comparaison des réels représentés entre eux :
\begin{itemize}
 \item Pour deux réels positifs non nuls, le plus grand est évidemment celui qui a le plus grand exposant (s'ils ont le même, on compare alors les \og mantisses\fg{} $m$).
\item Or, la représentation ordinaire dans les formats \og single\fg{} et \og double\fg{} ne permet pas la représentation de 0 : $[x = (-1)^s\cdot 2^{e-t}\cdot (1,m)]$ ne peut pas être nul, même si $m$ et $e-t$ sont nuls, auquel cas on obtient $1$ (ou $-1$).
\item Par ailleurs, comme $0$ est le plus petit réel positif, il est logique de lui attribuer le plus petit exposant (c'est-à-dire $-128$ ou $-1024$), et de lui attribuer évidemment une \og mantisse\fg{} nulle.
\item Mais il est plus simple (pour les tests) que $0$ possède un exposant nul, ce qui oblige à rendre tous les autres exposants positifs par la translation indiquée.
\item Pour retrouver le véritable exposant, il faut donc retrancher cette quantité à l'exposant de la représentation.\\
\end{itemize}

\item La notation $1,m$ (ou $0,m$ ou $i,m$) signifie que le nombre entier
$m$ doit être considéré comme la partie fractionnaire d'un nombre dont la représentation binaire a pour partie entière $1$ (ou $0$ ou $i$).\\

\item Pour les formats \og single\fg{} et \og double\fg{}, la formule à appliquer est différente dans le cas où l'exposant e est nul.

Il s'agit de ce que l'on appelle un \og réel dénormalisé\fg{}, introduit pour le motif suivant :
\begin{itemize}
 \item les chiffres significatifs du réel représenté sont contenus dans la mantisse ;
\item celle-ci est de longueur fixe pour un format donné,
\item donc, quel que soit l'ordre de grandeur du réel, sa représentation est obtenue avec la même précision relative, ce qui permet de conna\^\i tre la précision du résultat d'un calcul.
\end{itemize}

Cette mantisse $(1,m)$ représente un nombre compris entre $1$ (inclus, si $m=0$) et $2$ (exclu).

On obtient ce nombre en multipliant ou en divisant le réel à représenter par $2$ jusqu'à ce que le résultat soit compris entre $1$ et $2$. Le nombre d'opérations effectuées donne l'exposant (le vrai, négatif dans le cas de multiplications, positif dans le cas de divisions).

Pour des nombres réels trop petits, l'exposant peut alors être lui-même trop petit pour être représentable dans la plage qui lui est fixée. On admet alors que, pour la plus petite valeur de l'exposant (\og biaisé \fg{} ), c'est-à-dire $0$, la mantisse est à interpréter sous la forme $0,m$, ce qui permet de représenter encore quelques réels trop petits pour être représentés dans la représentation normalisée (les Anglo-Saxons parlent de \og progressive underflow\fg{} ). 

Ces réels \og dénormalisés\fg{} sont distingués des autres, parce qu'ils sont représentés avec une précision moindre (la mantisse a moins de 52 chiffres binaires significatifs).

Autrement dit, la précision d'un calcul qui utilise un réel dénormalisé n'est plus assurée, mais le risque d'une division par $0$ (alors que le \og vrai\fg{} nombre n'est pas nul) est diminué.\\

\item La distinction entre réels \og normalisés\fg{} et \og dénormalisés \fg{} disparaît dans le format \og extended\fg{}, puisque la partie entière de la mantisse y figure explicitement (le bit $i$, valeur $0$ ou $1$).

L'inconvénient est qu'il existe alors plusieurs représentations
possibles pour un même nombre réel.

\begin{Ex}
$1$ peut être représenté par $i=1$, $m=0$, $e=16383$, mais aussi par $i=0$, $m=100....0$, $e=16384$, ou encore $i=0$, $m=010...0$, $e=16385$, etc.
\end{Ex}

Mais il est clair que, pour la précision d'un calcul, il vaut mieux
utiliser tous les bits disponibles dans la mantisse (pour avoir le maximum
de chiffres significatifs).

C'est-à-dire qu'il faut choisir, parmi toutes les représentations possibles pour un nombre réel, celle pour laquelle $i=1$ : c'est ce que fait la machine (que les opérations soient implantées logiciellement ou effectuées par un coprocesseur arithmétique).

Autrement dit, on réservera la valeur $0$ pour $i$ au cas où l'exposant \og biaisé\fg{} est nul, comme pour les autres formats, et le problème de la précision se pose de la même manière.
\end{enumerate}



\subsection{Format \og extended\fg{} des microprocesseurs.} Dans un langage tel que C (ou java),
\begin{itemize}
 \item le format \og single\fg{} est obtenu avec les valeurs de type \og float\fg{},
\item le format \og double\fg{} est disponible dans les valeurs de type
\og double\fg{},
\item le format \og extended\fg{} dans les valeurs de type \og long double\fg{}.\\
\end{itemize}

Pour être complet, il est nécessaire de préciser que les microprocesseurs modernes possèdent presque tous, intégrée, une unité de calcul spécialisée dans le calcul sur les réels, ayant des registres de taille adaptée à la représentation de ces nombres (donc plus longs
que les registres de l'unité de calcul arithmétique et logique principale).\\


Plus anciennement, ce rôle était confié à une unité externe que l'on appelait \og coprocesseur arithmétique\fg{} et qui était quelquefois optionnelle.

Si, dans ce cas, l'option n'avait pas été retenue, les opérations sur les réels  étaient implémentées logiciellement au prix d'un dramatique allongement des temps de calcul.\\


Toujours est-il que les formats disponibles dans une unité de calcul sur les flottants dépendent de la taille des registres, et ceux-ci sont parfois limités à 64 bits, ce qui interdit le format \og extended\fg{} en natif sur la machine (si le langage de programmation utilisé y donne accès, les opérations sont alors implémentées logiciellement).\\

Lorsque le format \og extended\fg{} est disponible en natif dans la machine, les registres sont en général de taille 96 bits (et non 80).

Les 16 bits supplémentaires, s'ils sont évidemment utilisés par le processeur pour sa cuisine interne, ne sont jamais significatifs dans les résultats accessibles à l'utilisateur, et sont mis à 0.

Autrement dit, on obtient le réel au format \og extended\fg{} en supprimant les 16 bits nuls.
\vskip 10pt
\begin{center} \begin{tabular}{|c|c|c|c|c|c} \hline
s & \quad e \quad (15 bits) \quad & \quad (16 bits nuls) \quad & i & \quad m
\quad (63 bits) \quad \\ \hline \end{tabular}\end{center}\vskip 10pt

\bigskip


\section{Réels représentables et précision}

Tous les réels normalisés représentés en machine comportent le même nombre de chiffres binaires significatifs (dans un format donné).\\

Comme deux nombres dont les expressions binaires comportent le même nombre de chiffres n'ont pas nécessairement le même nombre de chiffre en
représentation décimale, le nombre de chiffres significatifs en base
10 peut varier d'une unité.

\begin{Ex}
1000 en base 2 est 8 en décimal : 4 chiffres binaires, 1 chiffre décimal, 1100 binaire est 12 décimal : 4 chiffres binaires, 2 chiffres décimaux.
\end{Ex}


Ainsi,
\begin{itemize}
 \item en format \og single\fg{}, on a 6 ou 7 chiffres significatifs,
\item en format \og double\fg{}, 15 ou 16 chiffres,
\item en format \og extended\fg{}, 19 ou 20.\\
\end{itemize}


Une telle précision peut sembler totalement superflue : elle est cependant largement insuffisante pour, par exemple, les calculs en astronomie (trajectoires de satellites, etc.), pour lesquels il est
nécessaire de faire appel à des précisions nettement supérieures...

\bigskip

\noindent Le plus grand nombre réel représentable en format \og single\fg{} est tel que
\begin{itemize}
\item $e = 254$, donc le véritable exposant est $254-127=127$
\item $m$ est constitué de 23 \og 1\fg{} , la mantisse a donc pour valeur
$1,1\ldots 1$, c'est-à-dire
$1+2^{-1}+2^{-2}+2^{-3}+\cdot\cdot\cdot+2^{-23}$ (somme d'une progression
géométrique de raison 1/2, donc) $= 2-2^{-23}$.
\item Il vaut donc exactement $2^{127}(2-2^{-23}) = 2^{128}-2^{104}$, c'est à dire approximativement $3,403\cdot 10^{38}$.\\
\end{itemize}


\noindent Le plus petit réel positif normalisé (\og single\fg{} ) est tel que
\begin{itemize}
\item $e = 1$, donc le véritable exposant est $1-127=-126$
\item $m=0$, donc la mantisse vaut 1
\item Il vaut donc exactement $2^{-126}$ c'est-à-dire approximativement
$1,175\cdot 10^{-38}$.\\
\end{itemize}


\noindent Le plus petit réel positif dénormalisé (\og single\fg{} ) est tel que
\begin{itemize}
\item $e = 0$, donc le véritable exposant est $-126$
\item $m=0\ldots 01$, donc la mantisse vaut $0,0\ldots 01$, soit $2^{-23}$
\item Il vaut donc exactement $2^{-149}$ c'est-à-dire approximativement
$1,401\cdot 10^{-45}$.\\
\end{itemize}

\noindent En format \og double\fg{}, les nombres correspondants sont
$1,7\cdot 10^{308}$, $2,3\cdot 10^{-308}$, $5\cdot 10^{-324}$.\\

\noindent En format \og extended\fg{}, les nombres correspondants sont
$1,1\cdot 10^{4932}$, $1,7 \cdot 10^{-4932}$, $1,9 \cdot 10^{-4951}$.\\


Les réels qui sont représentés en machine sont exacts; par contre, tous les nombres réels ne sont pas représentables (la représentation est évidemment discrète).

\begin{Ex}
Considérons le réel $1$ en format \og extended\fg{} : \og vrai exposant\fg{} : $0$, $s=0$, $i=1$, $m=0$, donc $e=16383$, c'est-à-dire (en hexadécimal) : 
\begin{itemize}
 \item 3FFF pour les 16 premiers bits,
\item 8000 hexadecimal pour les 16 suivants,
\item et tous les derniers sont nuls,
\end{itemize}

\noindent donc : 3FFF 8000 0000 0000 0000.

Le réel représentable en machine, supérieur à $1$ et le plus proche
de $1$, a évidemment un $m$ égal à $0\ldots 01$, il s'agit donc 
de 3FFF 8000 0000 0000 0001. 

La différence des mantisses $(i,m)$ de ces deux nombres est $0,0\ldots 01$, soit (exactement) $2^{-63}$, ou encore (environ) $1,08\cdot 10^{-19}$. 
\end{Ex}

En d'autres termes...
\begin{itemize}
 \item Dans l'intervalle $[1,2[$, les réels représentables varient de $2^{-63}$ en $2^{-63}$.
\item Dans l'intervalle $[2,4[$, les réels représentables varient de $2^{-62}$ en $2^{-62}$.
\item etc.
\item Dans l'intervalle $[2^{63},2^{64}[$, les réels représentables varient de $2^0$ en $2^0$, donc d'unité en unité : on ne peut plus représenter que des nombres entiers, mais il s'agit d'entiers qui sont plus grands que les entiers de la machine (sur 32 bits seulement).
\item Dans l'intervalle suivant, on ne peut plus représenter tous les entiers, on n'en représente plus qu'un sur deux, puis un sur quatre, etc.\\
\end{itemize}

\begin{Rem}

Les calculs sur les réels en machine sont exacts dans le sens suivant :

Si, par exemple, on additionne, soustrait ou multiplie deux entiers représentables sous forme de réels en machine, et si le résultat est aussi représentable sous forme de réel en machine, alors ce résultat est exact.

Autrement dit, il s'agit encore d'un entier exactement.
\end{Rem}


Le problème de la division est différent, parce que c'est évidemment l'algorithme de la division des réels qui est appliqué et non celui de la division euclidienne des entiers.\gsaut

\begin{Ex}
Soit à représenter $8,5$ sous forme de réel double précision (format \og double\fg{} )
\begin{enumerate}
 \item Le ramener entre 1 et 2 par divisions par 2 : $8,5 = 8\times 1,0625$.
\item L'exposant est donc $3$, et $e=3+1023=1026$, les 12 premiers bits sont donc $0100\,0000\,0010$ (en effet, $1026=1024+2$, et $1024$ est $2^{10}$, dont l'écriture binaire est \og 1\fg{} suivi de 10 \og 0\fg{} . On rajoute $2$, soit $10$ binaire).
\item $1,0625 = 1 + 0,0625$, et $0,0625= 2^{-4}$, soit (en binaire) $0,0001$, donc $m=0001\,00\ldots$ 
\end{enumerate}

On obtient : 0100 0000 0010 0001 0000 0000 $\ldots$, soit 4021 0000 0000 0000 en hexadécimal.
\end{Ex}


\begin{Ex}
Soit à représenter $0,1$ sous forme de réel double précision
\begin{enumerate}
 \item Le ramener entre $1$ et $2$ par multiplications par $2$ : $16\times
0,1=1,6$
\item L'exposant est donc $-4$, et $e=-4+1023=1019$, les 12 premiers bits sont (comme $s = 0$) 0011 1111 1011 (3FB hexadécimal)
\item $1,6=1+0,6$.

Pour obtenir la représentation binaire de $0,6$, il faut effectuer la division de 6 par 10 en base 2, ou, mieux, celle de 3 par 5 (donc 11 par 101 en base 2).

On obtient : 0,1001 1001 1001 $\ldots$.

Ce développement binaire est infini mais périodique, il suffit de le tronquer à 52 chiffres et d'effectuer l'arrondi.

Les 4 derniers bits sont 1001 et le suivant serait 1, donc l'arrondi est fait à 1010 pour les 4 derniers, soit A hexadécimal (la représentation n'est donc pas exacte, on l'a signalé plus haut).

Les précédents (par groupe de 4) sont égaux à 1001, soit 9 hexadécimal; on obtient finalement : 3FB9 9999 9999 999A.
\end{enumerate}
 
Attention : en \og single\fg{} , la représentation de 0,1 serait 3DCC CCCD et, en \og extended\fg{} : 3FFB CCCC CCCC CCCC CCCD (faites-le aussi!).


Autrement dit : le passage d'un format à l'autre n'est pas évident en hexadécimal (il ne suffit pas de \og raccourcir\fg{} ou de \og rallonger\fg{} !).
\end{Ex}



\gsaut
\centerline{\x{Fin du Chapitre}}