ARI02-Division.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "San Vu Ngoc - [IRMAR](https://irmar.univ-rennes1.fr/)\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II. Division euclidienne\n",
    "## 1. Divisibilité"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "12%3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "12%0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "0%12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Attention, pour tous les langages informatiques, on ne peut pas calculer 0%0, **pourtant 0 est divisible par 0**, car $0 = 1\\times 0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "0%0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divise (i,j): # retourne True si i divise j\n",
    "    return (i,j) == (0,0) or j == 0 or (i !=0 and (j % i == 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divise (3,12), divise (12,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divise (0,0), divise (12,0), divise (0,12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quels sont les diviseurs de $2^{82,589,933}-1$ ?\n",
    "\n",
    "(and why we care)\n",
    "\n",
    "https://www.mersenne.org/primes/?press=M82589933"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tracé de \"i divise j\"\n",
    "\n",
    "i =ligne,  j = colonne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialisations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "# inline can be replaced by notebook to get interactive plots\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as img\n",
    "import matplotlib.cm as cm\n",
    "import matplotlib.colors as colors\n",
    "\n",
    "font = {'family': 'serif',\n",
    "        'color':  'darkred',\n",
    "        'weight': 'normal',\n",
    "        'size': 20,\n",
    "        }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=100\n",
    "T = np.zeros((n,n))\n",
    "for i in range(0, n):\n",
    "        for j in range(0, n):\n",
    "            if divise (i,j):\n",
    "                T[i,j] = 0\n",
    "            else:\n",
    "                T[i,j] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (15.0, 10.0) # set figures display bigger\n",
    "plt.imshow(T+0.15, interpolation='none', clim=(0.0, 1.), cmap=cm.hot)\n",
    "plt.xlabel('i',fontdict=font)\n",
    "plt.ylabel('j',fontdict=font)\n",
    "\n",
    "# choix de la colormap: https://matplotlib.org/users/colormaps.html\n",
    "# choix de l'interpolation: https://matplotlib.org/examples/images_contours_and_fields/interpolation_methods.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Top = T[1:20,::]\n",
    "plt.imshow(Top+0.15, interpolation='none', clim=(0.0, 1.), cmap=cm.hot)\n",
    "plt.xlabel('time (s)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II. Division euclidienne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version itérative naïve, comme la \"preuve graphique\" du cours:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def division (a,b):\n",
    "    q = 0\n",
    "    m = 0\n",
    "    while (m <= a):\n",
    "      m = m + b\n",
    "      q = q + 1\n",
    "    return (q - 1, a - m + b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "division (2023,123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "123*16 + 55"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Attention avec les nombres négatifs ça ne marche pas du tout:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "division (-2022,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice:** adapter la fonction pour admettre a négatif."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version un peu plus élégante avec l'_invariant de boucle_ $a = qb + r$\n",
    "Les invariants sont très utiles pour éviter les erreurs de programmation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def division2 (a,b):\n",
    "    q,r = 0,a\n",
    "    while r >= b:\n",
    "        r = r - b\n",
    "        q = q + 1\n",
    "    return (q,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "division2 (2023,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version récursive:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divisionR (a,b):\n",
    "    if a < b:\n",
    "        return (0, a)\n",
    "    else:\n",
    "        q,r = divisionR (a-b, b)\n",
    "        return (q+1, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divisionR (2023,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexité\n",
    "\n",
    "Dans ces 3 algorithmes, la complexité (ici, le nombre d'itérations) est a/b+1, donc au pire linéaire en a (pire cas: pour b=1). On peut faire mieux (pour les grands nombres) avec un méthode de type Newton, cf:\n",
    "https://en.wikipedia.org/wiki/Division_algorithm#Newton%E2%80%93Raphson_division\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## En pratique\n",
    "dans tous les langages de programmation, la division euclidienne est déjà implémentée. \n",
    "\n",
    "### En Python:  `(q,r) = (a//b, a%b)` (pour des nombres _positifs_)\n",
    "Attention en Python 2 on faisait `a/b` au lieu de `a//b`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "2023/123"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "2023//123"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "2023%123"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divmod(2023,123)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le résultat est correct pour les nombres $a$ négatifs. Donc **attention**: -(a%b) n'est pas égal à (-a)%b !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(-2023)%123"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "-(2023%123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "divmod(-2023,123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": "A97CF38A0357447EA2C757EFF71C8E51",
   "lastKernelId": "1c5ef800-22ef-4303-b082-26935b00af48"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}