diff options
Diffstat (limited to 'info/formation-latex-ul/doc/exercice-demo.tex')
-rw-r--r-- | info/formation-latex-ul/doc/exercice-demo.tex | 1354 |
1 files changed, 1354 insertions, 0 deletions
diff --git a/info/formation-latex-ul/doc/exercice-demo.tex b/info/formation-latex-ul/doc/exercice-demo.tex new file mode 100644 index 0000000000..0aac11bace --- /dev/null +++ b/info/formation-latex-ul/doc/exercice-demo.tex @@ -0,0 +1,1354 @@ +\documentclass[letterpaper,11pt,english,french]{memoir} + \usepackage{natbib} + \usepackage{babel} + \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 + \RequirePackage[babel=true]{microtype} + \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 à 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 à 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, à 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 à exprimer +des nombres. L'humain s'est habitué à 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-à-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} + &= 1 \times 2^8 + 0 \times 2^7 + 1 \times 2^6 \\ + &\phantom{=} + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 \\ + &\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'à 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 à théorique), l'espace +disponible pour stocker un nombre est fini, c'est-à-dire que $m < +\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}} + &= \sum_{i = 0}^{m - 1} (b - 1) b^i \\ + &= (b - 1) \sum_{i = 0}^{m - 1} b^i \\ + &= (b - 1) + \left( + \frac{b^m - 1}{b - 1} + \right) \\ + &= 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 + &= x_{m-1}x_{m-2} \cdots x_1x_0,x_{-1}x_{-2} \cdots x_{-n} \\ + &= \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 à $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'à 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 à $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'à 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 à $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 à + 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$ & \multicolumn{1}{c}{$v$} & $\lfloor v/2 \rfloor$ & $v \bmod 2$ & $x_i$ \\ + \midrule + $0$ & $23$ & $11$ & $1$ & $1$ \\ + $1$ & $11$ & $5$ & $1$ & $1$ \\ + $2$ & $5$ & $2$ & $1$ & $1$ \\ + $3$ & $2$ & $1$ & $0$ & $0$ \\ + $4$ & $1$ & $0$ & $1$ & $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$ & $v$ & $2v$ & $\lfloor 2v \rfloor$ & $x_{-i}$ \\ + \midrule + $1$ & $0,31$ & $0,62$ & $0$ & $0$ \\ + $2$ & $0,62$ & $1,24$ & $1$ & $1$ \\ + $3$ & $0,24$ & $0,48$ & $0$ & $0$ \\ + $4$ & $0,48$ & $0,96$ & $0$ & $0$ \\ + $5$ & $0,96$ & $1,92$ & $1$ & $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 à + 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 à +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 à 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$ & $d_i$ & $x$ \\ + \midrule + $5$ & \texthl{$1$}$01011,011$ & $ 1$ \\ + $4$ & $1$\texthl{$0$}$1011,011$ & $ 2$ \\ + $3$ & $10$\texthl{$1$}$011,011$ & $ 5$ \\ + $2$ & $101$\texthl{$0$}$11,011$ & $10$ \\ + $1$ & $1010$\texthl{$1$}$1,011$ & $21$ \\ + $0$ & $10101$\texthl{$1$}$,011$ & $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$ & $d_{-i}$ & y \\ + \midrule + $3$ & $101011,01$\texthl{$1$} & 0.5 \\ + $2$ & $101011,0$\texthl{$1$}$1$ & 0.75 \\ + $1$ & $101011,$\texthl{$0$}$11$ & 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$ à partir de la définition: + \begin{align*} + \mathrm{AC}2,3\mathrm{D}8 + &= 10 \times 16^2 + 12 \times 16 + 2 + 3 \times 16^{-1} + 13 + \times 16^{-2} + 8 \times 16^{-3} \\ + &= \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'à penser à l'heure ou à 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 à 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 à 1~jour, 2~heures, 33~minutes et 20~secondes + est: + \begin{align*} + 1 \text{ j } 2 \text{ h } 33 \text{ min } 20 \text{ sec} + &= 1 \times (24)(60)(60) + 2 \times (60)(60) + 33 \times 60 + 20 \\ + &= \nombre{95600} \text{ secondes}. + \end{align*} + Si l'on fait la conversion en sens inverse, le nombre de jours, + heures, minutes et secondes correspondant à \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}{>{$}c<{$}>{$}r<{$}>{$}r<{$}>{$}r<{$}>{$}c<{$}>{$}c<{$}} + \toprule + i & + \multicolumn{1}{c}{$v$} & + \multicolumn{1}{c}{$b_i$} & + \lfloor v/b_i \rfloor & v \bmod b_i & x_i \\ + \midrule + 0 & \nombre{91492} & 60 & \nombre{1524} & 52 & 52 \\ + 1 & \nombre{1524} & 60 & 25 & 24 & 24 \\ + 2 & 25 & 24 & 1 & 1 & 1 \\ + 3 & 1 & 365 & 0 & 1 & 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 à 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 &= 2 \text{ reste } 3 \quad\Rightarrow\quad x_0 = 3 \\ + 2 \div 4 &= 0 \text{ reste } 2 \quad\Rightarrow\quad x_1 = 2, + \end{align*} + soit le «nombre» $(2, 3)$. En additionnant $1$ à 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 à partir de + $1$, alors que les systèmes de numération débutent à $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 à \fbox{$0$} ou à \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 à 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 à +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 à 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) à +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 à 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-à-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 à 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} à 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 à 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 à 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$ à $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}$ à $\nombre{1023}$. + +\begin{table} + \caption{Valeurs spéciales dans la norme IEEE~754} + \label{tab:ordinateurs:special_values} + \begin{tabular}{crccc} + \toprule + $S$ & + \multicolumn{1}{c}{$E$} & + $F$ & Représentation binaire & Valeur spéciale \\ + \midrule + $0$ & $0$ & $0$ & + \ieee{0}{00000000000}{00 \cdots 00} & $0$ \\ + $1$ & $0$ & $0$ & + \ieee{1}{00000000000}{00 \cdots 00} & $-0$ \\ + $0$ & $\nombre{2047}$ & $0$ & + \ieee{0}{11111111111}{00 \cdots 00} & $+\infty$ \\ + $1$ & $\nombre{2047}$ & $0$ & + \ieee{1}{11111111111}{00 \cdots 00} & $-\infty$ \\ + $0 \text{ ou } 1$ & $\nombre{2047}$ & $F \neq 0$ & + \ieee{$S$}{11111111111}{\hspace{1.2em} $F$ \hspace{1.2em}} & + \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é à 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} + &= 2^{-1} \\ + &= (-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} + &= 0,0001100110011001100110011001\dots \\ + &= 2^{-4} \times 1,1001100110011001\dots \\ + &= (-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 à, $\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à qui justifie le principe de + programmation énoncé à 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}} + &= \ieee{0}{11111111110}{11 \cdots 11} \\ + &= (-1)^0 \times 2^{\nombre{1023}} \times 1,11\cdots11 \\ + &= 2^{\nombre{1023}} \times (2 - 2^{-52}) \\ + &= \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}} + &= \ieee{0}{00000000001}{00 \cdots 00} \\ + &= (-1)^0 \times 2^{\nombre{-1022}} \times 1,00\cdots00 \\ + &= 2^{\nombre{-1022}} \\ + &= \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}} + &= (-1)^0 \times 2^{\nombre{-1022}} \times 0,00\cdots01 \\ + &= 2^{\nombre{-1022}} \times 2^{-52} \\ + &= 2^{-\nombre{1074}} \\ + &= \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}}^+ + &= (1 + \varepsilon) \times 2^{-\nombre{1022}} \\ + &= x_{\text{min}} + \varepsilon \times 2^{-\nombre{1022}} \\ + &= x_{\text{min}} + 2^{-\nombre{1074}}, \\ + \intertext{alors que le nombre précédant $x_{\text{max}}$ est} + x_{\text{max}}^- + &= (2 - 2^{-52} - \varepsilon) \times 2^{\nombre{1023}} \\ + &= x_{\text{max}} - \varepsilon \times 2^{\nombre{1023}} \\ + &= 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 > x_{\text{max}}$ ($x < +-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 < x_{\text{min}}$ entraine un +\emph{soupassement de capacité} et le résultat est habituellement +considéré égal à $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} +> .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$} & + \multicolumn{2}{c}{$\fl(x)$} \\ + \midrule + $2$&$5$ & $0$&$25000 \times 10^1$ \\ + $-42$&$182$ & $-0$&$42182 \times 10^2$ \\ + $0$&$214356$ & $0$&$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 à la valeur la plus près ($0,14$ devient $0,1$ et + $\nombre{0,16}$ devient $0,2$); + \item arrondir un nombre exactement à 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 à 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) + &= (0,70000 \times 10^1 + 0,40000 \times 10^1) + + 0,10000 \times 10^6 \\ + &= 0,11000 \times 10^2 + 0,10000 \times 10^6 \\ + &= 0,00001 \times 10^6 + 0,10000 \times 10^6 \\ + &= 0,10001 \times 10^6, \\ + \intertext{soit un résultat raisonnablement précis. Cependant,} + \fl(x) + [\fl(y) + \fl(z)] + &= 0,70000 \times 10^1 + + (0,00000 \times 10^6 + 0,10000 \times 10^6) \\ + &= 0,00000 \times 10^6 + 0,10000 \times 10^6 \\ + &= 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)] + &= 0,10000 \times 10^6 + - (0,10000 \times 10^6 + 0,00000 \times 10^6) \\ + &= 0,00000 \times 10^0, + \intertext{alors que} + [\fl(z) - \fl(y)] - \fl(x) + &= (0,10000 \times 10^6 - 0,10000 \times 10^6) - + 0,70000 \times 10^1 \\ + &= 0,00000 \times 10^1 - 0,70000 \times 10^1 \\ + &= -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 > 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}))] + &= 1 - [1 \div (1 + 0,24788 \times 10^{-2})] \\ + &= 1 - [0,10000 \times 10^1 \div 0,10025 \times 10^1)] \\ + &= 1 - 0,99751 \times 10^0 \\ + &= 0,10000 \times 10^1 - 0,09975 \times 10^1 \\ + &= 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) + &= \frac{e^{-6}}{1 + e^{-6}} \\ + &= \frac{1}{1 + e^6} + \end{align*} + dans laquelle l'opération de soustraction entre deux nombres presque + égaux est déjà effectuée, on obtient le résultat bien plus précis + \begin{align*} + 1 \div (1 + \fl(e^6)) + &= 1 \div (1 + 0,40343 \times 10^3)) \\ + &= 1 \div (0,00100 \times 10^3 + 0,40343 \times 10^3) \\ + &= 1 \div 0,40443 \times 10^3 \\ + &= 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 > \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} +> prod(x) +\end{Sinput} +\begin{Soutput} +[1] Inf +\end{Soutput} +\begin{Sinput} +> 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} +> 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} +> 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 à 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} +> 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 +à 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 & Cout relatif \\ + \midrule + Addition et soustraction & $1,0$ \\ + Multiplication & $1,3$ \\ + Division & $3,0$ \\ + Racine carrée & $4,0$ \\ + Logarithme & $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 à +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 à 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 à +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 à quatre octets et les premiers 128 caractères sont +identiques à 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} |