\documentclass[10pt,a4paper,chinois,russe,biblio]{article}
\usepackage{etex}
\usepackage[euler,utf8x]{preambuleTrm}
\usepackage{geometry}
\geometry{papersize={21cm,29.7cm}}
\geometry{margin=1cm,top=1.5cm,bottom=2cm}

\usepackage{textcomp}
\usepackage{ mathtools,xlop,longtable}

\hypersetup{
pdftitle={Mathematice - Dichotomie}, pdfauthor ={ Guillaume CONNAN}}


\title{ La complexité c'est simple comme la dichotomie (Lycée Maths/ISN)
}

\author{ Guillaume \textsc{Connan}\footnote{\url{Guillaume.Connan@univ-nantes.fr}} - \textsc{Irem} de Nantes}

\date{ JA \textsc{Irem} de Nantes - 8 avril 2015}


\usepackage{algo,bclogo}

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


\newcounter{definit}\newcounter{propri}
\newcounter{theor}\newcounter{retenir}
\newcounter{remar}


\newenvironment{Definition}[1][]{%
\refstepcounter{definit}
\begin{bclogo}[ombre=true,logo=\bcbook,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont    D\'efinition  \thedefinit\ : #1}}
{\end{bclogo}}



\newenvironment{Remarque}[1][]{%
\refstepcounter{remar}
\begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont  Remarque   \theremar\ : #1}}
{\end{bclogo}}



\newenvironment{Propriete}[1][]{%
\refstepcounter{propri}
\begin{bclogo}[ombre=true,logo=\bccoeur,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont    Propri\'et\'e  \thepropri\ : #1}}
{\end{bclogo}}




\newenvironment{Theoreme}[1][]{%
\refstepcounter{theor}
\begin{bclogo}[ombre=true,logo=\bctrefle,arrondi=0.05,couleur=white]{\color{black}\bfseries\fontfamily{ugq}\selectfont Th\'eor\`eme
    \thetheor\ : #1}}
{\end{bclogo}}



\newenvironment{Retenir}[1][]{%
\refstepcounter{retenir}
\begin{bclogo}[logo=\bcnote,arrondi=0.05,couleur=white]{\color{black}\bfseries\small\fontfamily{ugq}\selectfont    \`A retenir (\theretenir)\ : #1}}
{\end{bclogo}}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/PREPA/IPT/2014_15/Poly/}{/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/}} 

\usepackage[figurename=,labelformat=empty]{caption}



\begin{document}

\maketitle


\begin{Abstract}
La dichotomie,  c'est couper un  problème en  deux. On ne  la présente
  souvent au
  lycée que dans le cadre restreint  de la recherche dichotomique de la solution
  réelle d'une  équation du  type $f(x)=0$ et  on la dénigre  car elle  est bien
  plus lente  que la fulgurante méthode  des tangentes. Pourtant, elle  est bien
  plus  riche  que  son  utilisation  dans  ce  contexte  étroit  le  laisserait
  penser.  Nous  en   profiterons  pour  introduire  la   notion  de  complexité
  algorithmique.
\end{Abstract}

\setlength{\parindent}{0mm}

\section{Le lancer de piano ou comment faire de l'informatique sans ordinateur...}

\subsection{L'expérience}

Une entreprise de déménagement syldave veut réduire son personnel et rationnaliser ses
méthodes de transport de  piano. Elle engage un spécialiste de  chez Dicho \& Co
qui propose  l'approche scientifique suivante. L'entreprise  achemine $k$ pianos
en bas du bâtiment de l'Université de Klow qui a $N=2^n$ étages, le rez-de-chaussée
portant le numéro 0.

\begin{figure}[ht]
  \centering
  \includegraphics[height=5cm]{piano}
  \caption{Université de Klow\label{fig:piano} }
\end{figure}

Le but de l'expérimentation est de  déterminer l'étage à partir duquel lancer un
piano par la fenêtre lui (le piano..) est fatal.

On suppose qu'un tel étage existe et que le rez-de-chaussée n'est pas fatal.

On  suppose également  que  tant que  le  piano  survit au  lancer,  on peut  le
réutiliser.  Pour économiser  le temps  et le  dos des  expérimentateurs, on  va
chercher un algorithme qui minimise le  nombre d'essais effectués (et non pas le
nombre de pianos détruits).


Une première idée  serait de commencer au rez-de-chaussée et  de lancer un piano
de chaque étage jusqu'à atteindre l'étage  fatal. Si jamais l'étage fatal est le
dernier, cela nécessitera d'effectuer ??? essais: c'est le pire cas.

Si l'on considère  que tous les étages sont potentiellement  fatals avec la même
probabilité, on effectuera avec cette méthode ???? essais en moyenne.

Mais on peut faire mieux...Comment? (NE TOURNEZ PAS LA PAGE TOUT DE SUITE)

\subsection{Diviser pour régner}


\begin{flushleft}
\begin{minipage}[t]{3.5cm}
\begin{figure}
  \includegraphics[width=3.5cm]{sunzi}
\caption{\begin{CJK}{UTF8}{song}{\large 孫子}\end{CJK}\\
(544–496 av. J.-C.)
}
\end{figure}
\end{minipage}
\end{flushleft}
\vspace{-3.6cm}
\begin{flushright}
\begin{minipage}[t]{0.75\linewidth}


\begin{quote}
 \textit{Le commandement  du grand nombre  est le même pour  le petit nombre,  ce n'est
  qu'une question de division en groupes.}

  \begin{flushright}
    in \og L'art de la guerre\fg{} 
\begin{CJK}{UTF8}{song}
{\large 孙子兵法}
\end{CJK}
de Sun Zi (VI\eme siècle avant JC)
  \end{flushright}
\end{quote}

\end{minipage}
\end{flushright}
\vspace{1.6cm}

Nous allons diviser l'immeuble en deux  parties égales en considérant l'étage du
milieu:  si  cet  étage  est  fatal,  il suffira  de  chercher  dans  la  moitié
inférieure, sinon,  dans la  moitié supérieure de  l'immeuble. Nous  allons donc
effectuer une \textbf{recherche dichotomique} de l'étage fatal.


\begin{algo}
\STATE{inf\recoit{}Étage inférieur}
\STATE{sup\recoit{}Étage supérieur}
\STATE{milieu\recoit{} $({\rm inf} + {\rm sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu + 1, sup)}
\ENDIF 
\end{algo}


Quand  va-t-on  s'arrêter  de  découper  l'immeuble?  Lorsqu'il  n'y  aura  plus
d'ambiguité, c'est-à-dire lorsque l'étage supérieur sera juste au-dessus de l'étage
inférieur.
La fonction devient:


\begin{algo}
 \FUNC{ChercherEntre}{\pfarg{inf, sup}{Entiers}}{Entier}
\COMMENT{pré-condition: il existe au moins un étage fatal entre inf et sup et inf n'est pas fatal et inf < sup}
\COMMENT{invariant: le plus petit étage fatal est entre inf (non compris) et sup}
\COMMENT{post-condition: la valeur retrournée est le plus petit étage fatal}
\IF{sup == inf + 1}
\RETURN{sup}
\ELSE
\STATE{milieu\recoit{} $({\rm inf} + {\rm sup})/2$}
\IF{estFatal(milieu)}
\STATE{ChercherEntre(inf,milieu)}
\ELSE
\STATE{ChercherEntre(milieu, sup)}
\ENDIF
\ENDIF 
\end{algo}




Qu'a-t-on gagné?  Mais d'abord, est-ce  que notre fonction nous  renvoie l'étage
attendu? Et d'abord, renvoie-t-elle quelque chose?

Déterminer   les  réponses   à  ces   questions  constitue   les  trois   étapes
indispensables de l'étude d'un algorithme:

\begin{enumerate}
\item étude de  la\textit{ terminaison} de l'algorithme: est-ce  que la fonction
  renvoie effectivement une valeur?
\item étude  le la \textit{correction}  de l'algorithme: est-ce que  la fonction
  renvoie la valeur attendue?
\item  étude  de la  \textit{complexité}  de  l'algorithme: peut-on  estimer  la
  vitesse d'exécution de cet algorithme?
\end{enumerate}



NE REGARDEZ PAS TOUT DE SUITE LA PAGE SUIVANTE....

\vfill

\eject


\begin{enumerate}
\item Pour  répondre à  la première  question, il  suffit de  remarquer qu'au  départ,
l'intervalle d'étude  est l'ensemble $\bigl\{1,2,...,N\bigr\}$ de  longueur $N$. Après
chaque appel récursif, la longueur de l'intervalle est divisée par deux. 

Notons $\ell_i$ cette  longueur après $i$ appels récursifs. La  suite $\ell$ est
géométrique de raison $1/2$ et de premier terme $N$.

On a donc $\ell_i=\frac{N}{2^i}=\frac{2^n}{2^i}=2^{n-i}$. Ainsi $\ell_n=1$ et
l'algorithme s'arrête. 

\item Vérifions d'abord que l'invariant est valide à chaque appel récursif:
  c'est  vrai  au départ  car  on  précise qu'un  étage  fatal  existe entre  le
  rez-de-chaussée et le dernier étage.

  Par construction, on choisit inf et sup pour que le plus petit reste entre inf
  et sup et que la borne inférieure ne soit pas fatale.

  Quand la  récursion s'arrête,  l'intervalle est en  fait $\bigl\{\mathrm{inf},
  \mathrm{inf} + 1\bigr\}$ et inf
  n'est pas fatal donc $\mathrm{inf} + 1$ l'est et est la valeur cherchée, eh!

\item Combien  de temps nous a-t-il  fallu? Mais d'abord comment  mesure-t-on le
  temps?

  Nous ne sommes pas sur machine mais dans la grande université de Klow. Il faut
  compter le temps de chute, le temps  de remontée des pianos encore en état, le
  temps  de manipulation  pour passer  les pianos  par la  fenêtre, l'examen  de
  l'état du piano ayant chu.  Selon
  l'efficacité des muscles
  et l'état  de santé  des déménageurs,  nous pouvons poser  que ces  temps sont
  proportionnels  au nombre  d'étages, mis  à part  le temps  de passage  par la
  fenêtre   qui   est   constant   ainsi   que  l'examen   du   piano   par   un
  expert\footnote{C'est  ce  qui correspondra  par  exemple  en informatique  au
    parcours d'une liste chaînée.}.


  ...Mais  c'est   un  peu  compliqué...On   va  supposer  que   l'ascenseur  est
  ultra-performant et que  les pianos sont très lourds ce  qui entraîne que tous
  ces temps  sont à peu  près constants, quelque soit  l'étage\footnote{C'est ce
    qui  correspondra  par exemple  en  informatique  au parcours  d'un  tableau
    statique.}.

  Il suffit donc de compter combien de lancers ont été effectués. La réponse est
  dans l'étude faite  pour prouver la terminaison: c'est à  l'étape $n+1$ que l'on
  atteint la condition de sortie de l'algorithme.

  Que vaut $n$? On  a posé au départ que le nombre  d'étages était une puissance
  de 2: $N=2^n$. Ainsi, $n=\log_2N$.

  Finalement, le nombre de tests effectués est égal au logarithme en base 2 du
  nombre d'étages. Et  le temps? Et bien,  ce n'est pas ce  qui nous intéressait
  puisqu'on nous  demandait de mesurer  le nombre  de tests effectués  mais cela
  nous a  permis d'introduire la  notion de \textit{complexité}  d'un algorithme
  dont la mesure va dépendre de l'unité  choisie et sera plus ou moins difficile
  à déterminer.


  Si notre  immeuble a  1024 étages,  nous sommes  donc passés  de 1022  tests au
  maximum à  10 tests  ce qui  n'est pas  négligeable, surtout  pour le  dos des
  déménageurs.

\end{enumerate}


\subsection{Le bug de Java}

Pendant 9  ans, jusqu'en 2006, les  fonctions de recherche dichotomique  en Java
cachaient un bug...

Voici      ce     que      l'on      trouvait      dans     la      bibliothèque
\Colorbox{blue!10}{\lstinline{java.util.Arrays}}:


\begin{javacode}
public static int binarySearch(int[] a, int key) {
         int low  = 0;
         int high = a.length - 1;

         while (low <= high) {
             int mid    = (low + high) / 2;
             int midVal = a[mid];

             if (midVal < key)
                 low = mid + 1
             else if (midVal > key)
                 high = mid - 1;
             else
                 return mid; // key found
         }
         return -(low + 1);  // key not found.
     }  
\end{javacode}

Regardez la ligne 6: \mintinline{java}{int mid    = (low + high) / 2;}.

Tout va bien...mais en fait il faut se souvenir que les entiers sont codés en général
sur 64  bits et  que le  successeur de  $2^{63}-1$ n'est  pas $2^{63}$  mais son
opposé car on représente les nombres relatifs sur machine d'une manière spéciale
\footnote{Voir      par     exemple      le      bug      de     l'an      2038:
  \href{https://fr.wikipedia.org/wiki/Bug\_de\_l\%27an\_2038}{https://fr.wikipedia.org/wiki/Bug\_de\_l\%27an\_2038}}. Étudier
la manière de représenter les relatifs  sur machine est un problème intéressant:
un exemple de recherche sur ce thème est donné en \vref{exo::comp2}.

Le bug a été corrigé\footnote{\href{http://bugs.java.com/bugdatabase/view\_bug.do?bug\_id=5045582}{http://bugs.java.com/bugdatabase/view\_bug.do?bug\_id=5045582}} en remplaçant cette ligne par:

\mintinline{java}{ int mid = low + ((high - low) / 2);}


Il faudra faire de même dans nos fonctions!




\subsection{Questions subsidiaires}
\begin{enumerate}
\item  \textbf{Que  se  passe-t-il  si   nous  avons  moins  de}  $\mathbf{n=  }$
  \textbf{log}$\mathbf{_2}$\textbf{(N) pianos pour
    tester?}

 Aïe! Notre  dichotomie ne peut aller  jusqu'au bout. L'idée est  de l'appliquer
 $k-1$ fois ($k$  étant le nombre de  pianos à diposition). Il se  peut que nous
 n'ayons pas abîmé de piano. Il se peut aussi que nous ayons cassé un piano à
 chaque fois si  l'étage fatal est très  petit. Il nous reste donc  \textit{dans le pire
 des cas} un piano et $N/2^{k-1}$ étages non testés. 

 On  va  donc partir  du  plus  bas et  remonter  jusqu'à  casser notre  dernier
 piano. \textit{Dans le pire des cas}, ce sera le dernier testé.

 Ainsi, s'il nous reste  assez de pianos (si l'étage fatal  n'est pas trop bas),
 nous pourrons appliquer  la dichotomie jusqu'au bout. Dans le  pire des cas, il
 faudra effectuer $k-1+\frac{N}{2^{k-1}}-1$ tests.

 \item \textbf{Que se passe-t-il si nous n'avons que 2 pianos et que n est pair?}
   
 Si l'on applique une fois la dichotomie, il nous restera N/2 tests à effectuer.

 On peut faire mieux...
 
 Il suffit  de découper l'immeuble  en $\sqrt{N}=2^{n/2}$ paquets  de $\sqrt{N}$
 étages.

 On  commence par  tester  l'étage $\sqrt{N}$  puis éventuellement  $2\sqrt{N}$,
 etc. Bref, on effectue une recherche séquentielle du paquet fatal.

 Ensuite, il  suffit d'utiliser  le deuxième  piano (le  premier est  cassé pour
 déterminer  le paquet  fatal) afin  d'effecteur une  recherche séquentielle  de
 l'étage  fatal  cette  fois. Dans  le  pire  des  cas,  cela va  nous  demander
 $\sqrt{N}-1$ tests. 

 Bref, dans le pire des cas, nous effectuerons $2\sqrt{N}-1$ tests.


 \item \textbf{Que se passe-t-il quand N n'est pas une puissance de 2?}

   Ce  n'est   pas  grave  car  le   nombre  de  tests  croît   avec  le  nombre
   d'étages dans limmeuble. Or, pour tout  entier naturel N, il existe un entier
   $n$ tel que: 

   $$2^n \leqslant N < 2^{n+1}$$

   Si on  appelle T la  fonction qui, au nombre  d'étages, associe le  nombre de
   tests par la méthode dichotomique, alors:

   $$T(2^n)=n \leqslant T(N) < n+1$$
   
   donc $T(N)=n=\lfloor \log_2(N)\rfloor$.

   \item \textbf{Et si nous avions fait de la trichotomie}

     \begin{figure}[ht]
       \centering
       \includegraphics[height=4cm]{tricot}
       \caption{Trichotomie manuelle\label{fig:tricot} }
     \end{figure}

     On  pourrait penser  que diviser  notre immeuble  en 3  pourrait être  plus
     efficace  car   on  divise  la   taille  de  l'intervalle  suivant   par  3
     \textit{mais} on effectue au pire deux tests à chaque fois.

     Ainsi, dans  le pire  des cas  on effectuera  (en supposant  que N  est une
     puissance                               de                               3)
     $2\log_3(N)=2\frac{\ln(N)}{\ln(2)}\times\frac{\ln(2)}{\ln(3)}\simeq
     1,3\log_2(N)$ tests donc ce n'est pas mieux  et ça ne fera qu'empirer si on
     augmente le nombre de divisions...

     La division par 2 serait-elle magique?

\end{enumerate}


\section{Diviser ne permet pas toujours de régner}

Considérons un problème mathématique simple: la multiplication de deux entiers.

Vous savez additionner deux entiers de $n$ chiffres: cela nécessite $\lambda_1 n $ additions
de nombres de un chiffre compte-tenu des retenues avec $\lambda_1$ une constante positive.

Multiplier un entier de $n$ chiffres par un entier de 1 chiffre prend $\lambda_2 n$
unités de temps selon le même principe.

En utilisant  l'algorithme de l'école  primaire pour multiplier deux  nombres de
$n$ chiffres, on effectue $n$ multiplications d'un nombre de $n$ chiffres par un
nombre de  1 chiffre puis  une addition des $n$  nombres obtenus. On  obtient un
temps de calcul en $\lambda_3 n^2$.

On  peut espérer  faire  mieux  en appliquant  la  méthode \textit{diviser  pour
  régner}.

On  coupe par  exemple chaque  nombre en  deux parties  de $m=\lfloor  n/2\rfloor$
chiffres:

$$xy=(10^mx_1+x_2)(10^my_1+y_2)=10^{2m}x_1y_1+10^m(x_2y_1+x_1y_2)+x_2y_2$$




\begin{algo}
\FUNC{MUL}{\pfarg x entier ,y: entier}{entier}
\IF{n==1}
\RETURN{x.y}
\ELSE
\STATE{$m$ \recoit{} $\lfloor n/2\rfloor$}
\STATE{$x_1$ \recoit{} $\lfloor x/10^m\rfloor$}
\STATE{$x_2$\recoit{} $x$ mod $10^m$}
\STATE{$y_1$ \recoit{} $\lfloor y/10^m\rfloor$}
\STATE{$y_2$\recoit{} $y$ mod $10^m$}
\STATE{$a$ \recoit{} MUL($x_1$,$y_1$,m)}
\STATE{$b$ \recoit{} MUL($x_2$,$y_1$,m)}
\STATE{$c$ \recoit{} MUL($x_1$,$y_2$,m)}
\STATE{$d$ \recoit{} MUL($x_2$,$y_2$,m)}
\RETURN{$10^{2m}a+10^m(b+c)+d$}
\ENDIF
\end{algo}



Les divisions et  les multiplications par des  puissances de 10 ne  sont que des
décalages effectués en temps constant.

L'addition finale est en $\lambda n$ donc le temps d'exécution est défini par:

$$T(n)=4T(\lfloor n/2\rfloor) +\lambda n \qquad T(1)=1$$


Peut-on exprimez $T(n)$ explicitement en fonction de $n$ sans récursion?

Si  nous  avions une  idée  de  la solution,  nous  pourrions  la démontrer  par
récurrence.

Ça serait plus  simple si $n$ était  une puissance de
2. Voyons, posons $n=2^k$ et $T(n)=T(2^k)=x_k$.





Alors la relation de récurrence devient:

$$x_k=4x_{k-1}+\lambda 2^k \qquad x_0=1$$

On obtient:


$$x_k=4(4x_{k-2}+\lambda'  2^{k-1})+\lambda  2^k  =  4^kx_0+\sum_{i=1}^k\Lambda_k  2^k
=4^k+k\Lambda_k 2^k =n^2 + \Lambda_kn \log
n \sim n^2 $$

Car nous  verrons que l'on  peut encadrer  ce $\Lambda_k$ entre  deux constantes
positives dans la dernière section.


On montre alors par récurrence forte que ce résultat est vrai pour tout
entier naturel non nul $n$.



Bref, tout ça pour montrer que l'on n'a pas amélioré la situation...




\eject

\section{Et la recherche dichotomique d'une solution d'une équation réelle?}


Quel rapport entre la recherche dichotomique dans un tableau (ou un immeuble) et
la recherche des solutions d'une équation $f(x)=0$ dans $\bbr$?

Pour mettre en \oe  uvre une telle méthode, il faut donner  une précision. On ne
travaille que sur  des approximations décimales ou plutôt à  l'aide de nombres à
virgule flottante en base 2.

Par exemple, si nous cherchons une approximation de $x^2-2=0$ par la méthode de dichotomie avec
une précision de  $2^{-10}$ entre 1 et  2, il va falloir chercher  un nombre (un
étage) dans un tableau (un immeuble) de $2^{10}$ nombres (étages):


\begin{center}
\begin{tabular}[!h]{|c|c|c|c|c|c|}
  \hline
$1$      &      $1+2^{-10}$      &     $1+2\times      2^{-10}$&      $1+3\times
2^{-10}$&$\cdots$&$1+2^{10}\times 2^{-10}$\\
\hline
\end{tabular}
\end{center}


Notre  fonction  booléenne  \og  estFatal\fg{}  est alors  le  test  $x  \mapsto
\mathtt{x*x <= 2}$ et l'on va chercher  une cellule de ce tableau par dichotomie
comme on cherchait un étage dans un immeuble.

\begin{pythoncode}
  def racineDicho(prec):
    cpt = 0
    inf = 1
    sup = 2
    while (sup - inf > prec):
        m = inf + (sup - inf) / 2
        cpt += 1
        if m*m <= 2:
            inf = m
        else:
            sup = m
    return sup,cpt
\end{pythoncode}


Nous obtenons:

\begin{pythoncode}
In [1]: racineDicho(2**(-10))
Out[1]: (1.4150390625, 10)

In [2]: racineDicho(2**(-15))
Out[2]: (1.414215087890625, 15)

In [3]: racineDicho(2**(-20))
Out[3]: (1.4142141342163086, 20)

In [4]: racineDicho(2**(-30))
Out[4]: (1.4142135623842478, 30)

In [5]: racineDicho(2**(-50))
Out[5]: (1.4142135623730958, 50)
\end{pythoncode}


Attention!  Il  faudra  s'arrêter  à  la précison  $2^{52}$  compte-tenu  de  la
représentation des nombres sur machine. N'hésitez pas à parcourir 

 \href{http://download.tuxfamily.org/tehessinmath/les\%20pdf/JA2014.pdf}{http://download.tuxfamily.org/tehessinmath/les\%20pdf/JA2014.pdf}

ou 

\href{http://download.tuxfamily.org/tehessinmath/les\%20pdf/PolyAnalyse14.pdf}{
http://download.tuxfamily.org/tehessinmath/les\%20pdf/PolyAnalyse14.pdf}

pour plus de précisions ;-)


On \og voit\fg{} que le nombre de tests correspond à la longueur de l'intervalle
exprimé  en  \og logarithme  de  la  précision\fg{}:  ici, l'intervalle  est  de
longueur 1.




\section{La complexité sur machine: approche expérimentale et théorique}


\subsection{Méthode scientifique ;-) }


Le  problème:  \textit{on dispose  d'une  liste  de  N nombres.  Déterminez  les
  triplets dont la somme est nulle}.

Utilisons la force brute (pour le lecteur impatient: nous ferons mieux plus tard...):

\begin{pythoncode}
def trois_sommes(xs):
    N = len(xs)
    cpt = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                if xs[i] + xs[j] + xs[k] == 0:
                    cpt += 1
    return cpt
\end{pythoncode}


Comparons les temps pour différentes tailles:


\begin{pythoncode}
In [1]: %timeit trois_sommes([randint(-10000,10000) for k in range(100)])
10 loops, best of 3: 27.5 ms per loop

In [2]: %timeit trois_sommes([randint(-10000,10000) for k in range(200)])
1 loops, best of 3: 216 ms per loop

In [3]: %timeit trois_sommes([randint(-10000,10000) for k in range(400)])
1 loops, best of 3: 1.82 s per loop
\end{pythoncode}


On peut plutôt s'intéresser aux ratios:

\begin{pythoncode}
from time import perf_counter
from math import log

def temps(xs):
    debut = perf_counter()
    trois_sommes(xs)
    return perf_counter() - debut

t = [temps(range(100 * 2**k)) for k in range(4)]

ratio = [t[k + 1] / t[k] for k in range(3)]

def logD(x):
    return log(x)/log(2)

logratio = map(logD,ratio)
\end{pythoncode}

et on obtient:

\begin{pythoncode}
In [4]: ratio
Out[4]: [7.523860206447286, 9.118789882406599, 8.5098312160934]

In [5]: list(logratio)
Out[5]: [2.940628541715559, 3.133284732580891, 3.128693841844642]  
\end{pythoncode}


Bon, il semble que quand la taille double, le temps est multiplié par $2^3$.

Il ne  semble donc  pas aberrant  de considérer que  le temps  de calcul  est de
$aN^3$ mais que vaut $a$?



\begin{pythoncode}
In [6]: temps(range(400))
Out[6]: 4.005484320001415  
\end{pythoncode}

$4,00 = a\times 400^3 $ donc $a\approx 6,25\times 10^{-8}$

Donc pour $N=1000$, on devrait avoir un temps de $6,25\times 10^{-8}\times10^9=62,5$

\begin{pythoncode}
In [7]: temps(range(1000))
Out[7]: 68.54615448799996  
\end{pythoncode}

Presque mais Python reste Python...




Voici la même chose en C, sans vraiment chercher à optimiser le code.

\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{c}
#include <stdio.h>
#include <time.h>

typedef int Liste[13000];

int trois_sommes(int N)
{
  int cpt = 0;
  Liste liste;

  for ( int k = 0; k < N; k++)
    {
      liste[k] = k - (N / 2);
    }
  
  for (int i = 0; i < N; i++)
    {
      for (int j = i + 1; j < N; j++)
	{
	  for (int k = j + 1; k < N; k++)
	    {
	      if (liste[i] + liste[j] + liste[k] == 0) {cpt++;}
	    }
	}
     }
  return cpt;
}

void chrono(int N)
{
  clock_t temps_initial, temps_final;
  float temps_cpu;

  temps_initial = clock();
  trois_sommes(N);
  temps_final   = clock();
  temps_cpu = ((double) temps_final - temps_initial) / CLOCKS_PER_SEC;
  printf("Temps en sec pour %d : %f\n",N, temps_cpu);

}
  
int main(void)
{
  chrono(100);
  chrono(200);
  chrono(400);
  chrono(800);
  chrono(1600);
  chrono(3200);
  chrono(6400);
  chrono(12800);

  return 1;
}
\end{minted}


Et on obtient:

\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{sh}
$ gcc  -std=c99 -Wall -Wextra  -Werror -pedantic -O4 -o somm3 Trois_Sommes.c
$ ./somm3 
Temps en sec pour 100 : 0.00000
Temps en sec pour 200 : 0.000000
Temps en sec pour 400 : 0.020000
Temps en sec pour 800 : 0.090000
Temps en sec pour 1600 : 0.720000
Temps en sec pour 3200 : 5.760000
Temps en sec pour 6400 : 45.619999
Temps en sec pour 12800 : 360.839996
\end{minted}

On a la même évolution en $N^3$ avec  un rapport de 8 entre chaque doublement de
taille mais la constante est bien meilleure:

$45,61 = a\times 6400^3$ d'où $a\approx 1,74\times10^{-10}$

$360,84 = a\times 12800^3$ d'où $a\approx 1.72\times 10^{-10}$


\textbf{Conclusion}: Python  ou C,  l'algo est  le même et  on constate  la même
progression selon le cube de la taille.

Ce qui  nous intéresse en  premier lieu (et ce  que l'on mesurera  aux concours)
est donc un \textbf{ORDRE DΕ CROISSANCE}.


Cependant, les  temps sont  bien distincts:  ici, C  va 400  fois plus  vite que
Python ;-)

On a  donc une approche  expérimentale et  les expériences sont  plus facilement
menées que  dans les  autres sciences  et on  peut en  effectuer de  très grands
nombres.

La mauvaise  nouvelle, c'est  qu'il est difficile  de mesurer  certains facteurs
comme l'usage du cache, le comportement du ramasse-miettes, etc.

En C, on  peut regarder le code  assembleur généré mais avec  Python, c'est plus
mystérieux.


La bonne nouvelle, c'est qu'on peut cependant effectuer une analyse mathématique
pour confirmer nos hypothèses expérimentales.



\subsection{Notations}

\begin{center}
  %\begin{figure}
  \includegraphics[width=3cm]{hackers}
%\end{figure}
\end{center}



\begin{quote}
  {\it Brooks's Law [prov.]

\og Adding manpower to a late software project makes it later\fg{} -- a result
of  the fact that  the expected  advantage from  splitting work  among N
programmers is $O(N)$, but the complexity and
communications cost associated with  coordinating and then merging their
work is $O(N^2)$}
\begin{flushright}
  in \og The New Hacker's Dictionnary\fg{}\\
\href{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}{http://outpost9.com/reference/jargon/jargon\_17.html\#SEC24}
\end{flushright}
\end{quote}

Les notations  de \textsc{Landau}(1877-1938) ont  en fait été  crées par
Paul 
\textsc{Bachmann}(1837-1920) en 1894, mais bon, ce sont tous deux des 
mathématiciens allemands.

Par exemple, si l'on considère l'expression: $$f(n)=n+1+\frac{1}{n}+\frac{75}{n^2}-\frac{765}{n^3}+\frac{\cos(12)}{n^{37}}-\frac{\sqrt{\numprint{765481}}}{n^{412}}$$


Quand  $n$  est  \og  grand\fg{}, disons  $\numprint{10000}$,  alors  on
obtient:

$$f(\numprint{10000})=\numprint{10000}+1+0,0001+0,00000000075-0,0000000000000765+\text{
  peanuts}$$

Tous les  termes après  $n$ comptent  pour du beurre  quand $n$  est \og
grand\fg{}.  Donnons une définition pour plus de clarté:

\medskip

\begin{Definition}[\og Grand O\fg{}]
Soit $f$ et $g$ deux fonctions  de $\bbn$ dans $\bbr$. On dit que $f$
est un \og grand O\fg{} de $g$ et on note $f=O(g)$ ou $f(n)=O(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\leqslant
C|g(n)|$ pour tout $n\in \bbn$.
\end{Definition}



Dans  l'exemple précédent,  $\frac{1}{n} \leqslant  \frac{1}{1}\times 1$
pour tout entier $n$ supérieur à 1
donc $\frac{1}{n}=O(1)$.

De   même,  $\frac{75}{n^2}   \leqslant  \frac{75}{1^2}\times   1$  donc
$\frac{75}{n^2}=O(1)$ mais on peut dire mieux:
 $\frac{75}{n^2}\leqslant  \frac{75}{1}\times\frac{1}{n}$  et  ainsi  on
 prouve que $\frac{75}{n^2}=O \left(\frac{1}{n}\right)$.

En fait, un grand  O de $g$ est une fonction qui  est au maximum majorée
par un multiple de $g$.



On peut  cependant faire  mieux si l'on a  aussi une
minoration.

C'est le moment d'introduire une nouvelle définition:

\medskip


\begin{Definition}[\og Grand Oméga\fg{}]
  Soit $f$ et $g$ deux fonctions  de $\bbr$ dans lui-même. On dit que $f$
est un \og grand Oméga\fg{} de $g$ et on note $f=\Omega(g)$ ou $f(n)=\Omega(g(n))$ si,
et seulement si, il existe une constante strictement positive C telle que $|f(n)|\geqslant
C|g(n)|$ pour tout $n\in \bbn^*$.
\end{Definition}

\medskip


\begin{Remarque}
Comme   $\Omega$  est   une  lettre   grecque,  on   peut,   par  esprit
d'unification, parler de \og grand omicron\fg{} au lieu de \og grand O\fg{}...
\end{Remarque}


Si l'on a à la fois une minoration et une majoration, c'est encore plus précis et nous incite à
introduire une nouvelle définition:

\medskip


\begin{Definition}[\og Grand Théta\fg{}]
$f=\Theta(g)\Longleftrightarrow
  f=O(g)\ \ \wedge \ \ f=\Omega(g)
$
\end{Definition}


Voici maintenant une petite table pour illustrer les différentes classes
de complexité rencontrées habituellement:

\begin{center}
             \begin{tabularx}{\linewidth}{Y{3}}
	     \whline
             \backslashbox{coût}{$n$}&100&$\numprint{1000}$&$10^6$&$10^9$\\
             \whline
             $\log_2(n)$&$\approx7$&$\approx10$&$\approx 20$&$\approx 30$\\
             \hline
             $n\log_2(n)$&$\approx 665$&$\approx \numprint{10000}$&$\approx  2\cdot  10^{7}$&$\approx 3\cdot 10^{10}$\\
             \hline
             $n^2$&$10^4$&$10^6$&$10^{12}$&$10^{18}$\\
             \hline
             $n^3$&$10^6$&$10^9$&$10^{18}$&$10^{27}$\\
             \hline
             $2^n$&$\approx 10^{30}$&$>10^{300}$&$>10^{10^5}$&$>10^{10^8}$\\
             \whline
             \end{tabularx}
             \end{center}

Gardez en tête que l'âge de l'Univers est environ de $10^{18}$ secondes...


% \begin{NB}
%   Ce qui  nous intéressera,  c'est en  fait le  taux de  croissance du
%   temps  d'exécution,   c'est  pourquoi  ces notations   sont  très
%   pratiques  en  algorithmique car  elle  font  abstraction des  temps
%   d'accès mémoire, de la cadence  du processeur, etc. qui dépendent de
%   chaque machine et également des langages utilisés.
% \end{NB}

\subsection{Analyse mathématique}

\begin{flushleft}
\begin{minipage}[t]{2.25cm}
\begin{figure}
  \includegraphics[width=2.25cm]{knuth}
\caption{
D. E. Knuth \\
Né en 1938
}
\end{figure}
\end{minipage}
\end{flushleft}
\vspace{-4.6cm}
\begin{flushright}
\begin{minipage}[t]{0.85\linewidth}


Une   bonne  lecture   de   chevet   est  le   troisième   volume   de  \og   Zi
Arte\fg{} (\cite{knuth:vol3}).

Le temps  d'exécution est la somme  des produits (coût $\times$  fréquence) pour
chaque opération.

\begin{itemize}
\item le coût dépend de la machine, du compilateur, du langage;
\item la fréquence dépend de l'algorithme, de la donnée en entrée.
\end{itemize}



Par exemple, l'accès à un élément dans un itérateur en Python n'est pas gratuit.

\end{minipage}
\end{flushright}
\vspace{1.6cm}





\begin{pythoncode}
In [12]: xs = range(-500,501)


In [13]: %timeit xs[900]
10000000 loops, best of 3: 129 ns per loop
In [14]: %timeit xs[900] + xs[800] 
1000000 loops, best of 3: 292 ns per loop
In [15]: %timeit xs[900] + xs[800] + xs[700]
1000000 loops, best of 3: 424 ns per loop
\end{pythoncode}


Mais si on travaille sur une liste:

\begin{pythoncode}
In [22]: xs = list(range(-500,501))

In [23]: %timeit xs[900]
10000000 loops, best of 3: 40.7 ns per loop
In [24]: %timeit xs[900] + xs[800] 
10000000 loops, best of 3: 114 ns per loop
In [25]: %timeit xs[900] + xs[800] + xs[700]
10000000 loops, best of 3: 165 ns per loop  
\end{pythoncode}

oui mais:

\begin{pythoncode}
In [26]: %timeit range(-500,501)
1000000 loops, best of 3: 292 ns per loop
In [27]: %timeit list(range(-500,501))
100000 loops, best of 3: 13.9 µs per loop  
\end{pythoncode}





Dans notre algorithme des 3 sommes en python, on peut donc gagner du temps:

\begin{pythoncode}
def trois_sommes(xs):
    N = len(xs)
    cpt = 0
    for i in range(N):
        xi = xs[i]
        for j in range(i + 1, N):
            sij = xi + xs[j]
            for k in range(j + 1, N):
                if sij + xs[k] == 0:
                    cpt += 1
    return cpt  
\end{pythoncode}



C'est mieux:

\begin{pythoncode}
In [28]:  xs = list(range(-50,51))
In [29]: %timeit trois_sommes(xs)
100 loops, best of 3: 12.9 ms per loop

In [30]:  xs = list(range(-100,101))
In [31]: %timeit trois_sommes(xs)
10 loops, best of 3: 94.4 ms per loop

In [32]:  xs = list(range(-200,201))
In [33]: %timeit trois_sommes(xs)
1 loops, best of 3: 851 ms per loop

In [34]:  xs = list(range(-400,401))
In [35]: %timeit trois_sommes(xs)
1 loops, best of 3: 7.04 s per loop  
\end{pythoncode}

En C, ça ne changera rien, car le compilateur est intelligent et a remarqué tout
seul qu'il pouvait garder en mémoire certains résultats.


On peut visualiser en échelle log-log:

\begin{pythoncode}
tailles = [2**k for k in range(7,11)]*
listes = [list(range(- N//2, N//2 + 1)) for N in tailles]
t = [temps(xs) for xs in listes]
for taille in tailles:
    plt.loglog(tailles, t, basex = 2, basey = 2)
plt.title('Temps de calcul selon la taille de la liste en echelle log-log')
plt.xlabel('Taille des listes')
plt.ylabel('Temps en s')
\end{pythoncode}



%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{trois_sommes}
\end{center}
%\end{figure}

C'est assez rectiligne.

Regardons de nouveau le code des  trois sommes et comptons le nombre d'opérations:
% \begin{pythoncode}
% def trois_sommes(xs):
%     N = len(xs) 
%     cpt = 0
%     for i in range(N):
%         xi = xs[i]
%         for j in range(i + 1, N):
%             sij = xi + xs[j]
%             for k in range(j + 1, N):
%                 if sij + xs[k] == 0:
%                     cpt += 1
%     return cpt  
% \end{pythoncode}



\begin{center}

\begin{tabular}[!h]{|l|c|}
\hline
OPÉRATION & FRÉQUENCE\\
\hline
Déclaration de la fonction et du paramètre (l. 1)& 2\\
\hline
Déclaration de N, cpt et i (l. 2, 3 et 4)& 3\\
\hline
Affectation de N, cpt et i (l. 2, 3 et 4)& 3\\
\hline
Déclaration de xi (l. 5) & N\\
\hline
Affectation de xi (l. 5) & N\\
\hline
Accès à xs[i] (l. 5) & N\\
\hline
Déclaration de j (l.6) & N\\
\hline
Calcul de l'incrément de i (l. 6) & N\\
\hline
Affectation de j (l.6) & N\\
\hline
Déclaration de sij (l. 7) & $S_1$\\
\hline
Affectation de sij (l. 7) & $S_1$\\
\hline
Accès à xs[j] (l.7) & $S_1$\\
\hline
Somme (l.7) & $S_1$\\
\hline
Déclaration de k (l.8) & $S_1$\\
\hline
Incrément de j (l. 8) & $S_1$\\
\hline
Affectation de k (l.8) & $S_1$\\
\hline
Accès à x[k] (l.9) & $S_2$\\
\hline
Calcul de la somme (l.9) & $S_2$\\
\hline
Comparaison à 0 (l.9) & $S_2$\\
\hline
Incrément de cpt (l.9) & entre 0 et $S_2$\\
\hline
Affectation de la valeur de retour (l.11) &1\\
\hline
\end{tabular}


\end{center}


Que valent $S_1$ et $S_2$?

$$S_1=\sum_{i=0}^{N-1}N-(i+1)=\sum_{i'=0}^{N-1}i'=\frac{N(N-1)}{2} $$


\begin{eqnarray*}
  S_2&=&\sum_{i=0}^{N-1}\sum_{j=i+1}^{N-1}N-(j+1)\\
     &=&\sum_{i=0}^{N-1}\sum_{j'=0}^{N-(i+2)}j'\\
     &=&\sum_{i=0}^{N-2}\frac{(N-(i+2))(N-(i+1))}{2} \\
     &=&\sum_{i'=1}^{N-2}\frac{i'(i'+1)}{2}\\
     &=&\frac{1}{2}\left(\sum_{i=1}^{N-2}i^2+\sum_{i=1}^{N-2}i\right)\\
     &=&\frac{1}{2}\left(\frac{(N-2)(2N-3)(N-1)}{6}+\frac{(N-2)(N-1)}{2}\right)\\
     &=&\frac{N(N-1)(N-2)}{6}
\end{eqnarray*}


Notons  $a$  le   temps  constant  d'affectation,  $d$  le   temps  constant  de
déclaration, $x$ le temps constant d'accès  à une cellule, $s$ le temps constant
d'une somme, $c$ le temps constant d'une comparaison.


Le temps d'exécution vérifie:

$$\tau(N) \leqslant  (2d+3d+3a+a) + (d+a+x+d+s+a)N+(d+a+x+s+d+s+a)S_1+(x+s+c+s)S_2$$

Or $S_1\sim N^2$ et $S_2\sim N^3$ quand $N$ est \og grand\fg{}.


Finalement... $$\tau(N)=O(N^3)$$

...et ce, que l'on utilise C, Python, BrainFuck
(\href{https://fr.wikipedia.org/wiki/Brainfuck}{https://fr.wikipedia.org/wiki/Brainfuck}),
etc. 


C'est aussi ce que l'on a observé expérimentalement 


\textbf{Moralité}: on ne s'occupe que de ce qu'il  y a dans la boucle la plus profonde et
on oublie le reste....




\section{Plus fort que la dichotomie: l'algorithme de Héron}



Le mathématicien \textsc{Héron} d'Alexandrie n'avait pas attendu \textsc{Newton} et le
calcul différentiel  pour trouver  une méthode permettant  de déterminer
une approximation de la racine carrée d'un nombre entier positif puisqu'il a
vécu seize siècles avant Sir Isaac.


Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
 et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.

On  peut  montrer c'est  une  approximation  par  excès (en  développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).


En voici deux versions, une récursive et une itérative.  

%\begin{multicols}{2}
\begin{pythoncode}
def heron_rec(a,fo,n):
       if n == 0:
              return fo
       return heron_rec(a,(fo + a / fo) / 2, n - 1)

def heron_it(a,fo,n):
       app = fo
       for k in range(n):
              app = (app + a / app) / 2
       return app
\end{pythoncode}

Ce qui donne par exemple:

\begin{pythoncode}
In [12]: heron_rec(2,1,6)
Out[12]: 1.414213562373095

In [13]: heron_it(2,1,6)
Out[13]: 1.414213562373095

In [14]: from math import sqrt

In [15]: sqrt(2)
Out[15]: 1.4142135623730951

\end{pythoncode}




\paragraph{Est-ce que la suite des valeurs calculées par la boucle converge vers $\sqrt{2}$?}


Nous  aurons besoin  de  deux théorèmes  que  nous admettrons  et  dont nous  ne
donnerons que des versions simplifiées. 

\begin{Theoreme}[Théorème de la limite monotone]
Toute suite croissante majorée (ou décroissante minorée) converge.

\end{Theoreme}

Un théorème fondamental  est celui du point fixe. Il  faudrait plutôt parler des
théorèmes du point  fixe car il en  existe de très nombreux  avatars qui portent
les  noms   de  mathématiciens  renommés:  Banach,   Borel,  Brouwer,  Kakutani,
Kleene,…Celui  qui nous  intéresserait  le  plus en  informatique  est celui  de
Knaster-Tarski.  Ils donnent tous des conditions d'existence
de points  fixes (des solutions  de $f(x)=x$  pour une certaine  fonction). Nous
nous contenterons de la version light vue au lycée.  


\begin{Theoreme}[Un théorème light du point fixe]
  Soit I un intervalle  fermé de $\mathbb R$, soit $f$ une fonction  de Ι vers I
  et soit $(r_n)$ une suite d'éléments de I telle que $r_{n+1}=f(r_n)$ pour tout
  entier naturel  $n$. SI $(r_n)$ est  convergente ALORS sa limite  est UΝ point
  fixe de $f$ appartenant à I.  
\end{Theoreme}






Cela va nous aider à étudier notre suite définie par $r_{n+1}= f(r_n)=\frac{r_n + \frac{2}{r_n}}{2}$ et $r_0=1$. On peut alors démontrer par récurrence que

\begin{enumerate}

   \item  pour tout entier naturel non nul $n$, on a $r_n \geqslant \sqrt{2}$;
    \item la suite est décroissante;
    \item $\sqrt{2}$ est l'unique point fixe positif de $f$.
\end{enumerate}


On peut alors conclure et être assuré que notre algorithme va nous permettre d'approcher $\sqrt{2}$.




\paragraph{Quelle est la vitesse de convergence? }


 Ici, cela se traduit par \og combien de décimales obtient-t-on en plus à chaque itération?\fg{}. Introduisons la notion d'ordre d'une suite:


 \begin{Definition}[Ordre d'une suite - Constante asymptotique d'erreur]
   Soit $(r_n)$ une  suite convergeant vers $\ell$. S'il existe  un entier $k>0$
   tel               que:               $$               \displaystyle\lim_{n\to
     +\infty}\frac{|r_{n+1}-\ell|}{|r_n-\ell|^k}=C $$  avec $C\neq 0$  et $C\neq
   +\infty$ alors on dit  que $(r_n)$ est d'ordre $k$ et que  C est la constante
   asymptotique d'erreur.  
 \end{Definition}


Déterminons  l'ordre  et la  constante  asymptotique  d'erreur  de la  suite  de
Babylone donnant une approximation de $\sqrt{2}$. 
 On  démontre   que  $$
\left|r_{n+1} - \sqrt{2}\right| = \left| \frac{(r_n-\sqrt{2})^2}{2r_n}\right| $$

Ainsi   la   suite   est   d'ordre   2  et   sa   constante   asymptotique   est
$\frac{1}{2\sqrt{2}}$. Ici, on peut même avoir une idée de la vitesse sans étude
asymptotique.  

En  effet,  on  a  $r_n \geqslant  1$  donc  $$  \left|r_{n+1}  -
  \sqrt{2}\right| \leqslant \left| (r_n-\sqrt{2})^2\right| $$ 

Le nombre de  décimales d'un
nombre   positif   plus    petit   que   1   est    $-\log_{10}x$.   En   posant
$d_n=-\log_{10}|r_n-\sqrt{2}|$ on  obtient donc que $d_{n+1}  \geqslant 2d_n$: à
chaque tour de boucle, on double au minimum le nombre de bonnes décimales.


 La
précision de  la machine  étant de  16 décimales  si les  nombres sont  codés en
binaires sur 64 bits, \textbf{il faut au  maximum 6 itérations pour obtenir la précision
maximale}.  






\section*{Annexe: les relatifs et le complément à 2 puissance n}\label{exo::comp2}
    \begin{quote}
      {\itshape
Le monde se sépare en 10 catégories: ceux qui comprennent cette phrase
et les autres.
}
\begin{flushright}
  {\small Zorglub in \og Les aventures de Zorglub et Martine au Far-West\fg{}}
\end{flushright}
    \end{quote}

Nous  allons,  pour  favoriser  la  compréhension  et  simplifier  les
écritures,  travailler  sur 8  bits.  Cela  signifie que  nos  nombres
entiers peuvent être codés avec 8 chiffres égaux à 0 ou 1 en base 2.

\begin{enumerate}

\item Écrivez les nombres de 0 à 17  en base 2. Quel est le plus grand
  nombre que l'on peut écrire avec 8 bits?
  
\item  En fait,  on aimerait  avoir des  entiers signés,  c'est-à-dire
  pouvoir  représenter des  entiers  tant positifs  que négatifs  avec
  cette contrainte.

  On va donc réserver un bit (le plus à gauche) pour indiquer le signe
  du nombre: on mettra un 0 s'il est positif et un 1 s'il est négatif.

  Écrivez en compréhension l'ensemble des  nombres que l'on peut ainsi
  représenter et qui se note sur Haskell \lstinline{Int8}.

\item  Bon,  pas  de  problème...enfin  si  quand  même  un  peu.  Que
  pensez-vous de ces deux nombres:

  \begin{Verbatim}
    00000000 10000000
  \end{Verbatim}

\item On voudrait additionner facilement  ces nombres. Une idée serait
  d'utiliser l'addition  posée comme  à l'école primaire.  Par exemple
  pour calculer $ 5 + 9$

  \begin{Verbatim}
    00000101
+   00001001
------------
    00001110
  \end{Verbatim}

  On trouve bien 14.
  
  Et maintenant si on veut calculer $ 5 + (-9)$, qu'est-ce que cela donne avec ce système?

\item  Considérez maintenant  le  nombre \lstinline{m  = 11111111}  et
  ajoutez-lui 1  (vous n'avez que  8 bits  à disposition). Que  vaut $
  m+1$? Que cela vous donne-t-il comme idée?

  Considérez \lstinline{n=11111110} et calculez $ n+2$.

  Considérez \lstinline{p=11111100} et calculez $ n+4$.

  Considérez \lstinline{p=11111000} et calculez $ n+8$.

  Considérez \lstinline{p=11111010} et calculez $ n+6$.

  Des idées?

\item Si l'on considère que $  2^8$ vaut 0 en \lstinline{Int8}, ce qui
  est d'ailleurs le cas:



  \begin{haskellcode}
> let n = 256 :: Int8
> n
0
  \end{haskellcode}

Que pensez-vous alors de $x$ et de $2^8-|x|$ si $ x$ est négatif?

Comment s'écrit $2^8-|x|$ sur 8 bits?

Bon, vous commencez à voir ce qui se passe?

Alors expliquez  ce qui  se passe  ici (illustration  en Haskell  pour faciliter
l'utilisation d'enteirs 8 bits):

\begin{haskellcode}
> let n = 13 :: Int8
> n * 2
26
> n * 4
52
> n * 8
104
> n * 16
-48
> n * 32
-96
> n * 64
64
\end{haskellcode}

Généralisez, énoncez votre  norme de représentation des  entiers sur 8
bits,  énoncez un  \og truc\fg{}  pour trouver  facilement de  tête le
complément à $ 2^8$.


\end{enumerate}


  









%%% biblio et fin 
\renewcommand{\bibname}{Lectures recommand\'ees pour aller plus loin}
\nocite{*}
\bibliography{DichoMathematice}


   \end{document}

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