\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
%\usepackage{french}
\usepackage[francais]{babel}

%% Parametres de mise en page
\topmargin -.04cm
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  .96cm
\evensidemargin .96cm
\textwidth 14cm
\textheight 25.7cm
\advance\textheight by \topskip
\parindent 0pt

\def\ceil#1{\left\lceil #1\right\rceil}
\def\floor#1{\left\lfloor #1\right\rfloor}
\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\def\intro{\begin{center}\begin{minipage}{.9\linewidth}\small}
\def\endintro{\end{minipage}\end{center}}

\begin{document}
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 26 octobre 2001

Louis Granboulan
\end{center}

\section{Arithmétique flottante}
\begin{enumerate}
\item{Étude théorique}
  \begin{intro}
  On se donne quatre entiers : une base $B$, une longueur de mantisse $n$
  et deux exposants extrémaux $E_{\min}$ et $E_{\max}$.
  Habituellement, $B\geq2$, $n\geq2$ et $E_{\min}<0<E_{\max}$.
  L'écriture en virgule flottante d'un réel $x$
  est $\epsilon_x . \overline{x_0,x_1...x_{n-1}} B^{e_x}$
  avec $\epsilon_x = \pm1$, $E_{\min}\leq e_x \leq E_{\max}$ et
  $0\leq x_i<B$, si on a
  $x = \epsilon_x\left(\sum_{i=0}^{n-1}x_iB^{-i}\right)B^{e_x}$.
  On appelle {\em mantisse} la valeur $f_x = \sum_{i=0}^{n-1}x_iB^{-i}$.
  \end{intro}
  \begin{enumerate}
    \item Bien évidemment, tous les réels ne sont pas représentables exactement.
          Calculer quels sont le plus petit et le plus grand réels positifs
          représentables exactement.
    \item L'addition, soustraction, multiplication, ... de deux réels
          exactement représentables n'est pas toujours un réel
          exactement représentable. On décide par exemple d'arrondir
          au plus grand réel exactement représentable inférieur au
          résultat.
          \par
          Que donne l'algorithme suivant ? On suppose que $E_{\max}$ est
          suffisamment grand pour éviter les {\em overflow}.
          \begin{itemize}
          \item[] $a \leftarrow 1.0$ \qquad $b \leftarrow 1.0$
          \item[] \textbf{tant que} $((a + 1.0) - a) - 1.0$ \texttt{==} 0
                  \textbf{faire} $a \leftarrow a + a$
          \item[] \textbf{tant que} $((a + b) - a) - b$ \texttt{<>} 0
                  \textbf{faire} $b \leftarrow b + 1.0$
          \item[] \textbf{imprimer} $b$
          \end{itemize}
  \end{enumerate}
\item{Norme IEEE 754}
  \begin{intro}
  Cette norme étend la notation précédente comme suit : la base $B=2$
  et on note $f_x = \sum_{i=1}^n x_i 2^{-i}$. L'exposant $e_x$ peut
  varier dans l'intervalle $[E_{\min}-1, E_{\max}+1]$.
  \begin{center}
  \begin{tabular}{|c@{}c@{}c|}
  \hline Exposant & Mantisse & Valeur \cr
  \hline
  $E_{\min}-1$                     & $f_x=0$    & $\pm0$ \cr
  $E_{\min}-1$                     & $f_x\neq0$ & $\pm f_x 2^{E_{\min}}$ \cr
  $E_{\min}\leq e_x \leq E_{\max}$ &            & $\pm (1+f_x) 2^{e_x}$ \cr
  $E_{\max}+1$                     & $f_x=0$    & $\pm\infty$ \cr
  $E_{\max}+1$                     & $f_x\neq0$ & NaN \cr
  \hline
  \end{tabular}
  \begin{tabular}{|ll|}
  \hline {\tt float} & {\tt double} \cr
  \hline
  32 bits & 64 bits \cr
  $n = 23$ & $n = 52$ \cr
  $E_{\min}=-126$ & $E_{\min}=-1022$ \cr
  $E_{\max}=+127$ & $E_{\max}=+1023$ \cr
  \hline
  \end{tabular}
  \end{center}
  Les arrondis des opérations peuvent se faire de plusieurs façons :
  au plus proche, vers 0, vers le haut ou vers le bas.
  \end{intro}
  \begin{enumerate}
    \item Comparer cette représentation avec la représentation précédente.
        % Montrer par exemple que \texttt{x == y} et \texttt{x-y == 0}
        % deviennent identiques (en l'absence d'{\em overflow}).
  \end{enumerate}
\end{enumerate}

\section{Calcul d'une somme}
\begin{enumerate}
\item{Série harmonique}
  \begin{enumerate}
    \item On définit la suite $u_0=0$ et $u_n=u_{n-1}+\frac1n$
          Montrer que le calcul de cette suite en représentation
          flottante converge.
    \item Trouver une astuce pour calculer assez précisément
          $\sum_{n=1}^N \frac1n$. Évaluer la précision du
          résultat.
  \end{enumerate}
\item{Encadrement du résultat}
  \begin{enumerate}
    \item Décrire des techniques de calcul d'un encadrement
          de $\sum_{n=1}^N a_n$.
    \item En déduire quelques considérations sur la représentation
          d'un réel par un intervalle.
  \end{enumerate}
\item{Double précision}
  \begin{intro}
  On représente un réel par une somme de deux flottants.
  On veut normaliser $A + B$ sous la forme $X + x$
  de telle sorte que la valeur absolue de $x$ soit la
  plus petite possible.
  On suppose que les opérations sur les flottants sont
  arrondies au plus proche.
  \end{intro}
  \begin{enumerate}
    \item Exprimer la condition de normalisation sous la
          forme $|x|\leq \frac12\alpha(X)$.
    \item Trouver comment faire cette normalisation en six
          opérations dans le cas général et en trois opérations
          (additions et soustractions)
          si $|B|$ est suffisamment petit.
    \item En déduire comment faire une addition en vingt
          opérations.
    \item Étudier, dans cette représentation, les autres opérations
          habituelles.
  \end{enumerate}
\end{enumerate}

\end{document}
