{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c5d6cb63",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 6 -- avancé\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Nombres réels\n",
    "* Notion de précision\n",
    "* Affichage graphique\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "```{warning} \n",
    "Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d'exercices \"classiques\".\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 5. Approximation rationnelle de $\\sqrt{2}$\n",
    "\n",
    "\n",
    "Une approximation rationnelle d'un nombre réel $x$ est une suite $(p_n/q_n)$ de nombres **rationnels** qui tend vers $x$.\n",
    "\n",
    "\n",
    "### Méthode de Théon de Smyrne\n",
    "\n",
    "Théon de Smyrne (I$^{er}$ et II$^{ème}$ siècle après JC) a défini deux suites entières $(p_n)_{n \\in \\mathbb{N}}$ et $(q_n)_{n \\in \\mathbb{N}}$ qui permettent de calculer une approximation rationnelle $\\frac{p_n}{q_n}$ de $\\sqrt{2}$.\n",
    "\n",
    "Les suites sont définies de la sorte. Les termes initiaux sont $p_0 = q_0 = 1$, et la relation de récurrence est :\n",
    "\n",
    "$$\n",
    "    p_{n+1} = p_n + 2q_n \\quad \\text{ et } \\quad q_{n+1} = p_n + q_n, \\quad \\forall n \\ge 0\\,.\n",
    "$$\n",
    "\n",
    "On note enfin $t_n := \\frac{p_n}{q_n}$. \n",
    "\n",
    "**Question 1 :** Écrire une fonction `theon(n)` qui retourne la valeur de $t_n = p_n/q_n$ à l'ordre `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1be81fb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79644958",
   "metadata": {},
   "source": [
    "On peut montrer que la suite $(t_n)_{n \\in \\mathbb{N}}$ converge vers $\\sqrt{2}$ ; plus précisément on a \n",
    "\n",
    "$$\n",
    "|t_{n+1} - \\sqrt{2}| \\le \\frac{1}{2} |t_n - \\sqrt{2}|\n",
    "$$\n",
    "\n",
    "ce qui nous assure que chaque nouveau terme de la suite $(t_n)$ donne au moins un bit de précision supplémentaire (en effet, on divise l'erreur d'approximation par au moins $2$ à chaque étape).\n",
    "\n",
    "**Question 2 :** Avec Sagemath, calculer la valeur de $\\sqrt{2}$ avec une précision de $2000$ bits. Puis, vérifier que $t_{1000}$ est une approximation de $\\sqrt{2}$ à $\\le 2^{-1000}$ près."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79e99149",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5459e3a5",
   "metadata": {},
   "source": [
    "L'équation de convergence ci-dessus nous indique également que $|t_n - \\sqrt{2}| \\le 2 |t_{n+1}-t_n|$ pour tout $n \\ge 1$. Ainsi, si on souhaite obtenir une précision d'approximation de $\\epsilon > 0$, il suffit de calculer $t_n$ jusqu'à ce que $|t_{n+1}-t_n| \\le \\epsilon/2$. \n",
    "\n",
    "**Question 3 :** Écrire une fonction `approx_theon(epsilon)` qui prend en entrée un nombre positif `epsilon`, et qui retourne, avec la méthode ci-dessus, une approximation rationnelle de $\\sqrt{2}$ à $\\epsilon$ près. Avant de retourner l'approximation, on affichera le nombre d'étapes effectuées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32bcc3a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ebb123a",
   "metadata": {},
   "source": [
    "### Méthode de Héron\n",
    "\n",
    "\n",
    "La méthode de Héron s'apparente à une méthode générale dite \"méthode de Newton\". L'idée est de chercher une solution de l'équation $x^2 - 2 = 0$, en suivant les tangentes à la courbe $y = x^2 - 2$. Pour plus de précisions (non nécessaires pour cet exercice), voir https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton\n",
    "\n",
    "Dans notre cas, on définit la suite $(u_n)_{n \\in \\mathbb{N}}$ de premier terme $u_0 = 1$, et définie par récurrence par :\n",
    "\n",
    "$$\n",
    "    u_{n+1} = \\frac{u_n}{2} + \\frac{1}{u_n}, \\quad \\forall n \\ge 0\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "**Question 4 :** Écrire une fonction `heron(n)` qui calcule la valeur de $u_n$ à l'ordre `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76b1b770",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "351a145f",
   "metadata": {},
   "source": [
    "Comme précédemment, on peut démontrer que la suite $(u_n)_{n \\in \\mathbb{N}}$ converge vers $\\sqrt{2}$. Cette fois-ci la convergence est plus rapide : à partir d'un certain rang (qui dépend du choix de $u_0$), on a \n",
    "\n",
    "$$\n",
    "|u_{n+1} - \\sqrt{2}| \\le \\frac{1}{2\\sqrt{2}} |u_n - \\sqrt{2}|^2\\,.\n",
    "$$\n",
    "\n",
    "On parle de **convergence quadratique** : le nombre de bits exacts double à chaque itération.\n",
    "\n",
    "\n",
    "Comme on a $1$ bit de correct à la première itération, il faut donc environ $\\log_2(1000) \\simeq 10$ itérations supplémentaires pour obtenir $1000$ bits corrects.\n",
    "\n",
    "**Question 5 :** Vérifier que `heron(11)` donne une approximation rationnelle à $2^{-1000}$ près de $\\sqrt{2}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c75c936",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab0a7c45",
   "metadata": {},
   "source": [
    "L'équation précédente assure également que, à partir d'un certain rang (petit en pratique), si $|u_{n+1}-u_n| \\le \\epsilon$, alors $|u_{n+1} - \\sqrt{2}| \\le 2\\epsilon$.\n",
    "\n",
    "\n",
    "\n",
    "**Question 6 :** Écrire une fonction `approx_heron(epsilon)` qui prend en entrée un nombre positif `epsilon`, et qui retourne, avec la méthode ci-dessus, une approximation rationnelle de $\\sqrt{2}$ à $\\epsilon$ près. Avant de retourner l'approximation, on affichera le nombre d'étapes effectuées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "18488977",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0b3d353",
   "metadata": {},
   "source": [
    "## Exercice 6. Calcul d'une décimale\n",
    "\n",
    "**Question 1 :** Un entier `n` a été déclaré. Comment obtenir son chiffre (décimal) des unités avec une simple instruction ? et pour un nombre flottant `x` ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd60d96c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd248703",
   "metadata": {},
   "source": [
    "**Question 2 :** En s'inspirant de la question précédente, écrire une fonction `decimale(k, nombre)` qui prend entrée un entier strictement positif `k` et un nombre (flottant, symbolique ou rationnel) `nombre`, et qui retourne la $k$-ème décimale de `nombre` après la virgule. Par exemple, si `nombre = 12.345`  et `k = 2`, alors la fonction doit retourner $4$. \n",
    "\n",
    "*On supposera que `nombre` a été stocké avec une précision assez importante pour y effectuer des calculs arbitraires.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90406e4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Votre réponse ici"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}