<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[letterpaper,11pt,english,french]{memoir}
  \usepackage{natbib}
  \usepackage{babel}
  \usepackage[babel=true]{microtype}
  \usepackage[autolanguage]{numprint}
  \usepackage{amsmath,amsthm,amsfonts}
  \usepackage{fancyvrb}
  \usepackage{soul}

  %% Informations de la page de titre
  \title{Exemple de document Ã©laborÃ©}
  \author{Vincent Goulet}

  %% Polices de caractÃ¨res (configuration fonction du moteur utilisÃ©)
  \usepackage{iftex}            % dÃ©tection du moteur
  \iftutex                      % XeLaTeX
    \usepackage{fontspec}
    \usepackage{unicode-math}
    \setmainfont{STIXTwoText}
    [
      Extension = .otf,
      UprightFont = *-Regular,
      BoldFont = *-SemiBold,
      ItalicFont = *-Italic,
      BoldItalicFont = *-SemiBoldItalic,
      Scale = 1,
      Ligatures = TeX
    ]
    \setmathfont{STIXTwoMath-Regular}
    [
      Extension = .otf,
      Scale = 1,
      Ligatures = TeX
    ]
  \else                         % pdfLaTeX
    \usepackage[utf8]{inputenc}
    \usepackage[T1]{fontenc}
    \usepackage{stix2}
  \fi
  \usepackage{icomma}           % charger aprÃ¨s les polices

  %% Couleurs
  \usepackage{xcolor}
  \definecolor{comments}{rgb}{0.7,0,0}
  \definecolor{shadecolor}{gray}{0}
  \definecolor{link}{rgb}{0,0.4,0.6}   % ~RoyalBlue de dvips
  \definecolor{url}{rgb}{0.6,0,0}      % rouge-brun
  \definecolor{citation}{rgb}{0,0.5,0} % vert foncÃ©

  %% Hyperliens
  \usepackage{hyperref}
  \hypersetup{
    pdfauthor = {Vincent Goulet},
    colorlinks,
    linktocpage,
    urlcolor = url,
    linkcolor = link,
    citecolor = citation,
    bookmarksopen,
    bookmarksnumbered,
    bookmarksdepth = subsubsection
  }
  \renewcommand{\figureautorefname}{figure}
  \renewcommand{\tableautorefname}{tableau}
  \newcommand{\subtableautorefname}{tableau}
  \newcommand{\exempleautorefname}{exemple}
  \newcommand{\algorithmeautorefname}{algorithme}

  \frenchbsetup{%
    CompactItemize=false,          % ne pas compacter les listes
    ThinSpaceInFrenchNumbers=true, % espace fine dans les nombres
    og=Â«, fg=Â»                     % guillemets franÃ§ais
  }

  %% Environnements d'exemples et al.
  \theoremstyle{plain}
  \newtheorem{algorithme}{Algorithme}[chapter]
  \newtheorem{thm}{ThÃ©orÃ¨me}[chapter]

  \theoremstyle{definition}
  \newtheorem{exemple}{Exemple}[chapter]
  \newtheorem{definition}{DÃ©finition}[chapter]
  \newtheorem*{astuce}{Astuce}

  \theoremstyle{remark}
  \newtheorem*{remarque}{Remarque}
  \newenvironment{rem}{\begin{remarque} \mbox{}}{\end{remarque}}

  %% Nouveaux environnements pour le code informatique R
  \DefineVerbatimEnvironment{Sinput}{Verbatim}{fontshape=sl}
  \DefineVerbatimEnvironment{Soutput}{Verbatim}{}
  \DefineVerbatimEnvironment{Scode}{Verbatim}{fontshape=sl}
  \newenvironment{Schunk}{}{}

  %% Nouvelles commandes
  \newcommand{\code}[1]{\texttt{#1}}
  \newcommand{\ieee}[3]{\fbox{$#1$}\hspace{2pt}\fbox{$#2$}\hspace{2pt}\fbox{$#3$}}
  \newcommand{\fl}{\mathrm{fl}}

  %% NumÃ©roter les sous-sections
  \maxsecnumdepth{subsection}

  %% Sous-tableaux et figures
  \newsubfloat{table}

  %% Style de la bibliographie.
  \bibliographystyle{francais}

\begin{document}

\frontmatter                    % pages liminaires

\begin{titlingpage}
  \maketitle                    % production de la page de titre
\end{titlingpage}
\cleardoublepage

\tableofcontents                % production de la TdM
\cleardoublepage

\mainmatter                     % corps du document

\chapter{ArithmÃ©tique des ordinateurs}
\label{chap:ordinateurs}

\section{Les ordinateurs ne savent pas compter}
\label{sec:ordinateurs:introduction}

Le type de bogue le plus frÃ©quemment rapportÃ© dans les forums de
discussion de R a trait au fait que le logiciel ne retourne
pas le bon rÃ©sultat lors d'opÃ©rations arithmÃ©tiques simples.

On devine que les crÃ©ateurs de R n'ont pas nÃ©gligÃ© une fonctionnalitÃ©
aussi fondamentale pour un langage mathÃ©matique que le calcul
arithmÃ©tique. Les supposÃ©es erreurs ci-dessus relÃ¨vent toutes de la
reprÃ©sentation interne des nombres dans un ordinateur et d'erreurs
d'arrondi inhÃ©rentes aux opÃ©rations arithmÃ©tiques avec ces nombres. En
effet, un des plus cÃ©lÃ¨bres principes de programmation proposÃ©s par
\cite{Kernighan:style:1978} est:
\begin{center}
  \label{programming_principle}
  $10,0$ fois $0,1$ ne donne jamais vraiment $1,0$.
\end{center}
D'ailleurs, les auteurs des faux rapports de bogues dans
\texttt{r-help} sont invariablement renvoyÃ©s Ã&nbsp; l'\href{http://cran.r-project.org/doc/FAQ/R-FAQ.html#Why-doesn_0027t-R-think-these-numbers-are-equal_003f}{entrÃ©e 7.31} de la
foire aux questions\footnote{%
  \url{https://cran.r-project.org/doc/FAQ/R-FAQ.html}} %
de R.

Pour quiconque travaille rÃ©guliÃ¨rement avec un ordinateur pour faire
du calcul scientifique, connaitre globalement le fonctionnement
interne d'un ordinateur peut s'avÃ©rer prÃ©cieux pour les raisons
suivantes, entre autres:
\begin{itemize}
\item Ã©viter les erreurs d'arrondi et de troncature;
\item Ã©viter les dÃ©passements et soupassements de capacitÃ©
  (\emph{overflow} et \emph{underflow});
\item optimiser le code informatique.
\end{itemize}

Ce chapitre se penche sur les grands principes de l'arithmÃ©tique des
ordinateurs. En fait, les ordinateurs ne savent pas faire
d'arithmÃ©tique Ã&nbsp; proprement parler. Ils ne connaissent que deux Ã©tats:
ouvert (1) et fermÃ© (0). Nous en profiterons donc d'abord pour rÃ©viser
la conversion des nombres dÃ©cimaux vers, et de, n'importe quelle base.
AprÃ¨s avoir, Ã&nbsp; la \autoref{sec:ordinateurs:unites}, introduit les
principales unitÃ©s de mesure en informatique, nous expliquerons la
reprÃ©sentation interne des nombres dans un ordinateur en nous
concentrant sur la double prÃ©cision. Nous pourrons ainsi justifier que
les ordinateurs ne peuvent reprÃ©senter qu'un sous-ensemble des nombres
rÃ©els, d'oÃ¹ les erreurs d'arrondi et de troncature. La
\autoref{sec:ordinateurs:arithmetique} explique comment ces erreurs
surviennent. On y donne Ã©galement quelques pistes pour Ã©viter ou pour
diminuer l'impact de ces erreurs. Enfin, le chapitre se clÃ´t par un
survol d'un sujet quelque peu pÃ©riphÃ©rique: la reprÃ©sentation interne
des caractÃ¨res.


\section{Conversion de base}
\label{sec:ordinateurs:conversion}

La \emph{base}, dans un systÃ¨me de numÃ©ration, est le nombre de
symboles (habituellement les chiffres) qui pourront servir Ã&nbsp; exprimer
des nombres. L'humain s'est habituÃ© Ã&nbsp; compter en base $10$, le systÃ¨me
\emph{dÃ©cimal}, oÃ¹ les symboles sont $0, 1, \dots, 9$. De nos jours,
la grande majoritÃ© des ordinateurs travaillent toutefois en base $2$, le
systÃ¨me \emph{binaire}. Les autres systÃ¨me d'usage courant,
principalement en informatique, sont l'\emph{octal} (base $8$) et
l'\emph{hexadÃ©cimal} (base $16$). Dans ce dernier systÃ¨me, les symboles
utilisÃ©s pour les nombres $10$--$15$ sont gÃ©nÃ©ralement les lettres A--F.
(C'est pourquoi l'on retrouve ces six lettres sur le pavÃ© des
calculatrices scientifiques).

Cette section Ã©tudie la conversion des nombres entre la base $10$ et une
autre base quelconque.

\subsection{Notation et dÃ©finitions}
\label{sec:ordinateurs:conversion:notation}

De maniÃ¨re gÃ©nÃ©rale, soit $x$ un nombre (entier pour le moment) dans
la base de numÃ©ration $b$ composÃ© de $m$ chiffres ou symboles, c'est-Ã&nbsp;-dire
\begin{equation*}
  x = x_{m-1}x_{m-2} \cdots x_1x_0,
\end{equation*}
oÃ¹ $0 \leq x_i \leq b - 1$. On a donc
\begin{equation}
  \label{eq:ordinateurs:def_base}
  x = \sum_{i = 0}^{m - 1} x_i b^i.
\end{equation}

Lorsque le contexte ne permet pas de dÃ©terminer avec certitude la base
d'un nombre, celle-ci est identifiÃ©e en indice du nombre par un nombre
dÃ©cimal. Par exemple, $10011_2$ est le nombre binaire $10011$.

\begin{exemple}
  Soit le nombre dÃ©cimal $348$. Selon la notation ci-dessus, on a $x_0 =
  8$, $x_1 = 4$, $x_2 = 3$ et $b = 10$. En effet,
  \begin{displaymath}
    348 = 3 \times 10^2 + 4 \times 10^1 + 8 \times 10^0.
  \end{displaymath}
  Ce nombre a les reprÃ©sentations suivantes dans d'autres bases. En binaire:
  \begin{align*}
    101011100_{2}
    &amp;= 1 \times 2^8 + 0 \times 2^7 + 1 \times 2^6 \\
    &amp;\phantom{=} + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 \\
    &amp;\phantom{=} + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0.
  \end{align*}
  En octal:
  \begin{equation*}
    534_{8} = 5 \times 8^2 + 3 \times 8^1 + 4 \times 8^0.
  \end{equation*}
  En hexadÃ©cimal:
  \begin{equation*}
    15\mathrm{C}_{16} = 1 \times 16^2 + 5 \times 16^1 + 12 \times 16^0.
  \end{equation*}
  Des reprÃ©sentations ci-dessus, l'hexadÃ©cimale est la plus compacte:
  elle permet de reprÃ©senter avec un seul symbole un nombre binaire
  comptant jusqu'Ã&nbsp; quatre chiffres. C'est, entre autres, pourquoi
  c'est une reprÃ©sentation populaire en informatique.%
  \qed
\end{exemple}

Dans un ordinateur rÃ©el (par opposition Ã&nbsp; thÃ©orique), l'espace
disponible pour stocker un nombre est fini, c'est-Ã&nbsp;-dire que $m &lt;
\infty$. Le plus grand nombre que l'on peut reprÃ©senter avec $m$
chiffres ou symboles en base $b$ est
\begin{align*}
  x_{\text{max}}
  &amp;= \sum_{i = 0}^{m - 1} (b - 1) b^i \\
  &amp;= (b - 1) \sum_{i = 0}^{m - 1} b^i \\
  &amp;= (b - 1)
  \left(
    \frac{b^m - 1}{b - 1}
  \right) \\
  &amp;= b^m - 1.
\end{align*}

Par exemple, le plus grand nombre dÃ©cimal reprÃ©sentable avec $m = 4$
symboles est
\begin{equation*}
  x_{\text{max}} = \nombre{9999} = \nombre{10000} - 1 = 10^4 - 1,
\end{equation*}
alors que le plus grand nombre binaire est seulement
\begin{equation*}
  x_{\text{max}} = 1111 = 10000 - 1 = 2^4 - 1 = 15_{10}.
\end{equation*}

Par une extension naturelle de ce qui prÃ©cÃ¨de, un nombre composÃ© de $m
\geq 0$ symboles dans sa partie entiÃ¨re et $n \geq 0$ symboles dans sa
partie fractionnaire est reprÃ©sentÃ© en base $b$ comme
\begin{align*}
  x
  &amp;= x_{m-1}x_{m-2} \cdots x_1x_0,x_{-1}x_{-2} \cdots x_{-n} \\
  &amp;= \sum_{i = -n}^{m - 1} x_i b^i.
\end{align*}
Le symbole qui sÃ©pare les parties entiÃ¨re et fractionnaire du nombre
est la \emph{sÃ©paration fractionnaire} (une virgule en franÃ§ais, un
point en anglais).


\subsection{Conversion vers une base quelconque}
\label{sec:ordinateurs:conversion:10_vers_b}

Avant de discuter de la conversion de nombres dÃ©cimaux vers une base
quelconque, il convient de dÃ©finir les notions de \emph{quotient} et
de \emph{reste} d'une division.

Le quotient est la partie entiÃ¨re de la division de deux entiers $a$
et $d$; sa reprÃ©sentation mathÃ©matique habituelle est
\begin{equation}
  \label{eq:ordinateurs:quotient}
  q = \left\lfloor \frac{a}{d} \right\rfloor,
\end{equation}
oÃ¹ $\lfloor x \rfloor$ est la fonction qui retourne le plus grand
entier infÃ©rieur ou Ã©gal Ã&nbsp; $x$. Le reste de la division est simplement
la valeur
\begin{equation}
  \label{eq:ordinateurs:remainder}
  r = a - d \left\lfloor \frac{a}{d} \right\rfloor.
\end{equation}
Ã‰videmment, on a $r \in \{0, 1, \dots, d - 1\}$. Le reste est le
rÃ©sultat de l'opÃ©ration modulo, notÃ©e $r = a \bmod d$.

On remarquera que le premier chiffre en partant de la droite d'un
entier dÃ©cimal est le reste de la division de ce nombre par $10$, que le
second chiffre est le reste de la division par $10$ du quotient de la
division prÃ©cÃ©dente, et ainsi de suite. La conversion d'un nombre
dÃ©cimal en une base $b$ implique simplement de diviser par $b$ plutÃ´t
que par $10$ et de dÃ©terminer le symbole dans la base $b$ correspondant
au reste de chaque division.

L'algorithme suivant reprend ses idÃ©es sous forme plus formelle et en
ajoutant le traitement de la partie fractionnaire. Nous dÃ©montrerons
plus loin qu'il n'est pas rÃ©ellement nÃ©cessaire de savoir effectuer la
conversion de la partie fractionnaire d'un nombre rÃ©el.

\begin{algorithme}[Conversion de la base $10$ vers la base $b$]
  \label{algo:ordinateurs:10_vers_b}
  Soit $x$ un nombre rÃ©el en base $10$.
  \begin{enumerate}
  \item Poser $i \leftarrow 0$ et $v \leftarrow \lfloor x \rfloor$.
  \item RÃ©pÃ©ter les Ã©tapes suivantes jusqu'Ã&nbsp; ce que $v = 0$:
    \begin{enumerate}
    \item Poser $d_i \leftarrow v \bmod b$ et trouver $x_i$, le
      symbole dans la base $b$ correspondant Ã&nbsp; $d_i$;
    \item Poser $v \leftarrow \lfloor v/b \rfloor$;
    \item Poser $i \leftarrow i + 1$.
    \end{enumerate}
  \item Poser $i \leftarrow 1$ et $v \leftarrow x - \lfloor x
    \rfloor$.
  \item RÃ©pÃ©ter les Ã©tapes suivantes jusqu'Ã&nbsp; ce que $v = 0$ ou que $i
    = n$ (le nombre voulu ou maximal de chiffres aprÃ¨s la sÃ©paration
    fractionnaire):
    \begin{enumerate}
    \item Poser $d_{-i} \leftarrow \lfloor bv \rfloor$ et trouver $x_{-i}$, le
      symbole dans la base $b$ correspondant Ã&nbsp; $d_{-i}$;
    \item Poser $v \leftarrow bv - d_{-i}$;
    \item Poser $i \leftarrow i + 1$.
    \end{enumerate}
  \item Retourner
    \begin{displaymath}
      x_b = x_{m-1}x_{m-2} \cdots x_1x_0,x_{-1}x_{-2} \cdots x_{-n}.
    \end{displaymath}
  \end{enumerate}
\end{algorithme}

\begin{exemple}
  \label{ex:ordinateurs:10_vers_b}
  Soit le nombre dÃ©cimal $23,31$ que l'on convertit en binaire (base
  $2$) avec un maximum de cinq chiffres aprÃ¨s la sÃ©paration
  fractionnaire ($n = 5$). Le \autoref{tab:ordinateurs:10_vers_b}
  montre le processus en suivant les Ã©tapes de
  l'\autoref{algo:ordinateurs:10_vers_b}. On obtient le
  rÃ©sultat final en combinant la derniÃ¨re colonne du
  \autoref{tab:ordinateurs:10_vers_b:a} lue de bas en haut avec la
  derniÃ¨re colonne du \autoref{tab:ordinateurs:10_vers_b:b} lue de
  haut en bas. Ainsi, la reprÃ©sentation binaire du $23,31$ limitÃ©e Ã&nbsp;
  cinq chiffres aprÃ¨s la virgule est $10111,01001$.

  \begin{table}
    \caption{Conversion du nombre dÃ©cimal $23,31$ en binaire.}
    \label{tab:ordinateurs:10_vers_b}
    \begin{minipage}[t]{0.45\linewidth}
      \subcaption{partie entiÃ¨re}
      \label{tab:ordinateurs:10_vers_b:a}
      \begin{tabular*}{\linewidth}{crrcc}
        \toprule
        $i$ &amp; \multicolumn{1}{c}{$v$} &amp; $\lfloor v/2 \rfloor$ &amp; $v \bmod 2$ &amp; $x_i$ \\
        \midrule
        $0$ &amp; $23$ &amp; $11$ &amp; $1$ &amp; $1$ \\
        $1$ &amp; $11$ &amp;  $5$ &amp; $1$ &amp; $1$ \\
        $2$ &amp;  $5$ &amp;  $2$ &amp; $1$ &amp; $1$ \\
        $3$ &amp;  $2$ &amp;  $1$ &amp; $0$ &amp; $0$ \\
        $4$ &amp;  $1$ &amp;  $0$ &amp; $1$ &amp; $1$ \\
        \bottomrule
      \end{tabular*}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{0.45\linewidth}
      \subcaption{partie fractionnaire}
      \label{tab:ordinateurs:10_vers_b:b}
      \begin{tabular*}{\linewidth}{ccccc}
        \toprule
        $i$ &amp; $v$ &amp; $2v$ &amp; $\lfloor 2v \rfloor$ &amp; $x_{-i}$ \\
        \midrule
        $1$ &amp; $0,31$ &amp; $0,62$ &amp; $0$ &amp; $0$ \\
        $2$ &amp; $0,62$ &amp; $1,24$ &amp; $1$ &amp; $1$ \\
        $3$ &amp; $0,24$ &amp; $0,48$ &amp; $0$ &amp; $0$ \\
        $4$ &amp; $0,48$ &amp; $0,96$ &amp; $0$ &amp; $0$ \\
        $5$ &amp; $0,96$ &amp; $1,92$ &amp; $1$ &amp; $1$ \\
        \bottomrule
      \end{tabular*}
    \end{minipage}
  \end{table}
  \qed
\end{exemple}

\begin{exemple}
  \label{ex:ordinateurs:10_vers_b:bis}
  Soit de nouveau la conversion de $23,31$ en binaire avec une partie
  fractionnaire d'au plus cinq chiffres. En suivant les Ã©tapes de la
  remarque ci-dessus, on a:
  \begin{enumerate}
  \item $23,31 \times 2^5 = 23,31 \times 32 = 745,92$;
  \item la reprÃ©sentation binaire de $745 = 2^9 + 2^7 + 2^6 + 2^5 +
    2^3 + 1$ est $1011101001$;
  \item enfin, en dÃ©plaÃ§ant la virgule de cinq positions vers la
    gauche, on obtient $10111,01001$, comme Ã&nbsp;
    l'\autoref{ex:ordinateurs:10_vers_b}.
  \end{enumerate}
  \qed
\end{exemple}

On tire une conclusion intÃ©ressante de la procÃ©dure ci-dessus. S'il
existe un entier $k \leq n$ tel que la partie fractionnaire de $x$ est
un multiple de $1/b^k$, alors la multiplication de $x$ par $b^k$
rÃ©sultera en un entier. Par consÃ©quent, la reprÃ©sentation de $x$ en
base $b$ aura une partie fractionnaire de longueur finie. Ainsi, pour
obtenir une reprÃ©sentation binaire finie, la partie fractionnaire d'un
nombre rÃ©el doit Ãªtre un multiple de $\frac{1}{2}, \frac{1}{4},
\frac{1}{8}, \dots$ Ce n'Ã©tait pas le cas Ã&nbsp;
l'\autoref{ex:ordinateurs:10_vers_b:bis} (la partie fractionnaire
Ã©tant $0,31$), d'oÃ¹ la nÃ©cessitÃ© de limiter le nombre de chiffres
aprÃ¨s la virgule.

\subsection{Conversion en dÃ©cimal}
\label{sec:ordinateurs:conversion:b_vers_10}

La conversion d'un nombre en base $b$ vers la base $10$ repose
essentiellement sur la dÃ©finition \eqref{eq:ordinateurs:def_base},
mais avec chaque symbole $x_i$ remplacÃ© pour son Ã©quivalent dÃ©cimal.
Un algorithme de conversion est le suivant.

\begin{algorithme}[Conversion de la base $b$ vers la base $10$]
  \label{algo:ordinateurs:b_vers_10}
  Soit $x$
  \begin{displaymath}
    x_b = x_{m-1}x_{m-2} \cdots x_1x_0,x_{-1}x_{-2} \cdots x_{-n}
  \end{displaymath}
  un nombre rÃ©el en base $b$.
  \begin{enumerate}
  \item Poser $x \leftarrow 0$ et $y \leftarrow 0$.
  \item Pour $i = m - 1, m - 2, \dots, 0$, faire les Ã©tapes suivantes:
    \begin{enumerate}
    \item Trouver $d_i$, le nombre dÃ©cimal correspondant au symbole
      $x_i$;
    \item Poser $x \leftarrow x b + d_i$.
    \end{enumerate}
  \item Pour $i = -n, -n + 1, \dots, -1$, faire les Ã©tapes suivantes:
    \begin{enumerate}
    \item Trouver $d_i$, le nombre dÃ©cimal correspondant au symbole
      $x_i$;
    \item Poser $y \leftarrow (y + d_i)/b$.
    \end{enumerate}
  \item Retourner $x + y$.
  \end{enumerate}
\end{algorithme}

On peut, ici aussi, aisÃ©ment Ã©viter de devoir convertir la partie
fractionnaire. Il suffit de dÃ©placer la virgule de $n$ positions vers
la droite dans le nombre $x_b$ de maniÃ¨re Ã&nbsp; obtenir un entier, de
convertir ce nombre en dÃ©cimal avec les Ã©tapes 1 et 2 de
l'\autoref{algo:ordinateurs:b_vers_10} et, finalement, de
diviser le nombre obtenu par $b^n$.

\begin{exemple}
  \label{ex:ordinateurs:b_vers_10}
  On convertit le nombre binaire $101011,011$ en dÃ©cimal. Le
  \autoref{tab:ordinateurs:b_vers_10} illustre le processus de
  conversion selon l'\autoref{algo:ordinateurs:b_vers_10} (le chiffre
  en surbrillance est celui traitÃ© lors de chaque Ã©tape de
  l'algorithme). Le rÃ©sultat final est $43,375$.

  De maniÃ¨re Ã©quivalente, mais plus simple, on peut dÃ©placer la
  virgule de trois positions vers la droite pour obtenir l'entier
  binaire $101011011$. Ce nombre est $2^8 + 2^6 + 2^4 + 2^3 + 2 + 1 =
  347$ en dÃ©cimal. Enfin, $347 \div 2^3 = 43,375$.%
  \qed

  \begin{table}
    \caption{Conversion du nombre binaire $101011,011$ en dÃ©cimal}
    \label{tab:ordinateurs:b_vers_10}
    \begin{minipage}[t]{0.45\linewidth}
      \subcaption{partie entiÃ¨re}
      \begin{tabular*}{\linewidth}{@{\extracolsep{\fill}}ccr}
        \toprule
        $i$ &amp; $d_i$ &amp; $x$ \\
        \midrule
        $5$ &amp; \texthl{$1$}$01011,011$ &amp;  $ 1$ \\
        $4$ &amp; $1$\texthl{$0$}$1011,011$ &amp; $ 2$ \\
        $3$ &amp; $10$\texthl{$1$}$011,011$ &amp; $ 5$ \\
        $2$ &amp; $101$\texthl{$0$}$11,011$ &amp; $10$ \\
        $1$ &amp; $1010$\texthl{$1$}$1,011$ &amp; $21$ \\
        $0$ &amp; $10101$\texthl{$1$}$,011$ &amp; $43$ \\
        \bottomrule
      \end{tabular*}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{0.45\linewidth}
      \subcaption{partie fractionnaire}
      \begin{tabular*}{\linewidth}{@{\extracolsep{\fill}}ccD{.}{,}{1.3}}
        \toprule
        $i$ &amp; $d_{-i}$ &amp; y \\
        \midrule
        $3$ &amp; $101011,01$\texthl{$1$}   &amp; 0.5   \\
        $2$ &amp; $101011,0$\texthl{$1$}$1$ &amp; 0.75  \\
        $1$ &amp; $101011,$\texthl{$0$}$11$ &amp; 0.375 \\
        \bottomrule
      \end{tabular*}
    \end{minipage}
  \end{table}
\end{exemple}


\begin{exemple}
  Soit le nombre hexadÃ©cimal $\mathrm{AC}2,3\mathrm{D}8$. On peut le
  convertir en base $10$ Ã&nbsp; partir de la dÃ©finition:
  \begin{align*}
    \mathrm{AC}2,3\mathrm{D}8
    &amp;= 10 \times 16^2 + 12 \times 16 + 2 + 3 \times 16^{-1} + 13
    \times 16^{-2} + 8 \times 16^{-3} \\
    &amp;= \nombre{2754,240234375}.
  \end{align*}
  \qed
\end{exemple}


\subsection{Conversion avec des bases gÃ©nÃ©rales}
\label{sec:ordinateurs:conversion:bases_generales}

Il existe de nombreuses bases de numÃ©ration d'usage courant oÃ¹ chaque
symbole est (potentiellement) exprimÃ© dans une base diffÃ©rente. On a
qu'Ã&nbsp; penser Ã&nbsp; l'heure ou Ã&nbsp; l'ensemble du systÃ¨me de mesure impÃ©rial.
Or, il peut s'avÃ©rer utile de savoir convertir de et vers une base
quelconque. Le matÃ©riel de cette section se retrouve dans trÃ¨s peu
d'ouvrages d'analyse numÃ©rique ou de statistique numÃ©rique. Pourtant,
il existe quelques applications intÃ©ressantes de la conversion de et
vers des bases gÃ©nÃ©rales, comme nous le verrons.

On peut gÃ©nÃ©raliser la notion de nombre prÃ©sentÃ©e dans les sections
prÃ©cÃ©dentes Ã&nbsp; une collection de Â«symbolesÂ», chacun dans une base
diffÃ©rente. On restreint la discussion aux entiers sans perte de
gÃ©nÃ©ralitÃ©. On a donc
\begin{displaymath}
  x = x_{m-1}x_{m-2} \cdots x_1x_0,
\end{displaymath}
oÃ¹ $x_{m - 1}$ est un nombre en base $b_{m - 1}$, $x_{m - 2}$ est un
nombre en base $b_{m - 2}$, etc. Nous dirons que le nombre $x$ est
exprimÃ© en base $[b_{m - 1}\; b_{m - 2}\; \dots\; b_0]$. On a alors
\begin{equation}
  \label{eq:ordinateurs:def_base_gen}
  x = \sum_{i = 0}^{m - 1} x_i \prod_{j = -1}^{i - 1} b_j,
\end{equation}
avec $b_{-1} = 1$.

Les algorithmes de conversion \ref{algo:ordinateurs:10_vers_b} et
\ref{algo:ordinateurs:b_vers_10} demeurent essentiellement valides
ici. Il suffit de remplacer chaque mention de $b$ par $b_i$.

\begin{exemple}
  Le jour de l'annÃ©e et l'heure du jour est un Â«nombreÂ» exprimÃ© en
  base $[365\; 24\; 60\; 60]$. En utilisant directement
  l'Ã©quation~\eqref{eq:ordinateurs:def_base_gen}, le nombre de
  secondes correspondant Ã&nbsp; 1~jour, 2~heures, 33~minutes et 20~secondes
  est:
  \begin{align*}
    1 \text{ j } 2 \text{ h } 33 \text{ min } 20 \text{ sec}
    &amp;= 1 \times (24)(60)(60) + 2 \times (60)(60) + 33 \times 60 + 20 \\
    &amp;= \nombre{95600} \text{ secondes}.
  \end{align*}
  Si l'on fait la conversion en sens inverse, le nombre de jours,
  heures, minutes et secondes correspondant Ã&nbsp; \nombre{91492} secondes
  est, en utilisant l'\autoref{algo:ordinateurs:10_vers_b} avec la
  base $[365\; 24\; 60\; 60]$: 1~jour, 1~heure, 24~minutes et
  52~secondes (voir le \autoref{tab:ordinateurs:10_vers_generale} pour
  les calculs).
  \begin{table}
    \caption{Conversion du nombre dÃ©cimal $\nombre{91492}$ dans la
      base gÃ©nÃ©rale $[365\; 24\; 60\; 60]$.}
    \label{tab:ordinateurs:10_vers_generale}
    \centering
    \begin{tabular}{&gt;{$}c&lt;{$}&gt;{$}r&lt;{$}&gt;{$}r&lt;{$}&gt;{$}r&lt;{$}&gt;{$}c&lt;{$}&gt;{$}c&lt;{$}}
      \toprule
      i &amp;
      \multicolumn{1}{c}{$v$} &amp;
      \multicolumn{1}{c}{$b_i$} &amp;
      \lfloor v/b_i \rfloor &amp; v \bmod b_i &amp; x_i \\
      \midrule
      0 &amp; \nombre{91492} &amp;  60 &amp; \nombre{1524} &amp; 52 &amp; 52 \\
      1 &amp;  \nombre{1524} &amp;  60 &amp;           25  &amp; 24 &amp; 24 \\
      2 &amp;            25  &amp;  24 &amp;            1  &amp;  1 &amp;  1 \\
      3 &amp;             1  &amp; 365 &amp;            0  &amp;  1 &amp;  1 \\
      \bottomrule
    \end{tabular}
  \end{table}
  \qed
\end{exemple}

Les bases gÃ©nÃ©rales sont particuliÃ¨rement utiles pour assigner ou
extraire les Ã©lÃ©ments d'une matrice ou d'un tableau dans un ordre non
sÃ©quentiel. Typiquement, l'index de l'Ã©lÃ©ment Ã&nbsp; traiter est le
rÃ©sultat d'un calcul. L'exemple suivant illustre cette idÃ©e.

\begin{exemple}
  \label{ex:ordinateurs:position_dans_matrice}
  Soit $\mathbf{A}$ une matrice $4 \times 5$ que l'on suppose remplie en
  ordre lexicographique (par ligne). Il est simple de dÃ©terminer, ici,
  que le 14{\ieme} Ã©lÃ©ment est $a_{34}$. Or, on observe que la
  conversion du nombre $14 - 1 = 13$ dans la base $[4\; 5]$ donne :
  \begin{align*}
    13 \div 5 &amp;= 2 \text{ reste } 3 \quad\Rightarrow\quad x_0 = 3 \\
     2 \div 4 &amp;= 0 \text{ reste } 2 \quad\Rightarrow\quad x_1 = 2,
   \end{align*}
   soit le Â«nombreÂ» $(2, 3)$. En additionnant $1$ Ã&nbsp; ce rÃ©sultat, on
   obtient prÃ©cisÃ©ment la position du 14{\ieme} Ã©lÃ©ment dans la
   matrice. Les opÃ©rations $-1$ et $+1$ sont rendues nÃ©cessaires par
   le fait que les lignes et les colonnes sont numÃ©rotÃ©es Ã&nbsp; partir de
   $1$, alors que les systÃ¨mes de numÃ©ration dÃ©butent Ã&nbsp; $0$.%
   \qed
\end{exemple}



\section{UnitÃ©s de mesure}
\label{sec:ordinateurs:unites}

Les ordinateurs que nous utilisons couramment fonctionnent en base $2$.
La plus petite quantitÃ© d'information qu'un ordinateur peut traiter
est un \emph{bit} (compression de l'anglais \emph{binary digit}). En
informatique, un bit est Ã©gal Ã&nbsp; \fbox{$0$} ou Ã&nbsp; \fbox{$1$}. Le symbole du
bit est b.

Un \emph{octet} (\emph{byte}) est un groupe de huit bits. Son symbole
est o ou B. L'octet est l'unitÃ© de mesure la plus frÃ©quemment utilisÃ©e
en informatique, en grande partie parce que le codage d'un caractÃ¨re
dans la plupart des langues occidentales requiert un octet; voir la
\autoref{sec:ordinateurs:codage}. Les termes pour de plus grandes
quantitÃ©s de bits ou d'octets utilisent gÃ©nÃ©ralement les prÃ©fixes
usuels du systÃ¨me international d'unitÃ©s. Par exemple:
\begin{itemize}
\item $1$ kilooctet (ko) est $2^{10} = \nombre{1 024}$ octets;
\item $1$ mÃ©gaoctet (Mo) est $2^{20} = \nombre{1 048 576}$ octets;
\item $1$ gigaoctet (Go) est $2^{30} = \nombre{1 073 741 824}$ octets.
\end{itemize}
On voit que cette pratique fort rÃ©pandue entraine des distorsions par
rapport aux dÃ©finitions usuelles de kilo, mÃ©ga, giga, etc., et que
cette distorsion s'amplifie au fur et Ã&nbsp; mesure que l'on grimpe dans
l'Ã©chelle des tailles d'objets. Pour cette raison, on a dÃ©fini les
prÃ©fixes kibi, mÃ©bi, gibi, etc., mais ceux-ci demeurent peu utilisÃ©s Ã&nbsp;
ce jour.

Dans l'industrie de l'informatique, on joue beaucoup avec les unitÃ©s
pour montrer son produit sous un jour favorable. Deux exemples:
\begin{enumerate}
\item Les fournisseurs d'accÃ¨s Internet expriment la vitesse de
  tÃ©lÃ©chargement en Mb/sec, alors que la taille des fichiers est
  gÃ©nÃ©ralement affichÃ©e en octets. Il faut donc diviser par 8 la
  vitesse annoncÃ©e pour avoir une idÃ©e plus juste du temps requis pour
  tÃ©lÃ©charger un fichier.
\item Les fabricants de disques durs divisent la capacitÃ© rÃ©elle de
  leurs disques par $10^9$ pour l'exprimer en gigaoctets. Ainsi, un
  disque dont la capacitÃ© annoncÃ©e est de $100$~Go ne peut contenir, en
  fait, que $100 \times 10^9 \div 2^{30} = 93,132$~Go de donnÃ©es.
  Cette confusion serait Ã©liminÃ©e si les fabricants affichaient plutÃ´t
  une capacitÃ© de $93,132$ gibioctets. Moins vendeur\dots
\end{enumerate}



\section{ReprÃ©sentation en virgule flottante}
\label{sec:ordinateurs:ieee}

Cette section dÃ©crit la maniÃ¨re standard de reprÃ©senter les nombres
rÃ©els dans les ordinateurs d'usage courant. Il est utile de
connaitre les grandes lignes afin de comprendre pourquoi les nombres
rÃ©els n'ont pas tous une reprÃ©sentation exacte dans un ordinateur et
comment surviennent et se propagent les erreurs d'arrondi. L'Ã©tude du
sujet est Ã©galement intÃ©ressante en soi pour constater comment les
ingÃ©nieurs et les informaticiens sont parvenus Ã&nbsp; stocker un maximum
d'information dans un espace limitÃ©.

Tel que mentionnÃ© prÃ©cÃ©demment, la capacitÃ© de stockage d'un
ordinateur, bien que vaste de nos jours, n'en demeure pas moins
limitÃ©e. Par consÃ©quent, les nombres y sont reprÃ©sentÃ©s par un
ensemble de $m$ bits. Habituellement, $m$ est un multiple de $2$ et sa
valeur dÃ©termine le type de nombre. Par exemple, des dÃ©finitions
usuelles sont $m = 2^4 = 16$ pour un entier, $m = 2^5 = 32$ pour un
nombre rÃ©el en simple prÃ©cision (\emph{float} dans plusieurs langages
de programmation) et $m = 2^6 = 64$ pour un nombre rÃ©el en double
prÃ©cision (\emph{double}).

Il existe deux grandes faÃ§ons de reprÃ©senter les nombres (rÃ©els) Ã&nbsp;
l'aide de $m$ bits.
\begin{description}
\item[Virgule fixe] Dans cette reprÃ©sentation, la position de la
  virgule dans le nombre est prÃ©dÃ©terminÃ©e et, par consÃ©quent, n'a pas
  besoin d'Ãªtre conservÃ©e en mÃ©moire. On rÃ©serve alors $m_e$ positions
  pour la partie entiÃ¨re et $m_f$ pour la partie fractionnaire (avec
  $m = m_e + m_f$). La reprÃ©sentation en virgule fixe est
  particuliÃ¨rement utile dans les applications financiÃ¨res.
\item[Virgule flottante] Dans la reprÃ©sentation des nombres en virgule
  flottante, celle-ci peut Ãªtre placÃ©e n'importe oÃ¹ dans le nombre.
  L'Ã©tendue de cette reprÃ©sentation est beaucoup plus grande que la
  virgule fixe, mais ceci au dÃ©triment de la prÃ©cision puisque
  quelques bits doivent Ãªtre rÃ©servÃ©s pour stocker la position de la
  virgule dans le nombre.
\end{description}
La reprÃ©sentation en virgule flottante est celle utilisÃ©e dans les
applications scientifiques et celle sur laquelle nous nous concentrons
dans la suite.

La reprÃ©sentation en virgule flottante est analogue Ã&nbsp; la notation
scientifique. Le nombre rÃ©el $x$ est entiÃ¨rement dÃ©fini par un bit de
signe $S$, un exposant positif $E$ et une mantisse $M$ tel que
\begin{equation}
  \label{eq:ordinateurs:def_floating-point}
  x = (-1)^S \times B^{E - e} \times M,
\end{equation}
oÃ¹ $B$ est la base de la reprÃ©sentation et $e$ est un entier
prÃ©dÃ©terminÃ© appelÃ© le dÃ©calage, ou le biais, de l'exposant. Le
recours au dÃ©calage facilite les calculs internes et Ã©vite de devoir
rÃ©server un autre bit pour le signe de l'exposant en le stockant sous
forme non signÃ©e (c'est-Ã&nbsp;-dire sous forme d'entier positif).

La norme IEEE~754 dÃ©finit la maniÃ¨re standard de reprÃ©senter les
nombres en virgule flottante dans les ordinateurs \citep[][pour une
excellente prÃ©sentation]{IEEE:754,Wikipedia:IEEE754}. En premier lieu,
la norme stipule que la base dans la reprÃ©sentation est $B = 2$. Ceci
est implicite et n'est pas stockÃ© oÃ¹ que ce soit dans l'ordinateur. En
second lieu, la norme suppose que, pour les nombres dits
\emph{normalisÃ©s}, la mantisse est toujours de la forme $M = 1,F$, oÃ¹
$F$ est un entier binaire. Le bit Ã&nbsp; gauche de la virgule est appelÃ© le
\emph{bit cachÃ©} puisqu'il est lui aussi implicite et non stockÃ© dans
l'ordinateur.

Nous dÃ©crivons plus en dÃ©tail la norme pour les nombres rÃ©els en
\emph{double prÃ©cision} puisque c'est le type avec lequel R travaille
toujours\footnote{%
  \label{pg:arithmetique:entiers} Il est possible de crÃ©er des vrais
  entiers dans R en ajoutant un suffixe \code{L} Ã&nbsp; un nombre entier.
  Ainsi, \code{1L} est un nombre entier dans le sens oÃ¹
  \code{is.integer(1L)} est \code{TRUE}. Cela est relativement peu
  utilisÃ© en programmation normale.}. %
Tout d'abord, un nombre en double prÃ©cision est stockÃ© dans un mot de
$m = 64$~bits (8~octets) divisÃ© ainsi de gauche Ã&nbsp; droite: $m_S = 1$ bit
pour le signe, $m_E = 11$ bits pour l'exposant et $m_F = 52$ bits pour
la partie fractionnaire de la mantisse. Le premier bit du mot utilisÃ©
pour le signe est appelÃ© le \emph{bit fort}. Voir la
\autoref{fig:ordinateurs:double} pour une reprÃ©sentation
schÃ©matique.

\begin{figure}
  \centering
  \begin{equation*}
    \underbrace{
      \underbrace{\fbox{\hspace{0.5pt} $S$ \hspace{0.5pt}}}_{m_S = 1}
      \hspace{1pt}
      \underbrace{\fbox{\hspace{17.5pt} $E$ \hspace{17.5pt}}}_{m_E = 11}
      \hspace{1pt}
      \underbrace{\fbox{\hspace{78pt} $F$ \hspace{78pt}}}_{m_F = 52}%
    }_{m = 64}
  \end{equation*}
  \caption{ReprÃ©sentation schÃ©matique d'un nombre en double prÃ©cision
    dans la norme IEEE~754.}
  \label{fig:ordinateurs:double}
\end{figure}

On remarque que le bit cachÃ© confÃ¨re Ã&nbsp; la mantisse une longueur de mot
effective (ou prÃ©cision) de 53~bits.

Le dÃ©calage est $e = 2^{m_e - 1} - 1 = 2^{10} - 1 = \nombre{1023}$.
Avec une longueur de mot de 11~bits, les valeurs possibles de $E$ vont
de $0$ Ã&nbsp; $2^{11} - 1 = \nombre{2047}$. Cependant, les valeurs $0$ et
$\nombre{2047}$ sont rÃ©servÃ©es pour des usages spÃ©ciaux; voir le
\autoref{tab:ordinateurs:special_values}. Par consÃ©quent, les
valeurs possibles de l'exposant (une fois dÃ©calÃ©) pour les nombres en
double prÃ©cision vont de $-\nombre{1022}$ Ã&nbsp; $\nombre{1023}$.

\begin{table}
  \caption{Valeurs spÃ©ciales dans la norme IEEE~754}
  \label{tab:ordinateurs:special_values}
  \begin{tabular}{crccc}
    \toprule
    $S$ &amp;
    \multicolumn{1}{c}{$E$} &amp;
    $F$ &amp; ReprÃ©sentation binaire &amp; Valeur spÃ©ciale \\
    \midrule
    $0$ &amp; $0$ &amp; $0$ &amp;
      \ieee{0}{00000000000}{00 \cdots 00} &amp; $0$ \\
    $1$ &amp; $0$ &amp; $0$ &amp;
      \ieee{1}{00000000000}{00 \cdots 00} &amp; $-0$ \\
    $0$ &amp; $\nombre{2047}$ &amp; $0$ &amp;
      \ieee{0}{11111111111}{00 \cdots 00} &amp; $+\infty$ \\
    $1$ &amp; $\nombre{2047}$ &amp; $0$ &amp;
      \ieee{1}{11111111111}{00 \cdots 00} &amp; $-\infty$ \\
    $0 \text{ ou } 1$ &amp; $\nombre{2047}$ &amp; $F \neq 0$ &amp;
      \ieee{$S$}{11111111111}{\hspace{1.2em} $F$ \hspace{1.2em}} &amp;
      \code{NaN}$^a$ \\
    \bottomrule
  \end{tabular} \\
  $^a$ \emph{Not a number}, par exemple $\frac{0}{0}$
  ou $\frac{\infty}{\infty}$.
\end{table}

\begin{exemple}
  Tel qu'expliquÃ© Ã&nbsp; la
  \autoref{sec:ordinateurs:conversion:10_vers_b}, le nombre
  $\frac{1}{2}$ possÃ¨de une reprÃ©sentation binaire exacte:
  \begin{align*}
    \frac{1}{2}
    &amp;= 2^{-1} \\
    &amp;= (-1)^0 \times 2^{\nombre{1022} - \nombre{1023}} \times 1,0.
  \end{align*}
  Puisque la reprÃ©sentation de l'exposant est $\nombre{1022}_{10} =
  1111111110_2$, la reprÃ©sentation interne de $\frac{1}{2}$ selon la
  norme IEEE~754 est
  \begin{center}
    \ieee{0}{01111111110}{00 \cdots 00}.
  \end{center}

  En revanche, le nombre $\frac{1}{10}$ n'a pas une reprÃ©sentation
  binaire finie. En utilisant
  l'\autoref{algo:ordinateurs:10_vers_b}, on trouve (le cÃ´tÃ©
  droit de l'Ã©galitÃ© Ã©tant en binaire):
  \begin{align*}
    \frac{1}{10}
    &amp;= 0,0001100110011001100110011001\dots \\
    &amp;= 2^{-4} \times 1,1001100110011001\dots \\
    &amp;= (-1)^0 \times 2^{\nombre{1019} - \nombre{1023}} \times
    1,1001100110011001\dots
  \end{align*}
  Or, $\nombre{1019}_{10} = 1111111011_2$, d'oÃ¹ la reprÃ©sentation
  interne finie de $\frac{1}{10}$ est
  \begin{center}
    \ieee{0}{01111111011}{1001 \cdots 1001}.
  \end{center}
  Si l'on reconvertit ce nombre en dÃ©cimal, on obtient
  \begin{equation*}
    2^{-4} \times
    \left(
      1 + \sum_{k = 0}^{12} (2^{-4k - 1} + 2^{-4k - 4})
    \right),
  \end{equation*}
  un nombre prÃ¨s de, mais pas exactement Ã©gal Ã&nbsp;, $\frac{1}{10}$ (le
  programme de calcul en multiprÃ©cision \code{bc} donne
  $0,09999999999999999166$). DÃ¨s lors, la multiplication de ce nombre
  par $10$ ne donnera pas $1$. VoilÃ&nbsp; qui justifie le principe de
  programmation Ã©noncÃ© Ã&nbsp; la page \pageref{programming_principle}.%
  \qed
\end{exemple}

Les principales caractÃ©ristiques des nombres en double prÃ©cision sont
les suivantes.
\begin{enumerate}
\item Soit $x_{\text{max}}$ le plus grand nombre reprÃ©sentable. Parce
  que l'exposant $E = \nombre{2047}$ est rÃ©servÃ©, on a
  \begin{align*}
    x_{\text{max}}
    &amp;= \ieee{0}{11111111110}{11 \cdots 11} \\
    &amp;= (-1)^0 \times 2^{\nombre{1023}} \times 1,11\cdots11 \\
    &amp;= 2^{\nombre{1023}} \times (2 - 2^{-52}) \\
    &amp;= \nombre{1,797693} \times 10^{308}.
  \end{align*}
\item Soit $x_{\text{min}}$ le plus petit nombre normalisÃ©
  reprÃ©sentable. Parce que l'exposant $E = 0$ est rÃ©servÃ©, on a
  \begin{align*}
    x_{\text{min}}
    &amp;= \ieee{0}{00000000001}{00 \cdots 00} \\
    &amp;= (-1)^0 \times 2^{\nombre{-1022}} \times 1,00\cdots00 \\
    &amp;= 2^{\nombre{-1022}} \\
    &amp;= \nombre{2,225074} \times 10^{-308}.
  \end{align*}
  Afin de rendre la transition vers $0$ moins abrupte, la norme
  IEEE~754 dÃ©finit Ã©galement des nombres \emph{dÃ©normalisÃ©s}. Ceux-ci
  sont identifiÃ©s par $E = 0$ et une partie fractionnaire $F$ non
  nulle. Cependant, par dÃ©finition, les nombres dÃ©normalisÃ©s ont $E -
  e = -\nombre{1022}$ et leur bit cachÃ© est $0$. Par consÃ©quent, le
  plus petit nombre dÃ©normalisÃ© est stockÃ© sous la forme
  \begin{equation*}
    \ieee{0}{00000000000}{00 \cdots 01}
  \end{equation*}
  et sa valeur est
  \begin{align*}
    x_{\text{min}}
    &amp;= (-1)^0 \times 2^{\nombre{-1022}} \times 0,00\cdots01 \\
    &amp;= 2^{\nombre{-1022}} \times 2^{-52} \\
    &amp;= 2^{-\nombre{1074}} \\
    &amp;= \nombre{4,940656} \times 10^{-324}.
  \end{align*}
\item On a la mÃªme Ã©tendue pour les nombres nÃ©gatifs, soit
  \begin{gather*}
    [\nombre{-1,797693} \times 10^{308},\,
     \nombre{-2,225074} \times 10^{-308}] \\
    \intertext{ou}
    [\nombre{-1,797693} \times 10^{308},\,
     \nombre{-4,940656} \times 10^{-324}].
  \end{gather*}
  en considÃ©rant les nombres dÃ©normalisÃ©s.
\item Soit $\varepsilon$ la plus petite valeur tel que $1 +
  \varepsilon \neq 1$ dans la reprÃ©sentation en virgule flottante.
  Cette valeur est appelÃ©e l'\emph{epsilon de la machine} ou la
  \emph{prÃ©cision de la machine}. Or, puisque
  \begin{equation*}
    1 = (-1)^0 \times 2^0 \times 1,00\cdots00,
  \end{equation*}
  le nombre suivant est
  \begin{equation*}
    (-1)^0 \times 2^0 \times 1,00\cdots01.
  \end{equation*}
  Par consÃ©quent, on a $\varepsilon = 2^{-52} = \nombre{2,220446}
  \times 10^{-16}$.
\item Tout nombre $x$ reprÃ©sente en fait un intervalle de
  $\mathbb{R}$. Par exemple, tout nombre dans l'intervalle $[1, 1 +
  \varepsilon)$ est reprÃ©sentÃ© par le nombre $1$ dans l'ordinateur.
\item On a un ensemble fini de nombres pour reprÃ©senter $\mathbb{R}$.
  Or, cet ensemble est plus dense prÃ¨s de $0$ que pour les grandes
  valeurs. En effet, le nombre suivant $x_{\text{min}}$ est
  \begin{align*}
    x_{\text{min}}^+
    &amp;= (1 + \varepsilon) \times 2^{-\nombre{1022}} \\
    &amp;= x_{\text{min}} + \varepsilon \times 2^{-\nombre{1022}} \\
    &amp;= x_{\text{min}} + 2^{-\nombre{1074}}, \\
    \intertext{alors que le nombre prÃ©cÃ©dant $x_{\text{max}}$ est}
    x_{\text{max}}^-
    &amp;= (2 - 2^{-52} - \varepsilon) \times 2^{\nombre{1023}} \\
    &amp;= x_{\text{max}} - \varepsilon \times 2^{\nombre{1023}} \\
    &amp;= x_{\text{max}} - 2^{971}.
  \end{align*}
  L'Ã©cart entre les deux plus petits nombres reprÃ©sentables est donc de
  $2^{-\nombre{1024}} \approx 10^{-324}$, alors que celui entre les deux plus
  grands est de $2^{971} \approx 10^{292}$!
\end{enumerate}

Tout calcul impliquant un nombre $x &gt; x_{\text{max}}$ ($x &lt;
-x_{\text{max}}$) entraine un \emph{dÃ©passement de capacitÃ©}.
Habituellement, cela entraine l'arrÃªt immÃ©diat des calculs et un
rÃ©sultat de $+\infty$ ($-\infty$). Ã€ l'autre bout du spectre, un
calcul impliquant un nombre $x &lt; x_{\text{min}}$ entraine un
\emph{soupassement de capacitÃ©} et le rÃ©sultat est habituellement
considÃ©rÃ© Ã©gal Ã&nbsp; $0$.

R conserve dans une liste nommÃ©e \code{.Machine} les
valeurs mentionnÃ©es ci-dessus --- ainsi que plusieurs autres --- pour
l'architecture de l'ordinateur courant. Par exemple, on confirme les
valeurs de $\varepsilon_m$, $x_{\text{min}}$, $x_{\text{max}}$, $B$,
$m_f$ et $m_e$, dans l'ordre, pour l'architecture x86:
\begin{Schunk}
\begin{Sinput}
&gt; .Machine[c(1, 3:6, 11)]
\end{Sinput}
\begin{Soutput}
$double.eps
[1] 2.220446e-16

$double.xmin
[1] 2.225074e-308

$double.xmax
[1] 1.797693e+308

$double.base
[1] 2

$double.digits
[1] 53

$double.exponent
[1] 11
\end{Soutput}
\end{Schunk}



\section{Ã‰lÃ©ments d'arithmÃ©tique en virgule flottante}
\label{sec:ordinateurs:arithmetique}

La section prÃ©cÃ©dente expliquait pourquoi les nombres stockÃ©s dans un
ordinateur ne sont pas toujours ceux que l'on croit --- ou que l'on
voudrait. Puisque l'ordinateur ne peut reprÃ©senter tous les nombres
rÃ©els, toute opÃ©ration arithmÃ©tique avec des nombres en virgule
flottante implique une erreur d'arrondi ou de troncature (selon
l'architecture de l'ordinateur) dont il importe de tenir compte lors
de la mise en oeuvre de certains algorithmes. Cette section prÃ©sente
quelques grands principes d'arithmÃ©tique en virgule flottante ainsi
que de bons usages pour minimiser les erreurs d'arrondi. Consulter les
ouvrages
\cite{Monahan:numstat:2001,Burden:numerical:2011,Knuth:ACP:vol2:1997},
entre autres, pour une discussion plus complÃ¨te de ce vaste sujet.

Aux fins de cette section, on note $\fl(x)$ la reprÃ©sentation en
virgule flottante du nombre nombre $x$ et l'on dÃ©finit la
reprÃ©sentation simplifiÃ©e
\begin{equation}
  \label{eq:ordinateurs:fl(x)}
  \fl(x) = (-1)^S \times 10^E \times 0,F,
\end{equation}
oÃ¹ $F$ compte cinq chiffres significatifs, dont le dernier est arrondi.
Le \autoref{tab:arithmetic:simplified} fournit quelques exemples.

\begin{table}
  \caption{ReprÃ©sentation en virgule flottante simplifiÃ©e}
  \label{tab:arithmetic:simplified}
  \centering
  \begin{tabular}{r@{,}lr@{,}l}
    \toprule
    \multicolumn{2}{c}{$x$} &amp;
    \multicolumn{2}{c}{$\fl(x)$} \\
    \midrule
    $2$&amp;$5$       &amp; $0$&amp;$25000 \times 10^1$ \\
    $-42$&amp;$182$  &amp; $-0$&amp;$42182 \times 10^2$ \\
    $0$&amp;$214356$ &amp; $0$&amp;$21436 \times 10^0$ \\
    \bottomrule
  \end{tabular}
\end{table}

\begin{rem}
  Dans la norme IEEE~754, les rÃ¨gles d'arrondi de base sont:
  \begin{enumerate}
  \item arrondir Ã&nbsp; la valeur la plus prÃ¨s ($0,14$ devient $0,1$ et
    $\nombre{0,16}$ devient $0,2$);
  \item arrondir un nombre exactement Ã&nbsp; mi-chemin au nombre avec un
    dernier chiffre significatif pair ou nul ($0,05$ devient $0,0$
    alors que $\nombre{0,15}$ devient $0,2$).
  \end{enumerate}
\end{rem}


\subsection{Erreurs d'arrondi ou de troncature}
\label{sec:ordinateurs:arithmetique:erreurs}

Lors de l'addition et de la soustraction de nombres en virgule
flottante, on rend les exposants Ã©gaux en dÃ©plaÃ§ant les bits de la
mantisse du plus petit nombre vers la droite. Il en rÃ©sulte une perte
de bits significatifs et donc une \emph{erreur d'arrondi}. Dans les
cas extrÃªmes oÃ¹ les deux opÃ©randes sont de grandeur trÃ¨s diffÃ©rente,
le plus petit opÃ©rande devient nul suite Ã&nbsp; la perte de tous ses bits
significatifs.

La situation pour la multiplication et la division est quelque peu
diffÃ©rente, mais la source d'erreur d'arrondi demeure la mÃªme.

Ã€ toute fin pratique, tout calcul fait naitre de l'erreur d'arrondi et
celle-ci augmente avec le nombre d'opÃ©rations. Les quelques principes
de programmation ci-dessous, lorsque suivis par le programmeur prudent
et consciencieux, permettent d'attÃ©nuer l'impact de l'erreur
d'arrondi.

\begin{enumerate}
\item L'addition et la soustraction en virgule flottante ne sont pas
  associatives. Additionner les nombres en ordre croissant de grandeur
  afin d'accumuler des bits significatifs.
\item Ã‰viter de soustraire un petit nombre d'un grand, ou alors le
  faire le plus tard possible dans la chaine des calculs.
\item Pour calculer une somme alternÃ©e, additionner tous les termes
  positifs et tous les termes nÃ©gatifs, puis faire la soustraction.
\item Multiplier et diviser des nombres d'un mÃªme ordre de grandeur.
  Si $x$ et $y$ sont presque Ã©gaux, le calcul $x/y$ sera plus prÃ©cis
  en virgule flottante que $y^{-1} x$.
\end{enumerate}

Les exemples ci-dessous illustrent ces principes.

\begin{exemple}
  Soit $x = 7$, $y = 4$ et $z = \nombre{100000}$. Dans la
  reprÃ©sentation simplifiÃ©e \eqref{eq:ordinateurs:fl(x)}, on a $\fl(x)
  = 0,70000 \times 10^1$, $\fl(y) = 0,40000 \times 10^1$ et $\fl(z) =
  0,10000 \times 10^6$. Or, $x + y + z = \nombre{100011}$ et
  \begin{align*}
    [\fl(x) + \fl(y)] + \fl(z)
    &amp;= (0,70000 \times 10^1 + 0,40000 \times 10^1)
    + 0,10000  \times 10^6 \\
    &amp;= 0,11000 \times 10^2 + 0,10000 \times 10^6 \\
    &amp;= 0,00001 \times 10^6 + 0,10000 \times 10^6 \\
    &amp;= 0,10001 \times 10^6, \\
    \intertext{soit un rÃ©sultat raisonnablement prÃ©cis. Cependant,}
    \fl(x) + [\fl(y) + \fl(z)]
    &amp;= 0,70000 \times 10^1
    + (0,00000 \times 10^6 + 0,10000 \times 10^6) \\
    &amp;= 0,00000 \times 10^6 + 0,10000 \times 10^6 \\
    &amp;= 0,10000 \times 10^6.
  \end{align*}
  En effectuant les opÃ©rations dans un mauvais ordre, on obtient $x +
  y + z = z$ mÃªme si $x \neq 0$ et $y \neq 0$. %
  \qed
\end{exemple}

\begin{exemple}
  Soit $x = 7$, $y = \nombre{100006}$ et $z = \nombre{100002}$. On a
  $z - y - x = -11$. Or,
  \begin{align*}
    \fl(z) - [\fl(y) + \fl(x)]
    &amp;= 0,10000 \times 10^6
    - (0,10000 \times 10^6 + 0,00000 \times 10^6) \\
    &amp;= 0,00000 \times 10^0,
    \intertext{alors que}
    [\fl(z) - \fl(y)] - \fl(x)
    &amp;= (0,10000 \times 10^6 - 0,10000 \times 10^6) -
    0,70000 \times 10^1 \\
    &amp;= 0,00000 \times 10^1 - 0,70000 \times 10^1 \\
    &amp;= -0,70000 \times 10^1.
  \end{align*}
  \qed
\end{exemple}

L'exemple suivant est adaptÃ© de \cite{Monahan:numstat:2001}.

\begin{exemple}
  L'Ã©valuation numÃ©rique de probabilitÃ©s loin dans les queues d'une
  fonction de rÃ©partition peut s'avÃ©rer imprÃ©cise selon la technique
  employÃ©e. Par exemple, la fonction de rÃ©partition de la distribution
  logistique est
  \begin{equation*}
    F(x) = (1 + e^{-x})^{-1}.
  \end{equation*}
  La vraie valeur de $\operatorname{Pr}[X &gt; 6]$ est $1 - F(6) = 1 - (1
  + e^{-6})^{-1} = \nombre{0,002472623}$. L'Ã©valuation de cette
  probabilitÃ© dans notre reprÃ©sentation en virgule flottante avec la
  formule ci-dessus est
  \begin{align*}
    1 - [1 \div (1 + \fl(e^{-6}))]
    &amp;= 1 - [1 \div (1 + 0,24788 \times 10^{-2})] \\
    &amp;= 1 - [0,10000 \times 10^1 \div 0,10025 \times 10^1)] \\
    &amp;= 1 - 0,99751 \times 10^0 \\
    &amp;= 0,10000 \times 10^1 - 0,09975 \times 10^1 \\
    &amp;= 0,25000 \times 10^{-2}.
  \end{align*}
  (Nous n'avons pas Ã©crit les entiers en virgule flottante ci-dessus
  pour allÃ©ger la notation.) Toutefois, si l'on utilise plutÃ´t la
  formule Ã©quivalente
  \begin{align*}
    1 - F(6)
    &amp;= \frac{e^{-6}}{1 + e^{-6}} \\
    &amp;= \frac{1}{1 + e^6}
  \end{align*}
  dans laquelle l'opÃ©ration de soustraction entre deux nombres presque
  Ã©gaux est dÃ©jÃ&nbsp; effectuÃ©e, on obtient le rÃ©sultat bien plus prÃ©cis
  \begin{align*}
    1 \div (1 + \fl(e^6))
    &amp;= 1 \div (1 + 0,40343 \times 10^3)) \\
    &amp;= 1 \div (0,00100 \times 10^3 + 0,40343 \times 10^3) \\
    &amp;= 1 \div 0,40443 \times 10^3 \\
    &amp;= 0,24726 \times 10^{-2}.
  \end{align*}
  \qed
\end{exemple}

Les deux principes ci-dessous permettent d'Ã©viter des dÃ©passements ou
des soupassements de capacitÃ© et d'amÃ©liorer la prÃ©cision des calculs.

\begin{enumerate}
\item Chercher des formules mathÃ©matiques Ã©quivalentes Ã©vitant de
  devoir traiter des trÃ¨s grands ou des trÃ¨s petits nombres.
\item Travailler en Ã©chelle logarithmique. Par exemple, le produit de
  deux grands nombres $x$ et $y$ dÃ©passera la capacitÃ© plus tard et
  demeurera prÃ©cis plus longtemps s'il est calculÃ© sous la forme
  $e^{\log x + \log y}$.
\end{enumerate}

\begin{exemple}
  Soit $X_1, \dots, X_n$ un Ã©chantillon alÃ©atoire tirÃ© d'une
  distribution de Pareto translatÃ©e, dont la fonction de rÃ©partition est
  \begin{equation*}
    F(x; \mu, \alpha) = 1 -
    \left(
      \frac{\mu}{x}
    \right)^{\alpha}, \quad x &gt; \mu.
  \end{equation*}
  On peut dÃ©montrer que l'estimateur du maximum de vraisemblance de
  $\alpha$ est
  \begin{equation*}
    \hat{\alpha} = \frac{n}{\ln (X_1 \cdots X_n/X_{(1)}^n)},
  \end{equation*}
  oÃ¹ $X_{(1)} = \min (X_1, \dots, X_n)$. Soit \code{x} un objet R
  contenant un Ã©chantillon de $\nombre{1000}$ valeurs d'une distribution
  Pareto translatÃ©e de moyenne $\nombre{5000}$ (le contenu de cet objet
  n'est pas affichÃ© ici pour des raisons Ã©videntes). Le calcul de
  l'estimateur $\hat{\alpha}$ directement par la formule entraine
  rapidement un dÃ©passement de capacitÃ©, tant lors du produit $X_1
  \cdots X_n$ que lors de l'opÃ©ration $X_{(1)}^n$:
\begin{Schunk}
\begin{Sinput}
&gt; prod(x)
\end{Sinput}
\begin{Soutput}
[1] Inf
\end{Soutput}
\begin{Sinput}
&gt; min(x)^length(x)
\end{Sinput}
\begin{Soutput}
[1] Inf
\end{Soutput}
\end{Schunk}
  Le rÃ©sultat est donc \code{NaN}:
\begin{Schunk}
\begin{Sinput}
&gt; length(x)/log(prod(x)/min(x)^length(x))
\end{Sinput}
\begin{Soutput}
[1] NaN
\end{Soutput}
\end{Schunk}
  Selon la grandeur des donnÃ©es dans l'Ã©chantillon, la formule
  Ã©quivalente
  \begin{displaymath}
    \hat{\alpha} = \frac{n}{\ln \prod_{i = 1}^n X_i/X_{(1)}}
  \end{displaymath}
  peut Ã©viter le dÃ©passement de capacitÃ©. Elle n'est toutefois d'aucun
  secours dans le prÃ©sent exemple:
\begin{Schunk}
\begin{Sinput}
&gt; length(x)/log(prod(x/min(x)))
\end{Sinput}
\begin{Soutput}
[1] 0
\end{Soutput}
\end{Schunk}
  On remarquera de plus que cette approche nÃ©cessite un grand nombre
  de multiplications (voir la
  \autoref{sec:ordinateurs:arithmetique:cout}), en plus d'ouvrir
  la porte Ã&nbsp; des erreurs d'arrondi.

  Pour obtenir une rÃ©ponse on utilisera plutÃ´t une autre formule
  algÃ©briquement Ã©quivalente:
  \begin{displaymath}
    \hat{\alpha} = \frac{n}{\sum_{i=1}^n \ln X_i - n \ln X_{(1)}}.
  \end{displaymath}
  On obtient alors
\begin{Schunk}
\begin{Sinput}
&gt; length(x)/(sum(log(x)) - length(x) * log(min(x)))
\end{Sinput}
\begin{Soutput}
[1] 1.405529
\end{Soutput}
\end{Schunk}
  Cet exemple illustre combien des calculs \emph{algÃ©briquement}
  Ã©quivalents ne sont pas nÃ©cessairement \emph{numÃ©riquement}
  Ã©quivalents. %
  \qed
\end{exemple}


\subsection{Cout des opÃ©rations}
\label{sec:ordinateurs:arithmetique:cout}

Les ordinateurs modernes disposent d'une unitÃ© de calcul en virgule
flottante (FPU) intÃ©grÃ©e au processeur. Cette unitÃ© est Ã©videmment
trÃ¨s optimisÃ©e et, par consÃ©quent, elle accÃ©lÃ¨re beaucoup le calcul en
virgule flottante. NÃ©anmoins, certaines opÃ©rations sont plus couteuses
Ã&nbsp; rÃ©aliser que d'autres en termes de temps de calcul. Ã€ titre
indicatif, on trouve au \autoref{tab:ordinateurs:cout} le cout
relatif approximatif de quelques opÃ©rations en virgule flottante.
\begin{table}
  \centering
  \caption{Cout relatif de quelques opÃ©rations en virgule flottante}
  \label{tab:ordinateurs:cout}
  \begin{tabular}{lr}
    \toprule
    OpÃ©ration arithmÃ©tique &amp; Cout relatif \\
    \midrule
    Addition et soustraction &amp; $1,0$ \\
    Multiplication           &amp; $1,3$ \\
    Division                 &amp; $3,0$ \\
    Racine carrÃ©e            &amp; $4,0$ \\
    Logarithme               &amp; $15,4$ \\
    \bottomrule
  \end{tabular}
\end{table}

Ã€ titre d'exemple, considÃ©rons le calcul d'une simple moyenne
arithmÃ©tique
\begin{equation*}
  \bar{x} = \frac{1}{n} \sum_{i = 1}^n x_i.
\end{equation*}
Si l'on effectue le calcul tel qu'Ã©crit ci-dessus, cela requiert $n -
1$ additions et une division. En revanche, le calcul Ã©quivalent
\begin{equation*}
  \bar{x} = \sum_{i = 1}^n \frac{x_i}{n},
\end{equation*}
requiert $n - 1$ divisions et $n - 1$ additions. Pour $n$ grand
utiliser la premiÃ¨re approche plutÃ´t que la seconde fera une
diffÃ©rence.



\section{Codage de caractÃ¨res}
\label{sec:ordinateurs:codage}

Pendant que l'on discute de la reprÃ©sentation interne des nombres dans
un ordinateur, on peut toucher un mot de la reprÃ©sentation interne, ou
le codage, des caractÃ¨res. Ce sujet demeure une cible mouvante puisque
de nouveaux standards apparaissent encore aprÃ¨s de nombreuses annÃ©es
de systÃ¨mes incompatibles et basÃ©s sur la langue anglaise.

Peu importe le systÃ¨me retenu, les caractÃ¨res doivent Ãªtre codÃ©s en
binaire dans l'ordinateur. La partie la plus difficile consiste Ã&nbsp;
crÃ©er un systÃ¨me standard permettant aux ordinateurs et autres
appareils numÃ©riques de communiquer entre eux. Le premier standard
d'usage courant fut le Code amÃ©ricain normalisÃ© pour l'Ã©change
d'information, mieux connu sous son acronyme ASCII \citep{ASCII}. La
norme ASCII dÃ©finit des codes numÃ©riques pour 128 caractÃ¨res, soit 95
affichables (lettres, chiffres, symboles divers et l'espace) et 33 non
affichables (essentiellement des caractÃ¨res de contrÃ´le tels que saut
de ligne, retour de chariot ou espacement arriÃ¨re).

Ã€ titre d'exemple, les lettres majuscules A--Z occupent les cases
$65$--$90$ ($1000001$--$1011010$ en binaire) alors que les lettres
minuscules a--z occupent les cases $97$--$122$ ($1100001$--$1101010$
en binaire). On constate que les versions majuscule et minuscule d'une
mÃªme lettre ne diffÃ¨rent, dans leur reprÃ©sentation binaire, que par
leur second bit le plus significatif. Le changement de casse d'une
lettre ou d'un mot est donc une opÃ©ration trÃ¨s simple et rapide.

La reprÃ©sentation ASCII ne requiert en soi que sept bits. NÃ©anmoins,
on a rapidement codÃ© les caractÃ¨res sur un octet (huit bits) puisqu'il
s'agit du type de donnÃ©e natif des ordinateurs depuis les annÃ©es 1970.
L'ajout d'un bit a crÃ©Ã© de l'espace pour 128 caractÃ¨res additionnels
(cases 128--255). Une myriade de systÃ¨mes de codage diffÃ©rents sont
alors apparus pour supporter les caractÃ¨res des langues autres que
l'anglais (les caractÃ¨res accentuÃ©s, par exemple) ainsi que d'autres
symboles graphiques. La norme ISO~8859-1, ou Latin~1
\citep{ISO:8859-1}, a fini par s'imposer comme l'un des standards les
plus rÃ©pandus. Ces listes de codes fixes se rÃ©vÃ¨lent toutefois
problÃ©matiques lors de l'apparition d'un nouveau symbole. Par exemple,
pour faire de la place pour le symbole de l'euro Ã&nbsp; la fin des annÃ©es
1990, il a fallu retirer un symbole de ISO~8859-1. Avec quelques
autres changements, la nouvelle liste de code est devenue ISO~8859-15.
De plus, comment doit-on traiter les langues CJC (chinois, japonais,
corÃ©en) qui comptent des milliers de symboles diffÃ©rents?

Depuis le dÃ©but des annÃ©es 1990, la mondialisation de l'informatique a
suscitÃ© un effort concertÃ© de crÃ©ation d'un systÃ¨me de codage standard
couvrant la presque totalitÃ© des systÃ¨mes d'Ã©criture du monde. Le
systÃ¨me devait aussi permettre la composition de textes en plusieurs
langues, par exemple en franÃ§ais et dans une Ã©criture de droite Ã&nbsp;
gauche comme l'hÃ©breu ou l'arabe. Le standard ainsi crÃ©Ã© est Unicode
\citep{Unicode:5.0}. Le plus populaire systÃ¨me de codage capable de
reprÃ©senter l'ensemble des caractÃ¨res Unicode est \emph{Unicode
  Transformation Format} 8~bits, ou UTF-8 \citep[section
3.9]{Unicode:5.0}. Dans l'UTF-8, chaque caractÃ¨re est codÃ© sur une
suite d'un Ã&nbsp; quatre octets et les premiers 128 caractÃ¨res sont
identiques Ã&nbsp; la norme ASCII. L'UTF-8 est le systÃ¨me de codage par
dÃ©faut dans macOS et les plus rÃ©centes distributions GNU/Linux.

Le systÃ¨me R supporte les caractÃ¨res multi-octets de maniÃ¨re assez
exhaustive. Sans doute aidÃ©s en cela par le fait qu'il s'agit d'un
projet international, les dÃ©veloppeurs de R ont mis beaucoup d'effort
pour assurer l'internationalisation et la localisation du logiciel;
voir \cite{Ripley:Rnews:2005a}.

\bibliography{exercices}  % production de la bibliographie

\end{document}
</pre></body></html>