%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}


\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}


\usepackage{media9}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}
\newcommand\xor{\oplus}

\newcommand\foncpart{\rightarrow\!\!\!\!\!\!\shortmid}
\newcommand\fonctot{\rightarrow}
\newcommand\injpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid}
\newcommand\injtot{\rightarrowtail}
\newcommand\surjpart{\twoheadrightarrow\!\!\!\!\!\!\!\shortmid}
\newcommand\surjtot{\twoheadrightarrow}
\newcommand\bijpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid\!\!\!\!\twoheadrightarrow}
\newcommand\bijtot{\rightarrowtail\!\!\!\!\!\!\!\!\!\twoheadrightarrow}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}}




\newcommand\caml{\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\small\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}



\newcommand\haskell{\lstset{numbers=none, escapeinside={(*@}{@*)},language=haskell,xleftmargin=10pt,%
keywordstyle =\footnotesize\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\footnotesize\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\python{\lstset{numbers=none,language=sage,xleftmargin=10pt,%
keywordstyle
=\small\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b,
 morecomment=[n][\color{gray}]{In\ [}{]\:},  morecomment=[n][\color{red}]{Out[}{]\:},  morecomment=[n][\color{gray}]{sage}{\:}
}
}

\newcommand\ce{\lstset{numbers=none,language=c,xleftmargin=10pt,%
keywordstyle =\tiny\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\tiny\ttfamily\color{white},commentstyle=\normalfont\tiny\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}



\newcommand\lat{\lstset{numbers=none,language=[LaTeX]TeX,xleftmargin=10pt,%
keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}

\lstdefinelanguage{JavaScript}{
  keywords={js, pow, typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break,Math.pow},
  ndkeywords={ Math, class, export, boolean, throw, implements, import, this},
  ndkeywordstyle=\color{orange}\bfseries\scriptsize,
  identifierstyle=\color{gray}\scriptsize,
  sensitive=false,
  comment=[l]{//},
  morecomment=[s]{/*}{*/},
  morestring=[b]',
  morestring=[b]"
}



\newcommand\js{\lstset{numbers=none,language=JavaScript,xleftmargin=10pt,%
keywordstyle =\scriptsize\color{orange!60}\usefont{OT1}{cmtt}{b}{n},basicstyle=\scriptsize\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}




\setcounter{tocdepth}{2} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}

\newcommand{\triangleup}{\Delta}











\newcolumntype{C}[1]{>{\centering}b{\widthof{#1}}}
\newcommand\MyBox[2][XXX]{%
  \fbox{\tabular[b]{C{#1}} #2 \endtabular}}























\begin{document}


\title[] % (optional, use only with long paper titles)
{IEEE 754: au-delà du réel}

\subtitle{Journées académiques 2014}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IREM} de Nantes}% (optional, but mostly needed)

\logo{\includegraphics[width=0.1\textwidth]{logoirem}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today{} à \now}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

% \AtBeginSubsubsection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }




\AtBeginSubsection[]
{\scriptsize
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\tiny
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
%\ThisCenterWallPaper{1}{logoiremBigInv}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}



\python


\section{Préambule}

\begin{frame}
\begin{center}
  \includegraphics[width=0.7\textwidth]{patriot}
\end{center}
\end{frame}



\begin{frame}
\begin{center}
  \includegraphics[width=0.7\textwidth]{scud}
\end{center}
\end{frame}



\begin{frame}
\begin{center}
  \includegraphics[width=0.6\textwidth]{oups}
\end{center}
\end{frame}




\begin{frame}
\begin{center}
  \includegraphics[width=0.8\textwidth]{ariane2}
\end{center}
\end{frame}






\begin{frame}
\begin{center}
  \includegraphics[width=0.6\textwidth]{portavion}
\end{center}
\end{frame}



\begin{frame}
%\begin{figure}
\begin{center}
  \includegraphics[width=0.6\linewidth]{excel}
\end{center}
%\end{figure}
\end{frame}


\begin{frame}
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{jeu_erreur}
\end{center}
%\end{figure}
\end{frame}



\begin{frame}
\begin{center}
  \includegraphics[width=0.8\textwidth]{ingenieur}
\end{center}
\end{frame}



\begin{frame}
\begin{center}
  \includegraphics[width=0.7\textwidth]{Boulier.jpg}
\end{center}
\end{frame}





\begin{frame}
\begin{center}
  \includegraphics[width=0.8\textwidth]{zuse}
\end{center}
\end{frame}










\begin{frame}
\begin{center}
  \includegraphics[width=0.8\textwidth]{setun}
\end{center}
\end{frame}





\begin{frame}
  \begin{itemize}
\item \texttt{char} 
\item \texttt{int} 
\pause  $2147483647+1=-2147483648$...\pause
\item \texttt{short} \pause  \texttt{long} \pause
\item \texttt{float} 
\item single
\item \texttt{double}
\item \texttt{long} \texttt{double}
\item 3 \pause 3.0 \pause 3.0000 \pause 3.0e0 \pause 0.3e1
\item ...
\end{itemize}
\end{frame}



\begin{frame}[fragile]

  
\begin{lstlisting}
In [1]: 3 * 0.1
.
.
.
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]

  
\begin{lstlisting}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
.
.
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]

  
\begin{lstlisting}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
In [2]: sum([0.1 for k in range(10000000)])
.
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]

  
\begin{lstlisting}
In [1]: 3 * 0.1
Out[1]: 0.30000000000000004
In [2]: sum([0.1 for k in range(10000000)])
Out[2]: 999999.9998389754
\end{lstlisting}

\end{frame}

\begin{frame}

{\huge
\bfseries   

{LES NOMBRES RÉELS N'EXISTENT PAS.

\bigskip

\pause

 TOUT CE QUE VOUS AVEZ VU 


AU LYCÉE N'EST 

\medskip

QU'ILLUSION!}
}
\end{frame}



\section{La norme IEEE 754}





\subsection{Différents formats}




\begin{frame}
\begin{center}
  \includegraphics[width=0.6\textwidth]{Kahan}
\end{center}
\end{frame}

\begin{frame}

$$v = (-1)^s\times m\times 2^E$$

\pause

\begin{itemize}
\item \textit{binary32} \pause $(\#
E,\# m)=(8,24)$  \pause 

\item \textit{binary64} \pause  $(\#
E,\# m)=(11,53)$. \pause 


\item \textit{toy7} \pause $(\#
E,\# m)=(3,4)$. \pause 


\end{itemize}




\end{frame}




\begin{frame}[fragile]
 
On peut également gagner de la place en ne stockant pas le signe de l'exposant.


\pause

Sur $\# E$ bits on peut coder $2^{\# E}$ nombres.

\pause

La première moitié va donc de 0 à $2^{\# E - 1} - 1$.

\pause

Elle correspond aux exposants réels de $E_{\min}$ jusqu'à 0.

\pause

La deuxième de $2^{\# E - 1}$ à $2^{\# E} - 1$.

\pause

Elle correspond aux exposants de 1 jusqu'à $E_{\max}$.

\pause

Il suffit donc de translater les exposants réels de $2^{\# E - 1} - 1$...


\pause

$$
e_{\text{stocké}} = E_{\text{réel}} + 2^{\# E - 1} - 1
$$
\end{frame}


\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.\pause

$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,100_2\times2^{-1}$$\pause

$$e - \left(2^{3-1}-1\right)=E\pause =-1 \pause \lequiv e=-1+3=2=10_2
$$\pause



\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&1&0&1&0&0\\
    \hline
  \end{tabular}
\end{center}

\end{frame}





\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.


$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,\textcolor{yellow}{100}_2\times2^{-1}$$

\bigskip

$$e - \left(2^{3-1}-1\right)=E =-1  \lequiv e=-1+3=2=10_2
$$

\bigskip


\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&1&0&\textcolor{yellow}{1}&\textcolor{yellow}{0}&\textcolor{yellow}{0}\\
    \hline
  \end{tabular}
\end{center}

\end{frame}








\begin{frame} \frametitle{0,75 en toy7}
  $0,75_{10}$ en \textit{toy7}.


$$0,75_{10} = \frac{3_{10}}{2_{10}^{2}}=11_2\times 2^{-2}=1,\textcolor{yellow}{100_2}\times2^{-1}$$

\bigskip

$$e - \left(2^{3-1}-1\right)=E =-1  \lequiv e=-1+3=2=\textcolor{blue!40!yellow}{10_2}
$$

\bigskip


\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&\textcolor{blue!40!yellow}{0}&\textcolor{blue!40!yellow}{1}&\textcolor{blue!40!yellow}{0}&\textcolor{yellow}{1}&\textcolor{yellow}{0}&\textcolor{yellow}{0}\\
    \hline
  \end{tabular}
\end{center}

\end{frame}




\begin{frame} \frametitle{0,75 en toy7 : méthode générale}


Comment écrire en base 2 la partie fractionnaire d'un nombre en base 10?

\pause

$$
0,75 = b_1\times 2^{-1} + b_2\times 2^{-2} + \cdots
$$

\pause

$$
2\times 0,75 = b_1 + b_2\times 2^{-1} + \cdots
$$



\pause

On voit poindre un bel algo...


\end{frame}





\begin{frame}

\begin{exercice}

  Pourquoi le \textit{Patriot} a raté son \textit{Scud} de 600m?

Représentez 1/10 avec une mantisse de 24 bits et tronquez le résultat.

Calculez l'erreur en seconde puis  après 100 heures d'utilisation. Sachant qu'un
Scud vole à $\SI{1676}{m.s^{-1}}$, quelle est environ l'erreur commise en mètres?

Et si on avait arrondi au plus proche?


\end{exercice}

\end{frame}

\subsection{Les normaux, les sous-normaux et les paranormaux}





\begin{frame}
\begin{center}
  \includegraphics[width=0.9\textwidth]{alien}
\end{center}
\end{frame}


\begin{frame}
$$e_{\min}=0$$

\pause

$$e_{\max}=2^{\# E}-1$$

\pause

$$e=E+2^{(\# E) - 1}-1$$


\pause

\begin{center}
\textit{toy7},\pause $\#E = 3$, \pause $e_{\min}=000$, \pause $e_{\max}=111=1000-1$
\end{center}

\pause

\textcolor{yellow}{Les valeurs extrêmes de $E$ sont réservées pour des cas spéciaux}

\pause

$$
\begin{aligned}
E_{\min}&=\left(e_{\min}-2^{(\#   E)  -   1}+1\right)+1\pause  =0-2^{3-1}+1+1=-2
\pause \\
E_{\max}&=\left(e_{\max}-2^{(\# E) - 1}+1\right)-1\pause =(2^3-1)-2^{3-1}+1-1=7-4+1-1=3
\end{aligned}
$$

\end{frame}






\begin{frame}
 \begin{itemize}
\item  zéro sous forme normale?
\item $0.\underbrace{000...00}_{\# E}11\times 2^0=1.1\times 2^{-(\#E +1)}$ ?
\end{itemize}

\pause

Sous-normaux\pause....



\end{frame}



\begin{frame}
  \begin{exercice}
    En  utilisant vos  carreaux, représentez  les nombres  à virgule  flottante
    normaux en \textit{toy7} et rajoutez les sous-normaux.
  \end{exercice}
\end{frame}



\begin{frame}
\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    0&0&0&0&0&0&0\\
    \hline
  \end{tabular}
\end{center}


\pause

\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    1&0&0&0&0&0&0\\
    \hline
  \end{tabular}
\end{center}


\end{frame}







\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

.
.
.
.
.
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
.
.
.
.
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
.
.
.
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
.
.
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
.
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
.
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
.
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
In [5]: 4 - x
.
\end{lstlisting}



  
\end{frame}

\begin{frame}[fragile]
\begin{lstlisting}
In [1]: x = 1e500

In [2]: 1+x
Out[2]: inf
In [3]: x**3
Out[3]: inf
In [4]: 1/x
Out[4]: 0.0
In [5]: 4 - x
Out[5]: -inf
\end{lstlisting}



  
\end{frame}





\begin{frame}[fragile]

$$
\displaystyle\lim_{x\to +\infty}x^2 -x
$$

\pause



\begin{lstlisting}
In [9]: x**2 - x
.
\end{lstlisting}





\end{frame}



\begin{frame}[fragile]

$$
\displaystyle\lim_{x\to +\infty}x^2 -x
$$

\pause



\begin{lstlisting}
In [9]: x**2 - x
Out[9]: nan
\end{lstlisting}





\end{frame}






\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{nan}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
In [10]: x
Out[10]: inf

In [11]: x - x
Out[11]: nan

In [12]: x / x
Out[12]: nan

In [13]: x - x == x - x
Out[13]: False

In [14]: x**2 - x
Out[14]: nan

In [15]: x * (x - 1)
Out[15]: inf

In [16]: x * (x - 1) == x**2 - x
Out[16]: False
  \end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]

\begin{exercice}
\begin{enumerate}

\item   Comment expliquer les résultats suivants:

  \begin{lstlisting}
*Main> let f(x) = x^2 / sqrt(x^3 + 1)
*Main> f(1e100)
1.0e50
*Main> f(1e150)
0.0
*Main> f(1e200)
NaN
  \end{lstlisting}

\item Comment éviter le dernier NaN?



\end{enumerate}



\end{exercice}


  
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
In [16]: f = lambda x: x**2 / sqrt(x**3 + 1)

In [17]: f(1e100)
Out[17]: 1e+50

In [18]: f(1e150)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-18-79775d85f31a> in <module>()
----> 1 f(1e150)

<ipython-input-16-eed0b81ef932> in <lambda>(x)
----> 1 f = lambda x: x**2 / sqrt(x**3 + 1)

OverflowError: (34, 'Numerical result out of range')

In [19]: f(1e200)
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-19-c1d077e9d28e> in <module>()
----> 1 f(1e200)

<ipython-input-16-eed0b81ef932> in <lambda>(x)
----> 1 f = lambda x: x**2 / sqrt(x**3 + 1)

OverflowError: (34, 'Numerical result out of range')
  \end{lstlisting}
  
\end{frame}




\begin{frame}[fragile]
  \begin{lstlisting}
In [53]: x = 1e-500

In [54]: x
Out[54]: 0.0

In [55]: x / x
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-55-fd52a7f8b5f1> in <module>()
----> 1 x / x

ZeroDivisionError: float division by zero
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
In [56]: sqrt(-1.0)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-56-d1c09f21b443> in <module>()
----> 1 sqrt(-1.0)

ValueError: math domain error

  \end{lstlisting}

\end{frame}


\haskell

\begin{lstlisting}
*Main> let x = 1e500
*Main> x - x
NaN
*Main> x / x
NaN
*Main> sqrt(-1)
NaN
*Main> 0 / 0
NaN

\end{lstlisting}


\python

\begin{frame}\frametitle{USS Yorktown 1998}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{yorktown}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{Error-Message}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}\frametitle{Air France 447 - 1\er juin 2009}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{airbus}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}
  
\begin{center}
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    $s$ (1  bit) &  \multicolumn{3}{c||}{$e$ (3  bits)} &  \multicolumn{3}{c|}{$f$ (3
      bits)}\\
    \hline
    1&1&1&1&0&1&0\\
    \hline
  \end{tabular}
\end{center}

\end{frame}


\begin{frame} \frametitle{Arbre de lecture}
\begin{center}


  \begin{tabular}[h]{|c||c||c|}
    \hline
    $s$&$e$&$f$\\
    \hline
  \end{tabular}
\pause

  \begin{tabular}[h!]{llcl}

\hline
$e=0...0$ & $f=0$ & $\rightarrow$ & $v=(-1)^s\times 0.0$  \\
$e=0...0$ & $f\neq  0$ & $\rightarrow$ & $v=(-1)^s\times  0.f \times 2^{1-E_{\max}}$\\
$e=1...1$ & $f=  0$ & $\rightarrow$ & $v=(-1)^s\times \infty$\\
$e=1...1$ & $f\neq 0$ & $\rightarrow$ & $\text{NaN}$\\
$0...0<e<1...1$ & $f\neq  0$ & $\rightarrow$ & $v=(-1)^s\times  1.f \times 2^{e-E_{\max}}$\\
\hline

  \end{tabular}

\end{center}

\end{frame}


\begin{frame}\frametitle{Successeur}
$$n=\# f$$

\pause

 \textit{toy7}, \pause $n=3$


\pause

\textit{binary32}, \pause $n=23$

\pause

 \textit{binary64}, \pause $n=52$


\pause

$$v=M(v)\times 2^{E(v)-n}$$


\pause

$$\operatorname{succ} (v) = (M(v)+1)\times 2^{E(v)-n} = v +  2^{E(v)-n}$$


\end{frame}



\begin{frame} \frametitle{Tableau récapitulatif}


  \begin{itemize}
  \item On notera $ε_m$ l'\textit{epsilon} de  la machine, c'est-à-dire le successeur de
1

\item On notera $λ$ le plus petit VF normal positif



\item On notera $μ$ le plus petit VF sous-normal positif


\item On notera $Ω$ le plus grand VF normal.
  \end{itemize}


\pause

 Quelle relation existe-t-il entre $μ$, $ε_m$ et $λ$?


  
\end{frame}



\begin{frame}

 {\tiny
  \begin{tabular}{|*{9}{c|}}
\hline
    Format & $\# E$ & $\# f$ & $E_{\min}$ & $E_{\max}$ & $ε_m$ & $λ$ & $μ$ & $Ω$ \\
\hline
\textit{toy7} & 3 & 3 & $-2$& $3$ & $2^{-3}=1/8$ & $2^{-2}=1/4$ & $2^{-5}=1/32$ & $1,111\times 2^3=15$ \\
\textit{bin32} & 8 & 23 & $-126$ &$127$ &$2^{-23}$  &$2^{-126}$ & $2^{-126-23}$&  $(2^{24}-1)\times 2^{127-23}$\\
                  &  &    &         &       & $\approx 1,2\times 10^{-7}$ & $\approx 1,2\times 10^{-38}$  & $\approx 1,4\times 10^{-45}$ &$\approx 3,4\times 10^{38}$ \\
\textit{bin64} & 11 & 52 & $-1022$&$1023$ & $2^{-52}$ & $2^{-1022}$& $2^{-1074}$& $(2^{53}-1)2^{1023-52}$\\
                  & &  & & &  $\approx 2,2\times 10^{-16}$ &  $\approx 2,2\times
                  10^{-308}$ &$\approx 5\times 10^{-324}$ & $\approx 1,8\times 10^{308}$\\
\hline
  \end{tabular}\label{tab::reca}
}

\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
.
.
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True
.
.
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16
.
.
.
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
.
.
.
.
.
.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

.
.
.
.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
.

.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

.
.
  \end{lstlisting}
\end{frame}
\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

In [5]: 1e-16 + 1e-18
.
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  \begin{lstlisting}
In [1]: 1 + 1e-16 == 1
Out[1]: True

In [2]: x = 1 + 1e-16

In [3]: x - 1
Out[3]: 0.0

In [4]: x - 1e-16
Out[4]: 0.9999999999999999

In [5]: 1e-16 + 1e-18
Out[5]: 1.01e-16
  \end{lstlisting}
\end{frame}










\section{Algèbre des nombres VF}






\begin{frame}

$$\bbv_b$$

\pause

 $$\overline{\bbv_{b}}$$




\end{frame}


\begin{frame} \frametitle{Comparaison}
  Il  est  très  simple  et  rapide  de  comparer  deux  VF:  comment  la  machine
procède-t-elle? Quel est l'avantage de ce stockage des VF?
\end{frame}


\begin{frame} \frametitle{Addition}


\begin{enumerate}
\item on commence par ramener les deux nombres au même exposant, en l'occurrence
  le plus grand des deux;
\item on ajoute les deux mantisses \textit{complètes} en tenant compte du signe;
\item on renormalise le nombre obtenu.
\end{enumerate}

  
\end{frame}




\begin{frame} \frametitle{Addition}

En \textit{toy7}: $1,1 + 0,0111\ $ \pause $\ \rightarrow \ \ 1,1\times
2^{0} + 1,11\times 2^{-2}$ 

\pause

\medskip

1,1:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    0&0&1&1&1&0&0\\
    \hline
  \end{tabular}
\pause
  \hfill 0,0011:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
   \hline
    0&0&0&1&1&1&0\\
    \hline
  \end{tabular}

\pause

\vfill

1,100

\pause

0,001\textcolor{yellow}{\itshape 11}

$----$

\pause

1,101\textcolor{yellow}{\itshape 11}


\end{frame}


\begin{frame} \frametitle{Les arrondis}
  \begin{definition}
\begin{enumerate}
\item l'arrondi au plus proche (RN) qui  arrondit au VF...le plus proche. En cas
  d'égalité,  on choisit  la valeur  paire  (donc qui  se  termine par  un 0  en
  binaire);
\item l'arrondi  vers 0  (RZ) qui  arrondit à  la valeur  de plus  petite valeur
  absolue: c'est la troncature;
\item l'arrondi vers $+\infty$ (RU) qui  arrondit à la valeur supérieure la plus
  petite;
\item l'arrondi vers $-\infty$ (RD) qui arrondit à la valeur inférieure la plus grande.
\end{enumerate}
\pause
Le mode d'arrondi par défaut est le premier.
\end{definition}
\end{frame}


\begin{frame}



1,100


0,001\textcolor{yellow}{\itshape 11}

$----$



1,101\textcolor{yellow}{\itshape 11}


\pause


\bigskip



   $x=1,101\textcolor{yellow}{\mathit{11}}$ \pause VF en \textit{toy7}?


\pause

$$
1,101\textcolor{yellow}{ \mathit{00}} \leqslant \underbrace{1,101\textcolor{yellow}{ \mathit{11}}}_x \leqslant 1,110\textcolor{yellow}{ \mathit{00}}
$$

\pause

$$
\underbrace{1,100+ \textcolor{yellow}{\mathit{1,00}}ulp(x)}_v \leqslant  \underbrace{1,100+ \textcolor{yellow}{ \mathit{1,11}}ulp(x)}_{x} \leqslant \underbrace{1,100+ \textcolor{yellow}{\mathit{10,00}}ulp(x)}_{\operatorname{succ}(v)}
$$

$|x-v|=0,11ulp(x) $ \pause $\ |x- \operatorname{succ}(v)|=0,01ulp(x)$ \pause donc $RN(x)=\operatorname{succ}(v)$

\pause


$$ 1,1 \oplus 0,00111 = 1,110$$

\end{frame}






\begin{frame}
  


%\begin{figure}
\begin{center}
  \includegraphics{DrapeauFloat.5}
\end{center}
%\end{figure}


\end{frame}









\begin{frame}[fragile]
\begin{enumerate}
\item Est-ce que l'addition des VF est associative? 

\pause

  \begin{lstlisting}
In [14]: (1 + 1e-16) + 1e-16
Out[14]: 1.0

In [15]: 1 + (1e-16 + 1e-16)
Out[15]: 1.0000000000000002
  \end{lstlisting}
\pause
  
\item   Est-on sûr de l'ordre dans le quel un compilateur calcule $a+b+c+d$?

\end{enumerate}
\end{frame}


\begin{frame} \frametitle{Multiplication}
  \begin{enumerate}
\item on \og xore\fg{} les bits de signe;
\item on additionne les exposants réels et on décale ou plutôt on additionne les
  exposants décalés et on retire la valeur d'un décalage;
\item on multiplie les mantisses;
\item on normalise.
\end{enumerate}
\end{frame}


\begin{frame}
 $101,1 \times (-10,01)$

\pause

101,1:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    0&1&0&1&0&1&1\\
    \hline
  \end{tabular}
  \hfill -10,01:
  \begin{tabular}[h]{|c||c|c|c||c|c|c|}
   \hline
    1&1&0&0&0&0&1\\
    \hline
  \end{tabular}


\pause

  \begin{enumerate}
  \item 0 xor 1 donne 1: le bit de signe est 1;
  \item $101 +  100 - 11 = 1001 -  11 = 110 $: l'exposant décalé  est $110$ donc
    l'exposant est 3;
  \item $1,011\times 1,001=1,011 + 1,011\times 0,001=1,011 + 0,001011=1,100011$;
\item le produit est donc $1,100011\times 2^3$. Le passage à la forme normale va
  arrondir le produit. On a \pause
$$1,100<x<1,101$$

\pause

avec   $|x-1,100| =\pause 0,011ulp(x)$   et  $|x-1,101|= \pause 0,101ulp(x)$   \pause
donc   $$RN(101,1\times
(-10,01))=-1,100\times 2^3$$

\end{enumerate}

\begin{tabular}[h]{|c||c|c|c||c|c|c|}
    \hline
    1&1&1&0&1&0&0\\
    \hline
  \end{tabular}


\end{frame}

\begin{frame}[fragile]
\begin{enumerate}
\item  Est-ce que la multiplication des VF est associative? 

\pause

\begin{lstlisting}
In [1]: (1.00000001 * 1e-15) * 1e15
Out[1]: 1.0000000100000002

In [2]: 1.00000001 * (1e-15 * 1e15)
Out[2]: 1.00000001
\end{lstlisting}

\pause

\item Est-ce que la multiplication des VF est distributive sur l'addition?

\pause



\begin{lstlisting}
In [3]: 1e15 * (1e-16 + 1)
Out[3]: 1000000000000000.0

In [4]: (1e15 * 1e-16) + (1e15 * 1)
Out[4]: 1000000000000000.1
\end{lstlisting}


\end{enumerate}
\end{frame}



\section{Réels, arrondis et flottants}




\begin{frame}[fragile]

  \begin{lstlisting}
def base1(a):
    if (a + 1.0) - a != 1.0:
        return a
    else:
        return base1(2.0 * a)

def base2(a, b):
    if (a + b) - a == b:
        return b
    else:
        return base2(a, b + 1.0)
  \end{lstlisting}


\pause

????!!!!???? !!???



  
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{san_antonio}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}



\begin{quote}
  {\itshape
    95 \% of the folks out there are completely clueless about floating-point
}
\begin{flushright}
  James \textsc{Gosling} (M. Java) - 28 février 1998
\end{flushright}
\end{quote}




%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{gosling}
\end{center}
%\end{figure}


\end{frame}


\begin{frame}
 
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{ryan_gosling}
\end{center}
%\end{figure}

\end{frame}





\begin{frame}
 \begin{description}
\item[Précision]  (\textit{precision}): c'est  le nombre  de bits  utilisés pour
  représenter un nombre. La précision concerne  donc le format utilisé pour écrire ou
  stocker  ou   arrondir  un  nombre. \pause  Par   exemple  \texttt{3},  \texttt{3.0},
  \texttt{3.0000},  \texttt{3.0e0} n'ont  pas la  même précision,  précision qui
  dépend en plus du langage. \pause
\item[Exactitude] (\textit{accuracy}): c'est ce qui  relie un nombre au contexte
  dans lequel il est employé. 
\end{description}

\pause

$3,177777777777777$  est une  approximation plutôt  précise (16  décimales) mais
inexacte (2 décimales) de $\pi$.

\end{frame}


\begin{frame}
  Soit $x$ un nombre et $\widehat{x}$ le nombre qui le représente. On distingue:\pause
  \begin{description}
  \item[l'erreur absolue] $|x - \widehat{x}|$
  \item[l'erreur relative] $η=\frac{x-\widehat{x}}{x}$\pause alors $\widehat{x}=x(1+η)$
  \end{description} \pause
commise en prenant $\widehat{x}$ à la place de $x$.
\end{frame}






% \begin{frame}
%   $r=f(d)$

% \begin{definition}
%   \begin{itemize}
%   \item   L'erreur  \textit{aval} (\textit{forward  error}) est  la différence  entre le
%   résultat mesuré $\widehat{r}$ et le résultat théorique $r$.

% \item L'erreur \textit{amont}, ou erreur \textit{inverse} (\textit{backward error})
% est le plus petit $|Δ d|$ tel que $f(d + Δ d ) = \widehat{r}$.
% \end{itemize}
% \end{definition}

% \end{frame}







\begin{frame}
\begin{quote}
  {\itshape
   Feel nervous, but feel in control.
It’s not dark magic, it’s science.
}
\begin{flushright}
  Florent \textsc{de Dinechin}
\end{flushright}
\end{quote}



%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{AS400}
\end{center}
%\end{figure}



\end{frame}



\section{Que la force de l'erreur soit avec vous}



\subsection{Atelier Padawan \# 1: majorer l'erreur}






\begin{frame}\frametitle{Précision machine}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{padawan}
\end{center}
%\end{figure}

\end{frame}





\begin{frame}\frametitle{Précision machine}
$$M\times 2^{E-n}\leqslant  x < (M+1)\times 2^{E-n}\pause =M\times 2^{E-n} +2^{E-n}$$

\pause

$$|x-\widehat{x}|\leqslant \frac{1}{2}2^{E-n}$$


\pause

$$\left|\frac{x-\widehat{x}}{x}\right|\leqslant
\left|\frac{x-\widehat{x}}{m\times 2^E}\right|\pause \leqslant
\frac{1}{2}\frac{2^{E-n}}{m\times 2^E}\pause =\frac{1}{2}\frac{2^{-n}}{m}\pause =\frac{1}{2}\frac{ε_M}{m}$$

\pause

\begin{enumerate}
\item Si $\widehat{x}$ VF alors  l'\textbf{erreur relative} est majorée $\left|\frac{x-\widehat{x}}{x}\right|\leqslant\frac{1}{2}ε_M$

\item  Si $\widehat{x}$ est sous-normal, alors l'\textbf{erreur absolue} est majorée \pause $|x-\widehat{x}|\leqslant \frac{1}{2}2^{E_{\min}-1-n}$
\end{enumerate}


\end{frame}



\begin{frame}\frametitle{Précision machine}
$$\widehat{x}=x(1+η_1)+η_2$$

avec:

\begin{itemize}
\item si $\widehat{x}$ est normal $|η_1|\leqslant \frac{1}{2}ε_M$ et $η_2=0$
\item si $\widehat{x}$ est sous-normal $η_1=0$ et $|η_2|\leqslant  \frac{1}{2}2^{E_{\min}-1-n} $
\end{itemize}



\pause

Mouais...


\end{frame}

\begin{frame} \frametitle{Élimination}
 $\widehat{a}=a(1+η_a)$,\pause
$\widehat{b}=b(1+η_b)$,\pause $x=a-b$ \pause et $\widehat{x}=\widehat{a-b}\pause
=\widehat{a}-\widehat{b}$.

\pause


$$
\left|\frac{x-\widehat{x}}{x}\right|=\left|\frac{-a    η_a+b    η_b}{a-b}\right|
\pause \leqslant \max(|η_a|,|η_b|)\frac{|a|+|b|}{|a-b|}
$$

\end{frame}


% dérivation approchée

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
def deriv(f,h,x):
    return (f(x+h) - f(x)) / h
  \end{lstlisting}

\pause

\begin{lstlisting}
def derivn(f,x,h,n):
    if n == 0:
        return f(x)
    else:
        return derivn(lambda x: deriv(f,h,x),x,h,n-1)
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [1]: [derivn(lambda x: x**4,1,1e-7,k) for k in range(5)]
Out[1]: 
[1,
 4.000000601855902,
 12.012613126444194,
 -222044.6049250313,
 2220446049250.313]
  \end{lstlisting}

\pause

\begin{lstlisting}
In [2]: [derivn(lambda x: x**4,1,1e-8,k) for k in range(5)]
Out[2]: [1, 4.000000042303498, 11.102230246251565, 0.0, 2.220446049250313e+16]
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [3]: [derivn(lambda x: x**4,1,1e-9,k) for k in range(5)]
Out[3]: [1, 4.000000330961484, 0.0, 0.0, 0.0]
  \end{lstlisting}

\pause

\begin{lstlisting}
In [4]: [derivn(lambda x: x**4,1,1e-3,k) for k in range(6)]
Out[4]: 
[1,
 4.006004000999486,
 12.024014000244776,
 24.03599941303014,
 24.001245435556484,
 -2.4424906541753444]
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [5]: [derivn(lambda x: x**4,1,2**-10,k) for k in range(6)]
Out[5]: [1, 4.005863190628588, 12.02345085144043, 24.03515625, 24.0, 0.0]
  \end{lstlisting}

\pause


\begin{lstlisting}
In [6]: [derivn(lambda x: x**4,1,1.0/1026.,k) for k in range(6)]
Out[6]: 
[1,
 4.005851753982072,
 12.023405112200917,
 24.035087928668187,
 23.999573957547014,
 0.755876563500351]
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [7]: [derivn(lambda x: x**4,1,2**-20,k) for k in range(6)]
Out[7]: [1, 4.000005722045898, 12.0, 0.0, 268435456.0, -844424930131968.0]
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [7]: [derivn(exp,0,2**-5,k) for k in range(10)]
Out[7]: 
[1.0,
 1.0157890399712883,
 1.0318273737254913,
 1.0481189373895177,
 1.0646677284967154,
 1.081477828323841,
 1.0985534191131592,
 1.1158447265625,
 1.1376953125,
 0.953125]
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]\frametitle{Catastrophe}
  \begin{lstlisting}
In [8]: [derivn(exp,0,2**-20,k) for k in range(10)]
Out[8]: [1.0, 1.0000004768371582, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  \end{lstlisting}
\end{frame}





\begin{frame}
\footnotesize
\begin{exercice}\label{ex::delta}
  Vous savez résoudre  une équation du type $ax^2+bx+c=0$ avec
  $a\neq 0$...

Les  racines, si  elles  existent,  sont données  par  une  formule bien  connue
dépendant de $a$, $b$ et $c$:

$$r=\frac{-b\pm     \sqrt{b^2-4ac}}{2a}=\frac{-b\pm      \sqrt{Δ}}{2a}     \quad
\text{avec}\quad Δ = b^2-4ac$$





Où peuvent se cacher d'éventuelles  annulations catastrophiques? Étudiez ces cas
avec attention, voyez si vous pouvez éviter les éliminations catastrophiques en
réécrivant   les   formules   un   peu   dans   l'esprit   de   la   \og   levée
d'indétermination\fg{}.

\begin{enumerate}
\item Que  se passe-t-il lorsque  $b^2 \gg |4ac|$?  En quoi la  formule $\frac{-
    \left(b+\operatorname{signe}(b)\sqrt{Δ}\right)}{2a} $ peut aider? 
\item  Que se  passe-t-il  lorsque  $b^2\approx 4ac$?  Peut-on  y remédier?  Que
  peut-on dire de $Δ$ par rapport à $b^2$? Y a-t-il élimination catastrophique?
\item  Que  se  passe-t-il  dans   le  cas  de  l'équation  $10^{200}x^2-3\times
  10^{200}x+2\times 10^{200}=0$?
\item Et dans le cas de $10^{-200}x^2-3x+2\times 10^{200}=0$?
\item Moralité?


\end{enumerate}



\end{exercice}


\end{frame}

\begin{frame}[fragile]
  
\begin{exercice}[Max IEEE]

On peut calculer le maximum de deux réels ainsi:

\begin{algo}[noframe]
\FUNC{max}{\pfarg{$x$,$y$}{flottants}}{flottant}
\IF{$x>y$}
\STATE{$\max = x$}
\ELSE
\STATE{$\max = y$}
\ENDIF
\end{algo}

Est-ce adapté à la recherche du maximum de deux flottants en arithmétique IEEE?
  
\end{exercice}

\pause

\begin{lstlisting}
In [1]: max(1,1+1e-16)
Out[1]: 1

In [2]: max(0.1,1e500/1e500)
Out[2]: 0.1

In [3]: 0.1 <= 1e500/1e500
Out[3]: False

In [4]: 0.1 > 1e500/1e500
Out[4]: False
\end{lstlisting}

\end{frame}


\subsection{Atelier Padawan \# 2: somme de flottants}



\begin{frame}[fragile]\frametitle{Élimination}
  \begin{lstlisting}
def expn(n):
    return (1. + 1./n)**n
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]\frametitle{Élimination}
\begin{multicols}{2}
  \begin{lstlisting}
In [1]: [(exp(1) - expn(10.0**k)) for k in range(20)]
Out[1]: 
[0.7182818284590451,
 0.12453936835904278,
 0.01346799903751661,
 0.0013578962234515046,
 0.000135901634119584,
 1.359126674760347e-05,
 1.359363291708604e-06,
 1.3432696333026684e-07,
 3.011168736577474e-08,
\end{lstlisting}

\begin{lstlisting}
 -2.2355251516614771e-07,
 -2.2477574246337895e-07,
 -2.248980650598753e-07,
 -0.00024166757819266138,
 0.002171794372144209,
 0.0021717943720220845,
 -0.31675337809021675,
 1.718281828459045,
 1.718281828459045,
 1.718281828459045,
 1.718281828459045]
  \end{lstlisting}
\end{multicols}
\end{frame}


\begin{frame}[fragile]\frametitle{Élimination}
\begin{multicols}{2}
  \begin{lstlisting}
In [2]: [(exp(1) - expn(2.0**(3*k))) for k in range(20)]
Out[2]: 
[0.7182818284590451,
 0.1524973145086972,
 0.020936875893946105,
 0.0026498282900537795,
 0.0003317472693793455,
 4.147652875108321e-05,
 5.1846929989274315e-06,
 6.480886076687398e-07,
 8.101110671177025e-08,
\end{lstlisting}

\begin{lstlisting}
 1.0126388616527038e-08,
 1.2657985770658797e-09,
 1.582245445774788e-10,
 1.977795704988239e-11,
 2.4722446312352986e-12,
 3.090860900556436e-13,
 3.863576125695545e-14,
 4.884981308350689e-15,
 4.440892098500626e-16,
 1.718281828459045,
 1.718281828459045]
  \end{lstlisting}
\end{multicols}
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
In [89]: [2.0**53 + k for k in range(10)]
Out[89]: 
[9007199254740992.0,
 9007199254740992.0,
 9007199254740994.0,
 9007199254740996.0,
 9007199254740996.0,
 9007199254740996.0,
 9007199254740998.0,
 9007199254741000.0,
 9007199254741000.0,
 9007199254741000.0]
  \end{lstlisting}

\end{frame}

\begin{frame}[fragile]
  \begin{lstlisting}
In [91]: [2.0**55 + k for k in range(10)]
Out[91]: 
[3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.602879701896397e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16,
 3.6028797018963976e+16]
  \end{lstlisting}
\end{frame}





\begin{frame}
  \begin{alertblock}{Attention!}
     Pour  éviter de  déduire des  lemmes suivants  des théorèmes  totalement faux,
  n'oubliez pas que \textbf{DANS CE QUI SUIT X ET Y SONT DES NOMBRES À VIRGULE FLOTTANTE}!
  \end{alertblock}
\end{frame}




\begin{frame}
 
\begin{lemma}[Majoration de l'erreur d'une somme]\label{lemme::majSom}
Posons $x\oplus y =  x + y + \operatorname{err}(x\oplus y)$. Alors, s'il  n'y a pas de
dépassement de capacité, 

$$\left|\operatorname{err}(x\oplus y)\right| \leqslant \min  \left(|x|,|y|\right) 
$$

On a bien sûr un résultat analogue pour la différence

  
\end{lemma}

\end{frame}




\begin{frame}
  \begin{itemize}
  \item $x\oplus y = x + y + \operatorname{err}(x\oplus y)$
  \item $x\textcolor{black}{\oplus y} = x + y + (-y)$
  \item $x$ est un VF situé à la distance $|y|$ de $x+y$
  \item $x\oplus  y$ le VF le plus  proche de $x+y$
  \item $\left|\operatorname{err}(x\oplus y)\right| \leqslant |y|$
  \item de même  $\left|\operatorname{err}(x\oplus y)\right| \leqslant |x|$
  \end{itemize}


\pause


\begin{alertblock}{À noter}
    De l'importance de disposer avec la IEEE 754 de la \textbf{meilleure approximation}!
\end{alertblock}


\end{frame}


\begin{frame}

\begin{corollary}[M\o ller, Knuth, Dekker]
  L'erreur commise $\left|\operatorname{err}(x\oplus y)\right|$ peut être exprimée
  exactement sur $p$ bits.
\end{corollary}

\pause

\begin{itemize}
\item $|x| \geqslant |y|$
\item $x$ et $y$ sont des VF\pause : le  plus petit bit significatif de $\operatorname{err}(x\oplus y)$ est
au moins de magnitude celle de ulp($y$)

\pause

$x$\hspace{1em} \MyBox[mmmmmmmmm]{$x_1$}
\MyBox[mmmm]{$x_2$}

\pause

$+y$ \hspace{9.5em}\MyBox[mmmm]{$y_1$}
\MyBox[mmmmmmmm]{$y_2$}

\pause

$=$   \hspace{1em}\MyBox[mmmmmmmmm]{$x_1$}
\MyBox[mmmm]{$x_2+y_1$} \ $\operatorname{err}(x\oplus y)$

\pause

\item  $\left|\operatorname{err}(x\oplus y)\right| \leqslant |y|$\pause  donc la mantisse
entière de $\operatorname{err}(x\oplus y)$ a une longueur inférieure à $p$ bits
\end{itemize}

\end{frame}


\begin{frame}
\begin{lemma}\label{lemme::plusExact}
  Supposons que $|x+y|\leqslant \min(|x|,|y|)$, alors $x\oplus y = x + y$.

On obtient un résultat analogue pour la soustraction.
\end{lemma}

\begin{enumerate}
\item Supposons, sans perdre de généralité, que $|x| \geqslant |y|$
\item Le  plus petit bit significatif de $x+y$ est
au moins de magnitude celle de $\operatorname{ulp}(y)$
\item  $|x+y| \leqslant |y|$ donc la mantisse
entière de $x+y$  a une longueur inférieure à $p$ bits


\end{enumerate}

\end{frame}


\begin{frame}[fragile]
  \begin{alertblock}{DANGER}
  Nous avons démontré nos lemmes en considérant des VF $x$ et $y$.

  Est-ce que le résultat suivant contredit notre dernier lemme?

  \begin{lstlisting}
In [86]: 1 - 0.9
Out[86]: 0.09999999999999998
  \end{lstlisting}

  \end{alertblock}
\end{frame}





\begin{frame}
\begin{lemma}[Lemme de \textsc{Sterbenz} (1973)]
  Soit $(x,y)\in \bbv^2$ vérifiant $\dfrac{x}{2} \leqslant y \leqslant 2x$ alors $$x\ominus y=x-y$$
La différence de deux VF suffisamment proches est donc exacte.
\end{lemma}

\pause


\begin{enumerate}
\item  $\mathbf{x <  y}$:  alors  $x <  y  \leqslant  2x$ donc  $0
  < y-x \leqslant x \leqslant y$;
\item $\mathbf{x  \geqslant y}$: alors  $ \frac{x}{2} \leqslant y  \leqslant x$
  donc $ -\frac{x}{2} \leqslant y-x \leqslant 0$ et par suite $0 \leqslant x - y
  \leqslant \frac{x}{2} \leqslant y \leqslant x$.
\end{enumerate}


\pause


\textcolor{white}{Dans tous les cas $|x-y| \leqslant \min(|x|,|y|)$ et on peut utiliser le lemme 
\vref{lemme::plusExact}.}


\end{frame}






\begin{frame}
  \begin{itemize}
  \item   Concrètement, à quoi correspond cette condition $\dfrac{x}{2} \leqslant y \leqslant 2x$?

\item  Demandez-vous ce que l'on peut dire de l'écart maximum entre les exposants de $x$ et $y$.
  \end{itemize}
\end{frame}




\subsection{Atelier Padawan \# 3: somme compensée de flottants quelconques} 



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.7\textheight]{vador}
\end{center}
%\end{figure}

\end{frame}





\begin{frame}
  

\begin{theorem}[Fast2Sum - \textsc{Dekker} \& \textsc{Kahan}]\label{th::Fast2Sum}
On considère  deux VF $x$  et $y$ tels que  $|x| \geqslant |y|$  et l'algorithme
suivant:

\begin{algo}[numbered]
\STATE{$s$ \recoit{} $x\oplus y$ }
\STATE{$y_v$\recoit{} $s\ominus x$}
\STATE{$d$ \recoit{} $y \ominus y_v$}
\RETURN{$(s,d)$}
\end{algo}
  
Alors $x+y=s+d$ avec $s=x\oplus y$ et $d={\rm err}(x\oplus y)$. De plus $s$ et $d$ ne se chevauchent pas.

\end{theorem}

\pause


\begin{itemize}
\item  \textbf{si} $\mathbf{x}$  \textbf{et} $\mathbf{y}$  \textbf{sont de  même
    signe    OU    si}    $\mathbf{|y|    \leqslant    \frac{|x|}{2}}$:    alors
  $\frac{x}{2}\leqslant s \leqslant 2x$ et on peut appliquer le lemme;
\item \textbf{sinon}:  on a $x$ et  $y$ de signes opposés  ET $y> \frac{|x|}{2}$
  alors si $y$  est négatif $x/2 < -y  < x$ et sinon $-x/2<y<-x$.  Dans les deux
  cas, d'après  le lemme  de \textsc{Sterbenz}, $s$  est calculée  exactement et
  alors $y_v=y$.
\end{itemize}



\end{frame}

\begin{frame}\frametitle{Somme compensée}


\color{white}

\begin{tabular}[!h]{rp{5em}p{2.7em}p{4.5em}p{2.5em}l}
  $x$ & \fbox{ $x_1$\hspace{4.1em}} & \fbox{$x_2$\hspace{2.2em}} & & & \\
  $+y$ & & \fbox{$y_1$\hspace{2.2em}} & \fbox{$y_2$\hspace{4em}} & & \\
  $=s$ & \fbox{$x_1 \textcolor{black}{y_1}$\hspace{3.4em}} & \fbox{$x_2+y_1$} & \ $y_2$ perdu & & \\
  $-x=y_v$ & &\fbox{$y_1$\hspace{2.2em}} & \fbox{$0\textcolor{black}{x_1}$\hspace{3.2em}} & & \\
  $-y=-d$ & & & \fbox{$-y_2$\hspace{3.2em}} & \fbox{$0\textcolor{black}{x_1}$\hspace{1em}} & on récupère l'erreur
\end{tabular}

\end{frame}












\begin{frame}[fragile]

  \begin{lstlisting}
def fast2sum(x,y):
    if abs(x) >= abs(y):
        s  = x + y
        yv = s - x
        d  = y - yv
        return (s,d)
    else:
        return fast2sum(y,x)
\end{lstlisting}
\end{frame}



\begin{frame}[fragile]

  \begin{lstlisting}
In [100]: fast2sum(2.0**54,1.0)
Out[100]: (1.8014398509481984e+16, 1.0)
\end{lstlisting}
\pause
\begin{lstlisting}
In [101]: fast2sum(2.0**54,2.0)
Out[101]: (1.8014398509481984e+16, 2.0)
\end{lstlisting}
\pause
\begin{lstlisting}
In [102]: fast2sum(2.0**54,3.0)
Out[102]: (1.8014398509481988e+16, -1.0)
\end{lstlisting}
\pause
\begin{lstlisting}
In [103]: fast2sum(2.0**54,4.0)
Out[103]: (1.8014398509481988e+16, 0.0)
\end{lstlisting}
\pause
\begin{lstlisting}
In [104]: fast2sum(2.0**54,5.0)
Out[104]: (1.8014398509481988e+16, 1.0)
  \end{lstlisting}
  
\end{frame}



\begin{frame}
\begin{theorem}[2Sum - \textsc{Knuth} ]\label{th::2Sum}
On considère  deux VF $x$  et $y$   et l'algorithme
suivant:

\begin{algo}[numbered]
\STATE{$s$ \recoit{} $x\oplus y$ }
\STATE{$y_v$\recoit{} $s\ominus x$}
\STATE{$x_v$\recoit{} $s\ominus y_v$}
\STATE{$y_a$\recoit{} $y\ominus y_v$}
\STATE{$x_a$\recoit{} $x\ominus x_v$}
\STATE{$d$ \recoit{} $x_a \oplus y_a$}
\RETURN{$(s,d)$}
\end{algo}
  
Alors $x+y=s+d$ avec $s=x\oplus y$ et $d={\rm err}(x\oplus y)$. De plus $s$ et $d$ ne se chevauchent pas.

\end{theorem}

\end{frame}




\begin{frame} \frametitle{Somme compensée d'un nombre quelconque de flottants}
  \small
\begin{center}
\tikzstyle{int}=[draw, fill=blue!20, minimum size=2em]
\tikzstyle{init} = [pin edge={<-,thin,white}]
\tikzstyle{fin} = [pin edge={->,thin,white}, pin position = below]
\tikzstyle{sort} = [pin edge={->,thin,white}, pin position = right]
\tikzstyle{entre} = [pin edge={<-,thin,white}, pin position = left]

\begin{tikzpicture}[node distance=2.9cm,auto,>=latex']
  \node [int, pin={[init]$x_1$}, pin={[fin]$e_1$},pin={[sort]$s_1$}] (a) {\textcolor{blue}{\texttt{twoSum}}}; %bloc 1
  \node (b) [left of=a,node distance=1.5cm, coordinate] {a}; % noeud d'entrée
  \node [int,pin={[entre]}, pin={[init]$x_2$}, pin={[fin]$e_2$},pin={[sort]$s_2$}] (c) [right of=a] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 2
  \node [int,pin={[entre]}, pin={[init]$x_3$}, pin={[fin]$e_3$},pin={[sort]$s_3$}] (d) [right of=c] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 3
  \node [int,pin={[entre]}, pin={[init]$x_4$}, pin={[fin]$e_4$}] (e) [right of=d] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 4
  \node [coordinate] (end) [right of=e, node distance=1.5cm]{}; % noeud fin
  \draw[->] (b)node[left] {$x_0$} --(a) ; % entrée
  \draw[->] (e) --(end)node[right] {$s$} ; % fin
 \end{tikzpicture}

\end{center}


\end{frame}


\begin{frame}[fragile] \frametitle{Somme compensée d'un nombre quelconque de flottants}
\begin{lstlisting}
def sommeKahan(liste):
    (s,c) = (0.,0.)
    for x in liste:
        (s,c) = fast2sum(s, x + c)
    return s
\end{lstlisting}

\pause

\begin{lstlisting}
def sommePichat(liste):
    s,e = 0.,0.
    for x in liste:
        (s,c) = fast2sum(s, x)
        e += c
    return s + e
\end{lstlisting}

\end{frame}











\begin{frame}
$x_0=2^{53}-1$, $x_1=2^{53}$ et $x_2=-(2^{54}-2)$


\pause


\begin{center}
\tikzstyle{int}=[draw, fill=blue!20, minimum size=2em]
\tikzstyle{init} = [pin edge={<-,thin,white}]
\tikzstyle{fin} = [pin edge={->,thin,white}, pin position = below]
\tikzstyle{sort} = [pin edge={->,thin,white}, pin position = right]
\tikzstyle{entre} = [pin edge={<-,thin,white}, pin position = left]

\begin{tikzpicture}[node distance=3.1cm,auto,>=latex']
  \node [int, pin={[init]$2^{53}$}, pin={[fin]$-1$},pin={[sort]$2^{54}$}] (a) {\textcolor{blue}{\texttt{twoSum}}}; %bloc 1
  \node (b) [left of=a,node distance=1.5cm, coordinate] {a}; % noeud d'entrée
  \node [int,pin={[entre]}, pin={[init]$-(2^{54}-2)$}, pin={[fin]$0$}] (c) [right of=a] {\textcolor{blue}{\texttt{twoSum}}}; % bloc 2
  \node [coordinate] (end) [right of=c, node distance=1.5cm]{}; % noeud fin
  \draw[->] (b)node[left] {$2^{53}-1$} --(a) ; % entrée
  \draw[->] (c) --(end)node[right] {$2$} ; % fin
 \end{tikzpicture}
\end{center}

\begin{exercice}\label{exo::2sum}
  Expliquez les résultats trouvés. Que va faire l'algorithme de somme compensée?
  Et celui de somme en cascade?
\end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
In [105]: sommePichat([1. / n for n in range(1,100001)])
Out[105]: 12.090146129863427

In [106]: sommeKahan([1. / n for n in range(1,100001)])
Out[106]: 12.090146129863427

In [107]: sum([1. / n for n in range(1,100001)])
Out[107]: 12.090146129863335

In [108]: sum([1. / n for n in range(100000,0,-1)])
Out[108]: 12.090146129863408
  \end{lstlisting}

\pause

\begin{lstlisting}
sage: sum(1. / n, n , 1 , 100000).n(64)
12.0901461298634279
\end{lstlisting}

\end{frame}




\section{Des sujets de Bac maladroits...}

\begin{frame}[fragile]
Le sujet du Bac  S des Centres Étrangers 2012 fait étudier la  suite (vu dans BV
APMEP 507):

$$
I_{n+2}= \frac{1}{2} {\rm e} -  \frac{n+1}{2} I_n, \qquad I_1= \frac{1}{2} ({\rm
  e} -1)
$$

\pause

\begin{lstlisting}
def bac(n):
    if n == 1:
        return 0.5 * (exp(1.) - 1.)
    else:
        return (0.5 * (exp(1.) - (n - 1) * bac2012(n - 2)))
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]

  \begin{multicols}{2}
    \begin{lstlisting}
In [1]: [(2*k + 1,bac(2*k + 1)) for k in range(30)]
Out[1]: 
[(1, 0.8591409142295225),
 (3, 0.5),
 (5, 0.35914091422952255),
 (7, 0.2817181715409549),
 (9, 0.2322682280657029),
 (11, 0.197799773901008),
 (13, 0.17234227082347453),
 (15, 0.15274501846520083),
 (17, 0.13718076650791589),
 (19, 0.12451401565827958),
 (21, 0.11400075764672679),
 (23, 0.10513258011552784),
 (25, 0.09754995284318846),
 (27, 0.09099152726807258),
    \end{lstlisting}
    


\begin{lstlisting}
 (29, 0.08525953247650642),
 (31, 0.0802479270819263),
 (33, 0.07517408091870181),
 (35, 0.08118153861159172),
 (37, -0.1021267807791284),
 (39, 3.299549749032962),
 (41, -64.63185406642971),
 (43, 1358.6280763092534),
 (45, -29888.458537889346),
 (47, 687435.9055123692),
 (49, -16498460.373155948),
 (51, 412461510.6880396),
 (53, -10723999276.52989),
 (55, 289547980467.66614),
 (57, -8107343453093.293),
 (59, 235112960139706.84)]
.
\end{lstlisting}
  \end{multicols}
\end{frame}










\begin{frame}[fragile]\frametitle{Banque chaotique}

Exemple dû à Jean-Michel Muller  (in \cite{MullerEtAl2010})

\pause

{\itshape 
M. X a récemment été à sa banque (Chaotic Bank Society), pour connaître les nouvelles offres proposées aux
meilleurs clients. Son banquier lui propose l'offre suivante: \og vous déposez tout d'abord e - 1 euros sur votre compte
(où e = 2.7182818... est la base du logarithme népérien). La première année, nous prenons 1 euro sur votre compte de
frais de gestion. Par contre, la deuxième année est plus intéressante pour vous, car nous multiplions votre capital restant
par 2 et prenons 1 euro de frais de gestion. La troisième année est encore plus intéressante, car nous multiplions votre
capital par 3 et prenons 1 euro de frais de gestion. Et ainsi de suite : la n-ième année, nous multiplions votre capital par n
et prenons 1 euro de frais de gestion. Intéressant, non? \fg{} Pour prendre sa décision, M. X décide de demander l'aide
d'un informaticien et se retourne vers vous.
}

\end{frame}



\begin{frame}[fragile]

  \begin{lstlisting}
def chaotic(n):
    cpt = exp(1) - 1
    for i in range(1,n + 1):
        cpt = i*cpt - 1
    return cpt
  \end{lstlisting}

\pause

\begin{align*}
c_n&=&n!\times \left(c_0-1- \frac{1}{2!} - \frac{1}{3!} -\cdots - \frac{1}{n!} \right) \\
&=&n!\times(c_0-({\rm e}-1)+ \frac{1}{(n+1)!} + \frac{1}{(n+2)!}+\cdots )
\end{align*}

\end{frame}





\section{Lectures recommand\'ees pour aller plus loin}





\begin{frame}
  \renewcommand{\bibname}{Lectures recommand\'ees pour aller plus loin}
\nocite{*}


{\tiny \color{white}
\bibliography{JA2014}
}
\end{frame}


\end{document}

%%% Local Variables: 
%%% TeX-master: t
%%% End: 
