agreg/public2018_D2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Texte-d'oral-de-modélisation---Agrégation-Option-Informatique\" data-toc-modified-id=\"Texte-d'oral-de-modélisation---Agrégation-Option-Informatique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Texte d'oral de modélisation - Agrégation Option Informatique</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2017-18\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2017-18-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2017-18</a></div><div class=\"lev2 toc-item\"><a href=\"#À-propos-de-ce-document\" data-toc-modified-id=\"À-propos-de-ce-document-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>À propos de ce document</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-de-programmation\" data-toc-modified-id=\"Question-de-programmation-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Question de programmation</a></div><div class=\"lev3 toc-item\"><a href=\"#Modélisation\" data-toc-modified-id=\"Modélisation-131\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Modélisation</a></div><div class=\"lev2 toc-item\"><a href=\"#Solution\" data-toc-modified-id=\"Solution-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Solution</a></div><div class=\"lev3 toc-item\"><a href=\"#Types-et-représentations\" data-toc-modified-id=\"Types-et-représentations-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Types et représentations</a></div><div class=\"lev3 toc-item\"><a href=\"#Algorithmes\" data-toc-modified-id=\"Algorithmes-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Algorithmes</a></div><div class=\"lev2 toc-item\"><a href=\"#Complexités\" data-toc-modified-id=\"Complexités-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Complexités</a></div><div class=\"lev3 toc-item\"><a href=\"#En-espace\" data-toc-modified-id=\"En-espace-151\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>En espace</a></div><div class=\"lev3 toc-item\"><a href=\"#En-temps\" data-toc-modified-id=\"En-temps-152\"><span class=\"toc-item-num\">1.5.2&nbsp;&nbsp;</span>En temps</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Conclusion</a></div><div class=\"lev3 toc-item\"><a href=\"#Qualités\" data-toc-modified-id=\"Qualités-161\"><span class=\"toc-item-num\">1.6.1&nbsp;&nbsp;</span>Qualités</a></div><div class=\"lev3 toc-item\"><a href=\"#Défauts\" data-toc-modified-id=\"Défauts-162\"><span class=\"toc-item-num\">1.6.2&nbsp;&nbsp;</span>Défauts</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Texte d'oral de modélisation - Agrégation Option Informatique\n",
    "## Préparation à l'agrégation - ENS de Rennes, 2017-18\n",
    "- *Date* : 6 décembre 2017\n",
    "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n",
    "- *Texte*: Annale 2018, [\"Polynômes avec des nombres flottants\" (public2018-D2)](http://agreg.org/Textes/public2018-D2.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## À propos de ce document\n",
    "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n",
    "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n",
    "- L'implémentation sera faite en OCaml, version 4+ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The OCaml toplevel, version 4.04.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.04.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ocaml -version\";;\n",
    "print_endline Sys.ocaml_version;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val print : ('a, out_channel, unit) format -> 'a = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print f =\n",
    "    let r = Printf.printf f in\n",
    "    flush_all();\n",
    "    r\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Question de programmation\n",
    "La question de programmation pour ce texte était donnée en page 6 :\n",
    "\n",
    "Cet exercice consiste à observer le comportement des nombres en virgule flottante de la\n",
    "machine.\n",
    "Toutes les variables utilisées seront de type `double` ou `float` selon le langage choisi.\n",
    "On écrit un programme qui évalue $$S = \\sum_{i=0}^{\\infty} \\left(1 - \\frac{1}{\\rho}\\right)^i$$\n",
    "où $\\rho$ est une puissance de $2$ suffisamment grande, par exemple $\\rho = 2^{20}$.\n",
    "\n",
    "Si on calcule naïvement $S_n = \\sum_{i=0}^{n} (1 - \\frac{1}{\\rho})^i$, en ajoutant les termes un par un dans l'ordre des puissances croissantes, on remarque quand $n$ est suffisamment grand, $S_{n+1} = S_n \\oplus (1 - \\frac{1}{\\rho})^{n+1}$\n",
    "lorsqu’on calcule en `double` (ou `float`).\n",
    "\n",
    "En évaluant $S$ sous la forme $$S = \\sum_{j=0}^{\\infty} \\sum_{k=0}^{K-1} \\left(1 - \\frac{1}{\\rho}\\right)^{jK + k}$$\n",
    "ce phénomène se produit pour des rangs plus grands que précedemment, l'approximation de $S$ calculée est donc meilleure. On pourra essayer plusieurs valeurs de $K$ ($1,10,100,1000,10000$) et comparer. $K = 1$ correspond au calcul naïf de $S$ ci-dessus.\n",
    "Optionnellement, le programme pourra également calculer une borne sur l’erreur com-\n",
    "mise sur $S$.\n",
    "\n",
    "### Modélisation\n",
    "On est libre de choisir l'approche, mais ici il n'y a pas tellement de choix, on va utiliser des `float` de OCaml."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Solution\n",
    "\n",
    "On va essayer d'être rapide et de faire simple."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Types et représentations\n",
    "\n",
    "Rien à faire ici, on va travailler avec des `float` de OCaml classiques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithmes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Première méthode de calcul. On remarque qu'on est déjà malin, on n'utilise aucune exponentiation mais simplement un accumulateur `terme` qui vaut $(1-1/\\rho)^j$ pour les valeurs successives de $j$, et qu'on met à jour par une simple multiplication."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val premiercalcul : float -> int -> float = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let premiercalcul (rho : float) (n : int) =\n",
    "    let somme = ref 0. in\n",
    "    let unmoinsunsurrho = 1. -. (1. /. rho) in\n",
    "    let terme = ref 1. in\n",
    "    for _ = 0 to n do  (* terme = (1-1/rho)^j pour j = _ *)\n",
    "        somme := !somme +. !terme; (* somme = sum_k=0^j terme_k *)\n",
    "        terme := !terme *. unmoinsunsurrho; (* conserve l'invariant de boucle *)\n",
    "    done;\n",
    "    !somme\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voyons un exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rho : float = 1048576.\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rho = 2. ** 20.;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 0.999999046325683594\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1. -. 1. /. rho;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette valeur est proche de $1$, mais strictement plus petite que $1$, et donc $(1-1/\\rho)^i \\to 0$ géométriquement vite, ainsi $S_n$ converge bien vers $S$ pour $n \\to \\infty$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S_10000 \t= 1.04847e+06\n",
      "S_100000 \t= 1.04847e+06\n",
      "S_0 \t= 1\n",
      "S_1 \t= 2\n",
      "S_2 \t= 3\n",
      "S_3 \t= 3.99999\n",
      "S_4 \t= 4.99999\n",
      "S_5 \t= 5.99999\n",
      "S_6 \t= 6.99998\n",
      "S_7 \t= 7.99997\n",
      "S_8 \t= 8.99997\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for n = 0 to 10 do\n",
    "    print \"\\nS_%i \\t= %g\" n (premiercalcul rho n);\n",
    "done;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S_1009 \t= 1009.51\n",
      "S_1010 \t= 1010.51\n",
      "S_1000 \t= 1000.52\n",
      "S_1001 \t= 1001.52\n",
      "S_1002 \t= 1002.52\n",
      "S_1003 \t= 1003.52\n",
      "S_1004 \t= 1004.52\n",
      "S_1005 \t= 1005.52\n",
      "S_1006 \t= 1006.52\n",
      "S_1007 \t= 1007.52\n",
      "S_1008 \t= 1008.52\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for n = 1000 to 1010 do\n",
    "    print \"\\nS_%i \\t= %g\" n (premiercalcul rho n);\n",
    "done;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deuxième méthode de calcul :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val deuxiemecalcul : float -> int -> int -> float = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let deuxiemecalcul (rho : float) (k : int) (n : int) =\n",
    "    let somme = ref 0. in\n",
    "    let unmoinsunsurrho = 1. -. (1. /. rho) in\n",
    "    let terme = ref 1. in\n",
    "    for _ = 0 to n do\n",
    "        for _ = 0 to k-1 do\n",
    "            somme := !somme +. !terme;\n",
    "            terme := !terme *. unmoinsunsurrho;\n",
    "        done;\n",
    "        terme := !terme *. unmoinsunsurrho;\n",
    "    done;\n",
    "    !somme\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voyons le même exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S_9 \t= 95379.3\n",
      "S_10 \t= 104426\n",
      "\n",
      "For K = 1 ...\n",
      "S_0 \t= 1\n",
      "S_1 \t= 2\n",
      "S_2 \t= 2.99999\n",
      "S_3 \t= 3.99999\n",
      "S_4 \t= 4.99998\n",
      "S_5 \t= 5.99997\n",
      "S_6 \t= 6.99996\n",
      "S_7 \t= 7.99995\n",
      "S_8 \t= 8.99993\n",
      "S_9 \t= 9.99991\n",
      "S_10 \t= 10.9999\n",
      "\n",
      "For K = 10 ...\n",
      "S_0 \t= 9.99996\n",
      "S_1 \t= 19.9998\n",
      "S_2 \t= 29.9996\n",
      "S_3 \t= 39.9992\n",
      "S_4 \t= 49.9987\n",
      "S_5 \t= 59.9982\n",
      "S_6 \t= 69.9975\n",
      "S_7 \t= 79.9967\n",
      "S_8 \t= 89.9958\n",
      "S_9 \t= 99.9949\n",
      "S_10 \t= 109.994\n",
      "\n",
      "For K = 100 ...\n",
      "S_0 \t= 99.9953\n",
      "S_1 \t= 199.981\n",
      "S_2 \t= 299.957\n",
      "S_3 \t= 399.923\n",
      "S_4 \t= 499.88\n",
      "S_5 \t= 599.827\n",
      "S_6 \t= 699.765\n",
      "S_7 \t= 799.693\n",
      "S_8 \t= 899.611\n",
      "S_9 \t= 999.52\n",
      "S_10 \t= 1099.42\n",
      "\n",
      "For K = 1000 ...\n",
      "S_0 \t= 999.524\n",
      "S_1 \t= 1998.09\n",
      "S_2 \t= 2995.71\n",
      "S_3 \t= 3992.38\n",
      "S_4 \t= 4988.09\n",
      "S_5 \t= 5982.86\n",
      "S_6 \t= 6976.67\n",
      "S_7 \t= 7969.54\n",
      "S_8 \t= 8961.46\n",
      "S_9 \t= 9952.43\n",
      "S_10 \t= 10942.5\n",
      "\n",
      "For K = 10000 ...\n",
      "S_0 \t= 9952.47\n",
      "S_1 \t= 19810.5\n",
      "S_2 \t= 29574.9\n",
      "S_3 \t= 39246.6\n",
      "S_4 \t= 48826.6\n",
      "S_5 \t= 58315.6\n",
      "S_6 \t= 67714.5\n",
      "S_7 \t= 77024.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S_8 \t= 86245.5\n"
     ]
    }
   ],
   "source": [
    "let valeurs_k = [|1; 10; 100; 1000; 10000|] in\n",
    "\n",
    "for i = 0 to (Array.length valeurs_k) - 1 do\n",
    "    let k = valeurs_k.(i) in\n",
    "    print \"\\n\\nFor K = %i ...\" k;\n",
    "    for n = 0 to 10 do\n",
    "        print \"\\nS_%i \\t= %g\" n (deuxiemecalcul rho k n);\n",
    "    done;\n",
    "done;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec de grandes valeurs de $n$, on semble converger vers la limite $S$, d'autant plus vite que $K$ est grand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S_10000 \t= 1.04847e+06\n",
      "S_100000 \t= 1.04847e+06\n",
      "\n",
      "For K = 1 ...\n",
      "S_100 \t= 100.99\n",
      "S_1000 \t= 1000.05\n",
      "S_10000 \t= 9906.23\n",
      "S_100000 \t= 91042.7\n",
      "\n",
      "For K = 10 ...\n",
      "S_100 \t= 1009.47\n",
      "S_1000 \t= 9957.64\n",
      "S_10000 \t= 94942.6\n",
      "S_100000 \t= 619357\n",
      "\n",
      "For K = 100 ...\n",
      "S_100 \t= 10051\n",
      "S_1000 \t= 95425.8\n",
      "S_10000 \t= 641990\n",
      "S_100000 \t= 1.03813e+06\n",
      "\n",
      "For K = 1000 ...\n",
      "S_100 \t= 96283.8\n",
      "S_1000 \t= 644662\n",
      "S_10000 \t= 1.04745e+06\n",
      "S_100000 \t= 1.04753e+06\n",
      "\n",
      "For K = 10000 ...\n",
      "S_100 \t= 648345\n",
      "S_1000 \t= 1.0484e+06\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let valeurs_n = [|100; 1000; 10000; 100000|] in\n",
    "let valeurs_k = [|1; 10; 100; 1000; 10000|] in\n",
    "\n",
    "for i = 0 to (Array.length valeurs_k) - 1 do\n",
    "    let k = valeurs_k.(i) in\n",
    "    print \"\\n\\nFor K = %i ...\" k;\n",
    "    for j = 0 to (Array.length valeurs_n) - 1 do\n",
    "        let n = valeurs_n.(j) in\n",
    "        print \"\\nS_%i \\t= %g\" n (deuxiemecalcul rho k n);\n",
    "    done;\n",
    "done;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexités"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### En espace\n",
    "Ces calculs coûtent un espace constant en mémoire.\n",
    "\n",
    "(ou $\\log n$ si on considère que stocker des entiers bornés par $n$ coûtent un espace $\\log n$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### En temps\n",
    "Ces calculs coûtent un temps linéaire en $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Conclusion\n",
    "\n",
    "Voilà pour la question obligatoire de programmation.\n",
    "\n",
    "### Qualités\n",
    "- On a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n",
    "- On a testé la fonction exigée sur de petits exemples et sur un exemple de taille réelle (venant du texte).\n",
    "\n",
    "### Défauts\n",
    "- Par contre, on est un peu pauvre en visualisation et explication,\n",
    "- Et on a implémenté aucun autre développement. A suivre, j'en ajouterai quand je peux.\n",
    "\n",
    "\n",
    "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.\n",
    "\n",
    "> Vous auriez pu choisir de modéliser le problème avec une autre approche, mais je ne vois pas ce qu'on aurait pu faire différement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> C'est tout pour aujourd'hui les amis, allez voir [ici pour d'autres corrections](https://github.com/Naereen/notebooks/tree/master/agreg), et que la force soit avec vous !"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.04.2",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.04.2"
  },
  "notify_time": "10",
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "429px",
    "width": "251px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}