agreg/Arithmetique_sur_les_posits.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,-2018-19\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2018-19-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2018-19</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=\"#Texte\" data-toc-modified-id=\"Texte-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Texte</a></div><div class=\"lev3 toc-item\"><a href=\"#Rappels-sur-les-flottants-IEEE-754\" data-toc-modified-id=\"Rappels-sur-les-flottants-IEEE-754-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Rappels sur les flottants IEEE 754</a></div><div class=\"lev4 toc-item\"><a href=\"#Arithmétique-sur-les-flottants-IEEE\" data-toc-modified-id=\"Arithmétique-sur-les-flottants-IEEE-1411\"><span class=\"toc-item-num\">1.4.1.1&nbsp;&nbsp;</span>Arithmétique sur les flottants IEEE</a></div><div class=\"lev4 toc-item\"><a href=\"#Représentation-par-tableaux-de-bits\" data-toc-modified-id=\"Représentation-par-tableaux-de-bits-1412\"><span class=\"toc-item-num\">1.4.1.2&nbsp;&nbsp;</span>Représentation par tableaux de bits</a></div><div class=\"lev4 toc-item\"><a href=\"#Codage-redondant-!\" data-toc-modified-id=\"Codage-redondant-!-1413\"><span class=\"toc-item-num\">1.4.1.3&nbsp;&nbsp;</span>Codage redondant !</a></div><div class=\"lev3 toc-item\"><a href=\"#Nombres-universels-et-posits\" data-toc-modified-id=\"Nombres-universels-et-posits-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Nombres universels et <em>posits</em></a></div><div class=\"lev3 toc-item\"><a href=\"#Morceaux-d'un-posit\" data-toc-modified-id=\"Morceaux-d'un-posit-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Morceaux d'un <em>posit</em></a></div><div class=\"lev4 toc-item\"><a href=\"#Bit-de-signe\" data-toc-modified-id=\"Bit-de-signe-1431\"><span class=\"toc-item-num\">1.4.3.1&nbsp;&nbsp;</span>Bit de signe</a></div><div class=\"lev4 toc-item\"><a href=\"#Bits-de-régime\" data-toc-modified-id=\"Bits-de-régime-1432\"><span class=\"toc-item-num\">1.4.3.2&nbsp;&nbsp;</span>Bits de régime</a></div><div class=\"lev4 toc-item\"><a href=\"#Bits-de-l'exposant\" data-toc-modified-id=\"Bits-de-l'exposant-1433\"><span class=\"toc-item-num\">1.4.3.3&nbsp;&nbsp;</span>Bits de l'exposant</a></div><div class=\"lev4 toc-item\"><a href=\"#Bits-de-la-fraction\" data-toc-modified-id=\"Bits-de-la-fraction-1434\"><span class=\"toc-item-num\">1.4.3.4&nbsp;&nbsp;</span>Bits de la fraction</a></div><div class=\"lev3 toc-item\"><a href=\"#Interprétation-des-morceaux-d'un-posit\" data-toc-modified-id=\"Interprétation-des-morceaux-d'un-posit-144\"><span class=\"toc-item-num\">1.4.4&nbsp;&nbsp;</span>Interprétation des morceaux d'un <em>posit</em></a></div><div class=\"lev3 toc-item\"><a href=\"#Valeurs-spéciales-avec-les-posits\" data-toc-modified-id=\"Valeurs-spéciales-avec-les-posits-145\"><span class=\"toc-item-num\">1.4.5&nbsp;&nbsp;</span>Valeurs spéciales avec les <em>posits</em></a></div><div class=\"lev3 toc-item\"><a href=\"#Amplitude-dynamique-et-précision\" data-toc-modified-id=\"Amplitude-dynamique-et-précision-146\"><span class=\"toc-item-num\">1.4.6&nbsp;&nbsp;</span>Amplitude dynamique et précision</a></div><div class=\"lev3 toc-item\"><a href=\"#Théorie-à-rajouter\" data-toc-modified-id=\"Théorie-à-rajouter-147\"><span class=\"toc-item-num\">1.4.7&nbsp;&nbsp;</span>Théorie à rajouter</a></div><div class=\"lev3 toc-item\"><a href=\"#Amplitude-adaptative,-flottants-IEEE-vs-posits\" data-toc-modified-id=\"Amplitude-adaptative,-flottants-IEEE-vs-posits-148\"><span class=\"toc-item-num\">1.4.8&nbsp;&nbsp;</span>Amplitude adaptative, flottants IEEE <em>vs</em> posits</a></div><div class=\"lev3 toc-item\"><a href=\"#Exemple-sur-les-nombres-stockés-sur-8-bits\" data-toc-modified-id=\"Exemple-sur-les-nombres-stockés-sur-8-bits-149\"><span class=\"toc-item-num\">1.4.9&nbsp;&nbsp;</span>Exemple sur les nombres stockés sur 8 bits</a></div><div class=\"lev3 toc-item\"><a href=\"#Arithmétique-sur-les-posits\" data-toc-modified-id=\"Arithmétique-sur-les-posits-1410\"><span class=\"toc-item-num\">1.4.10&nbsp;&nbsp;</span>Arithmétique sur les <em>posits</em></a></div><div class=\"lev2 toc-item\"><a href=\"#Solution\" data-toc-modified-id=\"Solution-15\"><span class=\"toc-item-num\">1.5&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-151\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Types et représentations</a></div><div class=\"lev3 toc-item\"><a href=\"#Fonction-demandée\" data-toc-modified-id=\"Fonction-demandée-152\"><span class=\"toc-item-num\">1.5.2&nbsp;&nbsp;</span>Fonction demandée</a></div><div class=\"lev4 toc-item\"><a href=\"#Signe-d'un-posit\" data-toc-modified-id=\"Signe-d'un-posit-1521\"><span class=\"toc-item-num\">1.5.2.1&nbsp;&nbsp;</span>Signe d'un posit</a></div><div class=\"lev4 toc-item\"><a href=\"#Régime-d'un-posit\" data-toc-modified-id=\"Régime-d'un-posit-1522\"><span class=\"toc-item-num\">1.5.2.2&nbsp;&nbsp;</span>Régime d'un posit</a></div><div class=\"lev4 toc-item\"><a href=\"#Binaire-vers-entier\" data-toc-modified-id=\"Binaire-vers-entier-1523\"><span class=\"toc-item-num\">1.5.2.3&nbsp;&nbsp;</span>Binaire vers entier</a></div><div class=\"lev4 toc-item\"><a href=\"#Exposant-d'un-posit\" data-toc-modified-id=\"Exposant-d'un-posit-1524\"><span class=\"toc-item-num\">1.5.2.4&nbsp;&nbsp;</span>Exposant d'un posit</a></div><div class=\"lev4 toc-item\"><a href=\"#Binaire-décimal-vers-flottants\" data-toc-modified-id=\"Binaire-décimal-vers-flottants-1525\"><span class=\"toc-item-num\">1.5.2.5&nbsp;&nbsp;</span>Binaire décimal vers flottants</a></div><div class=\"lev4 toc-item\"><a href=\"#Fraction-d'un-posit\" data-toc-modified-id=\"Fraction-d'un-posit-1526\"><span class=\"toc-item-num\">1.5.2.6&nbsp;&nbsp;</span>Fraction d'un posit</a></div><div class=\"lev4 toc-item\"><a href=\"#Puissance-entière\" data-toc-modified-id=\"Puissance-entière-1527\"><span class=\"toc-item-num\">1.5.2.7&nbsp;&nbsp;</span>Puissance entière</a></div><div class=\"lev4 toc-item\"><a href=\"#Est-ce-qu'un-posit-est-infini-ou-nul-?\" data-toc-modified-id=\"Est-ce-qu'un-posit-est-infini-ou-nul-?-1528\"><span class=\"toc-item-num\">1.5.2.8&nbsp;&nbsp;</span>Est-ce qu'un posit est infini ou nul ?</a></div><div class=\"lev4 toc-item\"><a href=\"#Mettre-tout-ça-ensemble\" data-toc-modified-id=\"Mettre-tout-ça-ensemble-1529\"><span class=\"toc-item-num\">1.5.2.9&nbsp;&nbsp;</span>Mettre tout ça ensemble</a></div><div class=\"lev4 toc-item\"><a href=\"#Exemples\" data-toc-modified-id=\"Exemples-15210\"><span class=\"toc-item-num\">1.5.2.10&nbsp;&nbsp;</span>Exemples</a></div><div class=\"lev4 toc-item\"><a href=\"#Avec-des-bits-de-fraction-non-nuls\" data-toc-modified-id=\"Avec-des-bits-de-fraction-non-nuls-15211\"><span class=\"toc-item-num\">1.5.2.11&nbsp;&nbsp;</span>Avec des bits de fraction non nuls</a></div><div class=\"lev2 toc-item\"><a href=\"#Complexités\" data-toc-modified-id=\"Complexités-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Complexités</a></div><div class=\"lev3 toc-item\"><a href=\"#En-espace\" data-toc-modified-id=\"En-espace-161\"><span class=\"toc-item-num\">1.6.1&nbsp;&nbsp;</span>En espace</a></div><div class=\"lev3 toc-item\"><a href=\"#En-temps\" data-toc-modified-id=\"En-temps-162\"><span class=\"toc-item-num\">1.6.2&nbsp;&nbsp;</span>En temps</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-17\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Conclusion</a></div><div class=\"lev3 toc-item\"><a href=\"#Qualités\" data-toc-modified-id=\"Qualités-171\"><span class=\"toc-item-num\">1.7.1&nbsp;&nbsp;</span>Qualités</a></div><div class=\"lev3 toc-item\"><a href=\"#Défauts\" data-toc-modified-id=\"Défauts-172\"><span class=\"toc-item-num\">1.7.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, 2018-19\n",
    "- *Date* : 15 juin 2018\n",
    "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n",
    "- *Texte*: Texte rédigé par Lilian Besson, [\"Arithmétique avec les posits\"](https://perso.crans.org/besson/agreg-2018/textes/Arithmetique_avec_les_posits.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 *faux* [texte d'annale de l'agrégation de mathématiques, option informatique](https://perso.crans.org/besson/agreg-2018/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": 2,
   "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": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ocaml -version\";;\n",
    "print_endline Sys.ocaml_version;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.04.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val print : ('a, out_channel, unit) format -> unit = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print f =\n",
    "    ignore (Printf.printf f);\n",
    "    flush_all();\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Question de programmation\n",
    "La question de programmation pour ce texte était donnée en page XXX :\n",
    "\n",
    "FIXME\n",
    "\n",
    "### Modélisation\n",
    "On est libre de choisir l'approche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Texte\n",
    "TODO: convertir en LaTeX et utiliser un modèle ressemblant au maximum à celui des \"vrais textes\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce texte explique le fonctionnement des *posits*, en détaillant d'abord la signification de leurs bits, puis en discutant leur précision et amplitude adaptative."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les *posits* sont un nouveau format (2015) pour représenter des nombres réels sur un ordinateur, proposés comme une une alternative aux nombres flottants standards (IEEE). Une présentation plus complète est donnée [sur le site `posithub.org`](https://posithub.org/about)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'avantage des *posits* est leur capacité à donner une plus grande précision ou une amplitude adaptative, en utilisant le même nombre de bits qu'un flottant standard. Par exemple, si un logiciel peut passer des flottants IEEE 64-bits à des *posits* 32-bits, elle pourra stocker deux fois plus de nombres en mémoire en même temps !\n",
    "Cela peut sembler inutile, mais ce genre d'amélioration peut profiter à des calculs embarqués sur des micro-ordinateurs (*e.g.*, capteurs sans fils, robots) la mémoire du système est souvent très limitée, mais aussi à un ordinateur classique qui manipule un grand nombre de données (*e.g.*, apprentissage machine sur des grands corpus de données)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rappels sur les flottants IEEE 754"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On rappelera que les flottants standards sont souvent appelés `float` en OCaml, en Python, en C ainsi en Java.\n",
    "Selon les architectures, les `float` sont des flottants sur 32 ou 64 bits, et généralement les `double` sont des flottants sur 64 ou 128 bits, qui suivent tous les deux la norme IEEE 754. En Python, les `float` utilisent en fait des `double` en C."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 2018.\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0.0 +. 2018.0;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On rappelera aussi que les flottants standars contiennent trois valeurs spéciales, NaN (*\"not a number\"*, pas un nombre), `infinity` ou `inf` qui représente $+\\infty$ et `neg_infinity` ou `-inf` qui représente $-\\infty$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = neg_infinity\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = neg_infinity\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nan;;\n",
    "infinity;;\n",
    "-. infinity;;\n",
    "neg_infinity;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Arithmétique sur les flottants IEEE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les règles de calcul sur les valeurs spéciales et les calculs générant des valeurs spéciales sont illustrées par les exemples suivants :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = neg_infinity\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = neg_infinity\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* Apparition de valeurs spéciales *)\n",
    "1.0  /. 0.0;;\n",
    "-1.0 /. 0.0;;\n",
    "infinity /. infinity;;\n",
    "\n",
    "(* Calcul étendu aux valeurs spéciales *)\n",
    "1.0 +. infinity;; (* absorbant ! *)\n",
    "1.0 +. nan;;      (* absorbant ! *)\n",
    "(* Pareil pour -, *, / *)\n",
    "\n",
    "(* Changements de signe *)\n",
    "neg_infinity /. 3.0;;\n",
    "neg_infinity /. (-3.0);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On notera aussi qu'avec les flottants IEEE, il y a deux zéros, un négatif et un positif :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = false\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(-. 0.0) == 0.0;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce n'est pas le cas avec les entiers, par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 == -0;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enfin, on rappelle que l'arithmétique sur les nombres réels n'est pas exacte, par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float * float = (0.600000000000000089, 0.6)\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(0.2 +. 0.4, 0.6);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = false\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0.2 +. 0.4 == 0.6;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Représentation par tableaux de bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si la valeur NaN et les infinis sont uniques, ils ont en fait de très nombreuses représentations possibles, ce qui est souvent critiqué comme une perte.\n",
    "Par exemple, des flottants IEEE sur 32 bits a environ **16 millions** de façon de représenter NaN !\n",
    "Voir [cette page là](https://fr.wikipedia.org/wiki/NaN) (plus complète [en anglais](https://en.wikipedia.org/wiki/NaN#Encoding)).\n",
    "Cette page montre des exemples d'encodage redondant pour [les flottants IEEE à 64 bits](https://en.wikipedia.org/wiki/Double-precision_floating-point_format#Double-precision_examples), et [celle ci pour les flottants à 32 bits](https://en.wikipedia.org/wiki/Single-precision_floating-point_format#Single-precision_examples)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut utiliser le module `Int32` pour obtenir un flottant à partir d'une suite de bits.\n",
    "J'utilise `\"_\"` pour séparer le bit de signe, les bits de l'exposant et la mantisse (ou significant)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 1.\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_01111111_00000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = -2.\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b1_10000000_00000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Max et min. On ne peut pas utiliser `\"0b0_11111111_11111111111111111111111\"` pour le max, parce qu'il représente un nan, et on ne peut pas utiliser `\"0b0_00000000_00000000000000000000000\"` pour le min, parce qu'il représente un zéro."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 3.4028234663852886e+38\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_11111110_11111111111111111111111\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 1.17549435082228751e-38\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_00000001_00000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les zéro ont un exposant et une mantise remplie de zéro :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 0.\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_00000000_000000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "runtime_error",
     "output_type": "error",
     "traceback": [
      "\u001b[31mException: Failure \"Int32.of_string\".\nRaised by primitive operation at file \"[16]\", line 2, characters 19-78\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m"
     ]
    }
   ],
   "source": [
    "(* normalement, donne -0. mais échoue ici *)\n",
    "Int32.float_of_bits( Int32.of_string \"0b1_00000000_000000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les infinis ont un exposant rempli de $1$ et une mantisse remplie de $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_11111111_00000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = neg_infinity\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b1_11111111_00000000000000000000000\" );;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Codage redondant !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plusieurs exemples de Not a Number :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b1_11111111_10000000000000000000001\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b1_11111111_00000000000000000000001\" );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = nan\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int32.float_of_bits( Int32.of_string \"0b0_11111111_00000010000000000000001\" );;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il y en a *des millions* comme ça, puisqu'un exposant rempli de $1$ est toujours un nan ! C'est une perte d'espace énorme !\n",
    "Exactement, il y a en $2^{24} = 16777216$ (16 millions), puisqu'on peut mettre n'importe quelle valeur sur les $23$ bits de la mantisse et le bit de signe !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nombres universels et *posits*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les \"nombres universels\" (unum) ont été proposés par John Gustafson comme une autre manière pour la representation d'un nombre réel en utilisant un nombre fini de bits, afin d'être une alternative aux nombres flottants IEEE.\n",
    "Cf. son livre intitulé *The End of Error. Posits are a hardware-friendly version of unums.*, J. Gustafson, 2015 (voir aussi [ce document de référence](https://posithub.org/docs/Posits4.pdf) et pour une introduction plus courte, voir [cette page et ce poster](http://web.stanford.edu/class/ee380/Abstracts/170201.html)).\n",
    "\n",
    "Un nombre flottant (IEEE 754) a un bit de signe, un ensemble de bits représentant l'exponent et un ensemble de bits appelés le significant (aussi désigné avec le nom \"mantisse\").\n",
    "Pour une taille donnée, la longueur des différentes parties est fixée et standardisée\n",
    "Un nombre IEEE 752 stocké sur 64-bits au ainsi, 1 bit de signe, 11 bits d'exponent bits, et 52 bits pour le significant.\n",
    "\n",
    "Un *posit* reprend cette idée, mais ajoute une quatrième catégorie de bits, appelée *régime*.\n",
    "Un *posit* est un ensemble de bits (ordonnés), qui sont les suivantes (dans cet ordre) :\n",
    "\n",
    "- bit de signe,\n",
    "- regime,\n",
    "- exposant,\n",
    "- fraction.\n",
    "\n",
    "Le significant d'un nombre IEEE 754 correspond à la \"partie fractionnelle\", *.i.e.*, `fraction`.\n",
    "Contrairement aux nombres flottants classiques, les deux parties de l'exposant et la fraction d'un *posit* n'ont pas de longueur fixée.\n",
    "Les bits du signe et du régime ont la priorité, puis les bits restants, s'il y en a, vont dans l'exposant. Enfin, s'il reste des bits après l'exposant, ils vont dans la fraction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Morceaux d'un *posit*\n",
    "\n",
    "Pour comprendre les *posits* davantage, et prouver qu'ils ont des avantages en comparaison des nombres flottants classiques, nous allons détailler leur représentation bit-à-bit.\n",
    "L'organisation bit-à-bit d'un nombre *posit* est spécifié par deux nombres, le nombre total de bits, noté $n$, et le nombre maximum de bits dédiés à l'exponent, noté $es$.\n",
    "On dit qu'un tel nombre *posit* est un nombre `posit<n, es>`.\n",
    "\n",
    "#### Bit de signe\n",
    "Comme pour les flottants IEEE, le premier bit est le bit de signe.\n",
    "S'il est $1$, le nombre est négatif, et on prend le complément à $2$ (*i.e.*, $0 \\mapsto 1, 1 \\mapsto 0$ sur les bits) de tous les bits suivants avant d'extraire les informations du reste des bits.\n",
    "\n",
    "#### Bits de régime\n",
    "Après le bit de signe suit les bits de régime, dont le nombre est variable.\n",
    "Il peut y avoir de $1$ à $n-1$ bits de régime.\n",
    "Comment savoir quand se terminent les bits de régime ? Quand une suite de bits identiques se terminent, soit après $n-1$ bits, soit parce qu'on lit un bit opposé.\n",
    "\n",
    "Si le premier bit après le bit de signe est un $0$, alors les bits de régime continuent jusqu'à trouver un bit à $1$ ou lire $n-1$ bits.\n",
    "Et inversement si le premier bit est un $1$, les bits de régime continuent jusqu'à trouver un bit à $0$.\n",
    "\n",
    "Le bit qui indique la fin d'une séquence n'est pas inclut dans les bits de régime : le régime n'est qu'une séquence constituée uniquement de $0$ ou de $1$.\n",
    "\n",
    "#### Bits de l'exposant\n",
    "Les bits du signe et du régime sont au début du nombre. S'il reste des bits à lire, les bits de l'exposant sont les suivants.\n",
    "Il peut ne pas y avoir de bits d'exposant.\n",
    "Le nombre maximum de bits d'exposant est spécifié par ce nombre `es`.\n",
    "S'il y a au moins `es` bits après le bit de signe, les bits du régime, et le bit terminant le régime, alors les `es` prochains sont pour l'exposant.\n",
    "Mais s'il y a moins de `es` bits, tous les bits restants sont dans l'exposant.\n",
    "\n",
    "#### Bits de la fraction\n",
    "S'il reste des bits après le bit de signe, les bits du régime, le bit terminant le régime, et les bits de l'exposant, ils constituent les bits de la fraction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interprétation des morceaux d'un *posit*\n",
    "\n",
    "Expliquons maintenant comment utiliser ces quatres composants pour représenter un nombre réel (ou plutôt, une approximation décimale d'un nombre réel).\n",
    "\n",
    "Si $b$ est le signe de bit, alors le signe $s$ du nombre représenté est $(-1)^b$.\n",
    "\n",
    "Soit $m$ le nombre de bits du régime. Alors posons $k = –m$ si le régime consiste en une séquence de $0$, et $k = m-1$ sinon.\n",
    "\n",
    "$$k = \\left\\{ \\begin{array}{ll} -m & \\text{ si le régime est constitué de } m \\text{ 0's} \\\\ m-1 & \\text{ si le régime est constitué de } m \\text{ 1's} \\end{array} \\right.$$\n",
    "\n",
    "La \"graîne universelle\" (*useed*) $u$ du *posit* est déterminée par `es`, la taille maximum de l'exposant :\n",
    "\n",
    "$$u = 2^{2^{es}}.$$\n",
    "\n",
    "L'exposant $e$ est ensuite simplement un entier non signé obtenu en interprétant les bits de l'exposant, avec le bit de poids faible *en dernier* (comme un nombre binaire classique) − ce qu'on désigne souvent par \"little endian\", la petite fin.\n",
    "\n",
    "La fraction $f$ est $1 +$ les bits de fraction interprétés comme s'ils suivent une virgule en binaire. Par exemple, si les bits de fraction sont $10011$, alors $f = 1.10011$ en binaire. Sur cet exemple, la partie après la virgule est interprétée comme suit : $0.10011_2 = 1 * 2^{-1} + 0 * 2^{-2} + 0 * 2^{-3} + 1 * 2^{-4} + 1 * 2^{-5} = 0.59375_{10} = 10011_2 / 2^6 = 19/32$ ([référence](https://en.wikipedia.org/wiki/Radix_point)).\n",
    "\n",
    "Pour résumer, la valeur du nombre *posit* est le produit des contributions du bit de signe, des bits de régume, des bits de l'exposant (s'il y en a), et des bits de la fraction (s'il y en a) :\n",
    "\n",
    "$$x = s \\,\\times\\, u^k \\,\\times\\, 2^e \\,\\times\\, f = (-1)^b \\, f\\, 2^{e + k2^{es}}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Valeurs spéciales avec les *posits*\n",
    "\n",
    "Il y a deux *posits* spéciaux, avec $n-1$ bits à $0$ après le bit de signe.\n",
    "Une séquence de $n$ bits à $0$ représente le nombre zéro, et un bit à $1$ suivi de $n-1$ bits à $0$ représente $\\pm\\infty$.\n",
    "\n",
    "Il n'y a qu'un seul zéro pour les nombres posits, alors que les flottants IEEE contiennent deux zéro, un positif et un négatif.\n",
    "\n",
    "Il n'y a aussi qu'un nombre infini.\n",
    "Pour cette raison, on peut dire que les posits représentent les nombres réels projectifs plutôt que les nombres réels étendus.\n",
    "\n",
    "Les flottants IEEE ont deux types d'infinis, positif et negatif, ainsi que des \"non-nombres\" (*Not a Number*).\n",
    "Les posits n'ont qu'un seul élément qui ne correspondent pas à un nombre réel fini, et il s'agit de $\\pm\\infty$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Question : quelle utilité peut avoir un zéro négatif ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Amplitude dynamique et précision\n",
    "\n",
    "L'amplitude dynamique et la précision d'un *posit* dépendent de la valeur de `es`.\n",
    "Pour une plus grande valeur de `es`, la contribution du régime et de l'exposant augmentent, et donc des nombres ayant une grande valeur peuvent être représentés. \n",
    "Augmenter `es` augmente l'amplitude des *posits* `posit<n,es>`.\n",
    "\n",
    "L'amplitude dynamique, mesurée en décades, est calculée par le logarithme en base $10$ du rapport entre la plus grande et la plus petite valeur représentable par les *posits* `posit<n,es>`.\n",
    "\n",
    "Mais augmenter la `es` implique aussi de diminuer le nombre de bits disponibles pour la fraction, ce qui diminue la précision.\n",
    "L'un des avantages des *posits* est cette possibilité de choisir `es` pour ajuster le compromis entre amplitude dynamique et précision pour satisfaire au mieux les besoins d'une application.\n",
    "\n",
    "- Question : cela n'est pas le cas pour les flottants IEEE ?\n",
    "\n",
    "Pour des *posits* `posit<n,es>`, la plus grande valeur finie représentable est notée $\\mathrm{maxpos}$. Cette valeur est obtenue quand $k$ est aussi grand que possible as, *i.e.*, quand tous les bits après le bit de signe sont des $1$.\n",
    "Dans ce cas, $k=n-2$, donc $\\mathrm{maxpos}$ vaut\n",
    "\n",
    "$$u^{n-2} = \\left( 2^{2^{es} } \\right)^{n-2}.$$\n",
    "\n",
    "Symétriquement, la plus petite valeur positive représentable, notée $\\mathrm{minpos}$, est obtenue lors que $k$ est négatif et le plus petit possible, *i.e.*, quand le plus grand nombre possible de bits après le bit de signe sont à $0$.\n",
    "Il ne peut pas n'y avoir que des $0$ sinon on obtient la représentaion de $0$, donc il faut un unique bit à $1$ à la fin. Dans ce cas, on obtient $m = n-2$ et $k = 2-n$.\n",
    "\n",
    "$$\\mathrm{minpos} = u^{2-n} = \\left( 2^{2^{es} } \\right)^{2-n} = 1/\\mathrm{maxpos}$$\n",
    "\n",
    "L'amplitude dynamique est\n",
    "\n",
    "$$\\log_{10}\\left( 2^{2^{e} } \\right)^{2n-4} = (2n-4) \\times 2^{es}\\times \\log_{10}2.$$\n",
    "\n",
    "Par exemple, des *posits* sur $16$ bits avec `es`$=1$ ont une amplitude dynamique de $17$ décades, alors que des flottants IEEE sur $16$ bits ont une amplitude de $12$ décades.\n",
    "\n",
    "Les *posits*, dans cet exemple, ont une fraction de $12$ bits pour les nombres proche de $1$ et les flottants ont un significant (ou mantisse) de $10$ bits. Donc un nombre `posit<16,1>` a à la fois une plus grand amplitude dynamique et une meilleure précision (près de $1$) que les flottants sur $16$ bits.\n",
    "\n",
    "[FIXME use next post.]\n",
    "\n",
    "Notez que la précision d'un *posit* dépend de sa valeur. On dit qu'ils ont une précision *adaptative*.\n",
    "Les nombres proches de $1$ ont une plus grande précision, alors que les nombres très grands et très petits ont un plus faible précision.\n",
    "Et c'est précisément ce que l'on cherche en pratique.\n",
    "Dans la plupart des calculs, les valeurs des nombres sont souvent de l'ordre de $1$ (et pas $10^{-15}$ par exemple), et pour les très grandes et très petites valeurs, on veut surtout qu'il n'y a pas d'erreur de dépassement supérieur (une très grande valeur devient négative), ou inférieur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Théorie à rajouter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FIXME"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Amplitude adaptative, flottants IEEE *vs* posits\n",
    "\n",
    "Il n'y pas grand chose à dire, les posits gagnent carrément !\n",
    "\n",
    "Il faut que j'ajoute de la théorie !\n",
    "\n",
    "> [Inspiré par ce post de blog](https://www.johndcook.com/blog/2018/04/14/ieee-vs-posit/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![comparaison_floats_vs_posits_under_stereographic_projection.png 50%](images/comparaison_floats_vs_posits_under_stereographic_projection.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemple sur les nombres stockés sur 8 bits\n",
    "> [Inspiré par ce post de blog](https://www.johndcook.com/blog/2018/04/15/eight-bit-floating-point/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![images/eight_bit_ieee2.png](images/eight_bit_ieee2.png)\n",
    "![images/eight_bit_ieee2.png](images/eight_bit_posit2.png)\n",
    "https://www.johndcook.com/eight_bit_posit2.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FIXME"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Arithmétique sur les *posits*\n",
    "\n",
    "TODO à rédiger.\n",
    "Ce code peut aider : https://github.com/mightymercado/PySigmoid/blob/master/PySigmoid/Posit.py\n",
    "\n",
    "Dans cette partie, nous considérons les calculs directement implémentés sur les *posits*.\n",
    "\n",
    "Une première approche consiste à transformer les *posits* en nombres flottants, et utiliser les opérations classiques sur les *posits*, puis à convertir le résultat flottant en un *posit*.\n",
    "\n",
    "- Question : à `n` et `es` fixés, peut-on convertir un flottant en un *posit* ? De façon unique ? Décrivez l'algorithme.\n",
    "- Question : cela peut-il fonctionner ? Peut-on espérer garder les avantages décrits plus hauts si on se limite à cette approche naïve ?\n",
    "\n",
    "Proposer des algorithmes qui permettent de calculer les opérations suivantes, pour des *posits* $x$ et $y$ qui partagent le même format `posit<n,es>` :\n",
    "\n",
    "- $x \\mapsto -x$\n",
    "- $x, y \\mapsto x + y$\n",
    "- $x, y \\mapsto x - y$\n",
    "- $x, y \\mapsto x * y$\n",
    "- $x \\mapsto 1/x$\n",
    "- $x, y \\mapsto x / y$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Solution\n",
    "\n",
    "On va essayer d'être rapide et de faire simple.\n",
    "\n",
    "> Si vous êtes curieux ou que vous cherchez à utiliser les *posits* pour votre propre application, [cette page](https://posithub.org/khub_community) liste des implémentationes des *posits* et de leur arithmétique en différents langages (Javascript, Julia, Rust, C++, Python etc)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Types et représentations\n",
    "\n",
    "On va représenter un *posit* comme un tableau de `bool` en OCaml, pour se rapprocher le plus possible de l'implémentation bas-niveau qui utilisera une séquence de bits.\n",
    "\n",
    "Notez qu'on a **besoin** d'aussi stocker `es` et `n`, si on veut que notre implémentation soit générique et facile à écrire.\n",
    "Sinon on pourrait écrire chaque fonction suivante de telle sorte qu'elle accepte `es` et `n` en arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type bits = bool array\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type bits = bool array;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type posit = { es : int; n : int; b : bits; }\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type posit = {\n",
    "    es : int; (* prend de la place en plus ! *)\n",
    "    n  : int; (* mais simplifie l'écriture des fonctions *)\n",
    "    b  : bits;\n",
    "};;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Est-ce que ça coûte très cher de stocker aussi `n` et `es` ?\n",
    "> A priori non, parce que pour un *posit* de 32 bits, `b` occupe 32 bits et `n` et `es` sont majorés par $\\log_2(32) = 5$ donc occupe $2 \\times 5 = 10$ bits au maximum à eux deux. C'est un sur-coût raisonnable pour notre approche.\n",
    ">\n",
    "> En pratique, on l'a dit, on choisirait `n` et `es` *une bonne fois pour toute* pour une certaine application."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fonction demandée\n",
    "\n",
    "On vous demandait de convertir un *posit* en un nombre flottant.\n",
    "On va appliquer à la lettre la spécification donnée dans le texte.\n",
    "\n",
    "On découpe tout le traitement en sous fonctions, autant que possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Signe d'un posit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val signe_of_posit : posit -> int = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let signe_of_posit (p : posit) : int =\n",
    "    if p.b.(0) then -1 else 1\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val echange_bits : bits -> int -> bits = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let echange_bits (b : bits) (debut : int) : bits =\n",
    "    let b2 = Array.copy b in\n",
    "    for i = debut to (Array.length b) - 1 do\n",
    "        b2.(i) <- not b.(i)\n",
    "    done;\n",
    "    b2\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val echange_bits_apres_le_premier : posit -> posit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let echange_bits_apres_le_premier (p : posit) : posit =\n",
    "    if p.b.(0) then\n",
    "        { p with b = echange_bits p.b 1 }\n",
    "    else\n",
    "        { p with b = Array.copy p.b }\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Régime d'un posit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val regime_of_posit : posit -> int = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let regime_of_posit (p : posit) : int =\n",
    "    let premier_bit_regime = p.b.(1) in\n",
    "    let encore_les_memes_bits = ref true in\n",
    "    let m = ref 1 in\n",
    "    while !encore_les_memes_bits && !m <= p.n - 1\n",
    "    do\n",
    "        if p.b.(!m + 1) <> premier_bit_regime then\n",
    "            encore_les_memes_bits := false\n",
    "        else\n",
    "            incr m\n",
    "    done;\n",
    "    if premier_bit_regime then\n",
    "        (!m - 1)  (* m bits à 1 *)\n",
    "    else\n",
    "        (- !m)    (* m bits à 0 *)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Binaire vers entier\n",
    "On a d'abord besoin de savoir interpréter une séquence binaire comme un nombre entier non signé. On utilise la méthode de Hörner qui est optimale (en terme de nombre d'opérations arithmétiques) pour ce problème :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val uint_of_bits : bits -> int = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let uint_of_bits (b : bits) : int =\n",
    "    let taille = Array.length b in\n",
    "    let i = ref 0 in\n",
    "    for k = 0 to taille-1 do\n",
    "        if b.(k) then\n",
    "            i := !i * 2 + 1\n",
    "        else\n",
    "            i := !i * 2\n",
    "    done;\n",
    "    !i\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> On peut aussi écrire ça avec un simple `Array.fold_left`, mais cette fonction n'est pas disponible dans les versions plus anciennes de OCaml."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a besoin de quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val t : bool = true\n",
       "val f : bool = false\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let t = true and f = false;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uint_of_bits [|f; f; f|];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le bit de poids faible est bien à la fin :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uint_of_bits [|t; f; f|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 6\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uint_of_bits [|t; t; f|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 1\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uint_of_bits [|f; f; t|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 7\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uint_of_bits [|t; t; t|];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exposant d'un posit\n",
    "\n",
    "Pour éviter de la recalculer, on renvoit aussi la taille de l'exposant, pour faciliter le calcul des bits de fraction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val exposant_of_posit : posit -> int -> int * int = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let exposant_of_posit (p : posit) (m : int) : (int * int) =\n",
    "    let taille = Array.length p.b in\n",
    "    let taille_restante = taille - 1 - m - 1 in\n",
    "    let taille_exposant = min taille_restante p.es in\n",
    "    (* on enlève le bit de signe, le régime, et le bit de fin du régime *)\n",
    "    let exposant = uint_of_bits (Array.sub p.b (2 + m) taille_exposant) in\n",
    "    exposant, taille_exposant\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Binaire décimal vers flottants\n",
    "\n",
    "C'est assez rapide, on va écrire une fonction qui prend le tableau des bits après la virgule décimale (*e.g.*, $10011$) et donne le nombre flottant (décimal) correspondant à $0.f$ (*e.g.*, $0.10011_2 = 0.59375_{10}$). Il suffira d'ajouter $1_{10}$ pour obtenir la fraction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val float_of_bits_apres_virgule : bits -> float = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let float_of_bits_apres_virgule (b : bits) : float =\n",
    "    let taille = float_of_int (Array.length b) in\n",
    "    let nominateur = float_of_int (uint_of_bits b) in\n",
    "    let denominateur = 2.0 ** taille in\n",
    "    nominateur /. denominateur\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 0.59375\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_of_bits_apres_virgule [|t;f;f;t;t|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : float = 0.\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_of_bits_apres_virgule [||];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Fraction d'un posit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a juste à extraire les bits de la fraction, s'il en reste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val fraction_of_posit : posit -> int -> int -> float = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let fraction_of_posit (p : posit) (m : int) (taille_exposant : int) : float =\n",
    "    let debut_fraction = 1 + m + 1 + taille_exposant in\n",
    "    (* Pas sur de ce calcul *)\n",
    "    let taille_fraction = (Array.length p.b) - debut_fraction in\n",
    "    if taille_fraction > 0 then begin\n",
    "        let bits_apres_virgule = Array.sub p.b debut_fraction taille_fraction in\n",
    "        1.0 +. float_of_bits_apres_virgule (bits_apres_virgule)\n",
    "    end else (* notez que ce cas n'est pas nécessaire *)\n",
    "        1.0\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Puissance entière\n",
    "OCaml ne propose pas d'opérateur d'exponentiation entière, `**` est pour les flottants.\n",
    "C'est une bonne occasion de montrer qu'on sait écrire rapidement l'algorithme d'exponentiation rapide :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val carre : int -> int = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let carre (x : int) : int = x * x;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val expo_int : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Complexité en O(log_2 n) nombre d'appels (donc mémoire),\n",
    "    et opérations arithmétiques. *)\n",
    "let rec expo_int (x : int) (n : int) : int =\n",
    "    match n with\n",
    "    | n when n < 0 -> failwith \"expo_int avec n négatif n'est pas possible\";\n",
    "    | 0 -> 1\n",
    "    | 1 -> x\n",
    "    (* il ne faut PAS écrire\n",
    "    (expo_int x (n/2)) * (expo_int x (n/2))\n",
    "    sinon on ne gagne rien : la même fonction est appelée deux fosi *)\n",
    "    | n when n mod 2 = 0 -> carre (expo_int x (n/2))\n",
    "    | n when n mod 2 = 1 -> x * (carre (expo_int x (n/2)))\n",
    "    | _ -> failwith \"Valeur incompatible pour expo_int\"\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 2\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 8\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 16\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expo_int 2 1;;\n",
    "expo_int 2 2;;\n",
    "expo_int 2 3;;\n",
    "expo_int 2 4;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notez qu'on pourrait utiliser l'opérateur de décallage de bits vers la gauche :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "( lsl );;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 2\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 8\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 16\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 lsl 0;;\n",
    "2 lsl 1;;\n",
    "2 lsl 2;;\n",
    "2 lsl 3;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Est-ce qu'un posit est infini ou nul ?\n",
    "\n",
    "C'est très rapide à vérifier, avec cette fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : ('a -> bool) -> 'a array -> bool = <fun>\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Array.for_all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val est_nul : posit -> bool = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let est_nul (p : posit) : bool =\n",
    "    Array.for_all (not) p.b\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val est_infini : posit -> bool = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let est_infini (p : posit) : bool =\n",
    "    p.b.(0) && (Array.for_all (not) (Array.sub p.b 1 ((Array.length p.b) - 1)))\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mettre tout ça ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va commencer par écrire une fonction qui affiche un `posit<n,es>`, pour aider au débogage de la suite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val print_posit : posit -> unit = <fun>\n"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print_posit (p : posit) : unit =\n",
    "    Format.printf \"\\nposit<%i,%i> \" p.n p.es;\n",
    "    Array.iter (fun a -> Format.printf (if a then \"1\" else \"0\")) p.b;\n",
    "    flush_all();\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et enfin on assemble le tout :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val posit_to_float : ?debogue:bool -> posit -> float = <fun>\n"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Complexité linéaire dans la taille des bits de p *)\n",
    "let posit_to_float ?(debogue=false) (p : posit) : float =\n",
    "    if debogue then print_posit p;\n",
    "    (* Bit de signe *)\n",
    "    let signe = signe_of_posit p in\n",
    "    if debogue then Format.printf \"\\nSigne %i\" signe; flush_all();\n",
    "    (* On doit inverser les bits suivant si le nombre est négatif *)\n",
    "    let p2 = echange_bits_apres_le_premier p in\n",
    "    if debogue then print_posit p2;\n",
    "    (* Bits de régime *)\n",
    "    let k = regime_of_posit p2 in\n",
    "    if debogue then Format.printf \"\\nRegime %i\" k; flush_all();\n",
    "    (* Taille du régime *)\n",
    "    let m = if k < 0 then -k else k + 1 in\n",
    "    if debogue then Format.printf \"\\nTaille du regime %i\" m; flush_all();\n",
    "    (* Bits de l'exposant *)\n",
    "    let exposant, taille_exposant = exposant_of_posit p2 m in\n",
    "    if debogue then Format.printf \"\\nExposant %i\" exposant; flush_all();\n",
    "    if debogue then Format.printf \"\\nTaille de l'exposant %i\" taille_exposant; flush_all();\n",
    "    (* Bits de la fraction *)\n",
    "    let fraction = fraction_of_posit p2 m taille_exposant in\n",
    "    if debogue then Format.printf \"\\nFraction %g\" fraction; flush_all();\n",
    "    (* Gestion de l'infini *)\n",
    "    if est_infini p then infinity\n",
    "    else begin\n",
    "    if est_nul p then 0.0\n",
    "    else\n",
    "        (float_of_int signe) *.\n",
    "        (* on fait le plus possible de calcul sur les entiers *)\n",
    "        2.0 ** (float_of_int (exposant + k * (expo_int 2 p.es)))\n",
    "        *. fraction\n",
    "    end\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exemples\n",
    "\n",
    "On doit faire des essais, sur des *posits* sur 16 bits, avec par exemple `n=10` et `es=1` comme l'exemple dans le texte. :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val n : int = 10\n",
       "val es : int = 1\n"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let n = 10 and es = 1;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les valeurs spéciales sont évidemment bien correctes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p1 : posit =\n",
       "  {es = 1; n = 10;\n",
       "   b =\n",
       "    [|false; false; false; false; false; false; false; false; false; false;\n",
       "      false; false; false; false; false; false|]}\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "posit<10,1> 0000000000000000\n",
      "Signe 1\n",
      "posit<10,1> 0000000000000000\n",
      "Regime -10\n",
      "Taille du regime 10\n",
      "Exposant 0\n",
      "Taille de l'exposant 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = 0.\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p1 = { n = n; es = es; b = [|f;f;f;f;f;f;f;f;f;f;f;f;f;f;f;f|] };;\n",
    "let _ = posit_to_float ~debogue:true p1;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p2 : posit =\n",
       "  {es = 1; n = 10;\n",
       "   b =\n",
       "    [|true; false; false; false; false; false; false; false; false; false;\n",
       "      false; false; false; false; false; false|]}\n"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fraction 1\n",
      "posit<10,1> 1000000000000000\n",
      "Signe -1\n",
      "posit<10,1> 1111111111111111\n",
      "Regime 9\n",
      "Taille du regime 10\n",
      "Exposant 1\n",
      "Taille de l'exposant 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = infinity\n"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p2 = { n = n; es = es; b = [|t;f;f;f;f;f;f;f;f;f;f;f;f;f;f;f|] };;\n",
    "let _ = posit_to_float ~debogue:true p2;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Essayons d'autres valeurs :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Positif, avec un régime de $1$ et de longueur 4 (donc $m=k-1=3$), tous les autres bits à $0$, on obtient le nombre $(-1)^0 * 1.0 * 2^{0 + 3*2^1} = 64$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p3 : posit =\n",
       "  {es = 1; n = 10;\n",
       "   b =\n",
       "    [|false; true; true; true; true; false; false; false; false; false;\n",
       "      false; false; false; false; false; false|]}\n"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fraction 1.875\n",
      "posit<10,1> 0111100000000000\n",
      "Signe 1\n",
      "posit<10,1> 0111100000000000\n",
      "Regime 3\n",
      "Taille du regime 4\n",
      "Exposant 0\n",
      "Taille de l'exposant 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = 64.\n"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p3 = { n = n; es = es;\n",
    "    b = [|f; t;t;t;t; f;   f;   f;f;f;f;f;f;f;f;f|]\n",
    "    (* signe regime4t sepa expo fraction *)\n",
    "};;\n",
    "let _ = posit_to_float ~debogue:true p3;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Positif, avec un régime de $1$ et de longueur 4 (donc $m=k-1=3$), un exposant à $1$ et tous les autres bits à $0$, on obtient le nombre $(-1)^0 * 1.0 * 2^{1 + 3*2^1} = 128$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p4 : posit =\n",
       "  {es = 1; n = 10;\n",
       "   b =\n",
       "    [|false; true; true; true; true; false; true; false; false; false; false;\n",
       "      false; false; false; false; false|]}\n"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fraction 1\n",
      "posit<10,1> 0111101000000000\n",
      "Signe 1\n",
      "posit<10,1> 0111101000000000\n",
      "Regime 3\n",
      "Taille du regime 4\n",
      "Exposant 1\n",
      "Taille de l'exposant 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = 128.\n"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p4 = { n = n; es = es;\n",
    "    b = [|f; t;t;t;t; f;   t;   f;f;f;f;f;f;f;f;f|]\n",
    "    (* signe regime4t sepa expo fraction *)\n",
    "};;\n",
    "let _ = posit_to_float ~debogue:true p4;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Si on change `es` la taille maximale de l'exposant, on voit qu'on peut atteindre des nombres plus grands. Positif, avec un régime de $1$ et de longueur 4 (donc $m=k-1=3$), un exposant à $11_2 = 3$ (lu en binaire !) et tous les autres bits à $0$, on obtient le nombre $(-1)^0 * 1.0 * 2^{3 + 3*2^2} = 32768$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p5 : posit =\n",
       "  {es = 2; n = 10;\n",
       "   b =\n",
       "    [|false; true; true; true; true; false; true; true; false; false; false;\n",
       "      false; false; false; false; false|]}\n"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fraction 1\n",
      "posit<10,2> 0111101100000000\n",
      "Signe 1\n",
      "posit<10,2> 0111101100000000\n",
      "Regime 3\n",
      "Taille du regime 4\n",
      "Exposant 3\n",
      "Taille de l'exposant 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = 32768.\n"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p5 = { n = n; es = 2;\n",
    "    b = [|f; t;t;t;t; f;   t;t;   f;f;f;f;f;f;f;f|]\n",
    "    (* signe regime4t sepa expo fraction *)\n",
    "};;\n",
    "let _ = posit_to_float ~debogue:true p5;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Avec des bits de fraction non nuls\n",
    "\n",
    "Les *posits* sont très simples à interpréter tant que leurs bits de fraction sont non nuls, mais ils ne sont pas tellement plus compliqués avec une fraction.\n",
    "Voici un exemple :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img width=\"40%\" alt=\"images/exemple_calcul_valeur_posit.png\" src=\"images/exemple_calcul_valeur_posit.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p6 : posit =\n",
       "  {es = 3; n = 16;\n",
       "   b =\n",
       "    [|false; false; false; false; true; true; false; true; true; true; false;\n",
       "      true; true; true; false; true|]}\n"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fraction 1\n",
      "posit<16,3> 0000110111011101\n",
      "Signe 1\n",
      "posit<16,3> 0000110111011101\n",
      "Regime -3\n",
      "Taille du regime 3\n",
      "Exposant 5\n",
      "Taille de l'exposant 3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : float = 3.55392694473266602e-06\n"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let p6 = { n = 16; es = 3;\n",
    "    b = [|f; f;f;f;   t;   t;f;t;   t;t;f;t;t;t;f;t|]\n",
    "    (* signe regime3t sepa expo     fraction *)\n",
    "};;\n",
    "let _ = posit_to_float ~debogue:true p6;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexités"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### En espace\n",
    "Ces calculs coûtent un espace linéaire en mémoire, parce que pour éviter de modifier le posit d'entrée on créée des copies de son tableau de bits."
   ]
  },
  {
   "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.\n",
    "\n",
    "### Défauts\n",
    "- On a implémenté aucun autre développement. A suivre, j'en ajouterai quand je peux.\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": false,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "40px",
    "left": "726px",
    "right": "20px",
    "top": "86px",
    "width": "232px"
   },
   "toc_section_display": "none",
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}