{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "11da0641",
   "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": "c2880bcf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def theon(n):\n",
    "    p = 1\n",
    "    q = 1\n",
    "    for i in range(n):\n",
    "        nouveau_p = p + 2*q\n",
    "        nouveau_q = p + q\n",
    "        p = nouveau_p\n",
    "        q = nouveau_q\n",
    "    return p/q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d204afc",
   "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": "ac23fd5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = RealField(2000)(sqrt(2))\n",
    "t1000 = theon(1000)\n",
    "print(t1000)\n",
    "print(abs(s-t1000) < 2**(-1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a499b55",
   "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": "bdb4d5e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def approx_theon(epsilon):\n",
    "    p, q = 1, 1                # une manière d'assigner (p, q) à (1, 1) en une ligne\n",
    "    t = p/q\n",
    "    p, q = p + 2*q, p + q      # une manière d'assigner (p, q) à (p + 2*q, p + q) en une ligne\n",
    "    steps = 1\n",
    "    while abs(p/q - t) > epsilon/2:\n",
    "        t = p/q\n",
    "        p, q = p + 2*q, p + q\n",
    "        steps += 1\n",
    "    print(\"steps =\", steps)\n",
    "    return p/q\n",
    "    \n",
    "t = approx_theon(2**(-1000))\n",
    "print(abs(s-t) < 2**(-1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c417b7e",
   "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": "13f08cb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def heron(n):\n",
    "    u = 1\n",
    "    for i in range(n+1):\n",
    "        u = u/2 + 1/u\n",
    "    return u"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d40dc36",
   "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": "1f259e15",
   "metadata": {},
   "outputs": [],
   "source": [
    "h11 = heron(11)\n",
    "print(h11)\n",
    "print(abs(s-h11) < 2**(-1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbc5be91",
   "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": "1d79984f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def approx_heron(epsilon):\n",
    "    u = 1\n",
    "    nouveau_u = u/2 + 1/u\n",
    "    steps = 1\n",
    "    while abs(nouveau_u - u) > epsilon/2:\n",
    "        u = nouveau_u\n",
    "        nouveau_u = u/2 + 1/u\n",
    "        steps += 1\n",
    "    print(\"steps =\", steps)\n",
    "    return u\n",
    "    \n",
    "u = approx_heron(2**(-1000))\n",
    "print(abs(s-u) < 2**(-1000))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b24e76d1",
   "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` ?\n",
    "\n",
    "\n",
    "Pour un entier $n$, on calcule le reste de la division euclidienne de $n$ par $10$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "692473cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 12345\n",
    "print(n % 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "590bcd5f",
   "metadata": {},
   "source": [
    "Pour un nombre flottant $x$, on calcule sa partie entière inférieure, puis on revient au cas précédent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9798bd5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 12.345\n",
    "print( floor(x) % 10 )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "642e6e7b",
   "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": "8a6f2643",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decimale(k, nombre):\n",
    "    return floor(nombre * 10**k) % 10\n",
    "    \n",
    "print(decimale(2, 12.345))\n",
    "print(decimale(4, pi))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}