quotient-and-modulo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# Efficient Computation of Quotients and Modulo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Assignment\n",
    "\n",
    "Assume that $m, n \\in \\mathbb{R}$. Than there exists $q, r \\in \\mathbb{N}$, such that $m=q\\cdot n+r \\land 0 \\leq r > n$ with $q = m // n$ and $r = m \\% n$.\n",
    "\n",
    "We want to develop a function `div_mod` such that: `div_mod(m, n) = (q, r)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Inefficient, but simple solution\n",
    "\n",
    "The listing below shows an obviously correct, but very inefficient algorithm. As long as $m$ is greater or equal to $n$, it gets decremented by $n$. If this is done, we have found the quotient, which is the number of times we decremented $m$. The modulo is the remaining value of $m$.\n",
    "\n",
    "This algorithm requires $q$ iterations to calculate the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def div_mod_simple(m, n):\n",
    "    q = 0\n",
    "\n",
    "    while m >= n:\n",
    "        q += 1\n",
    "        m -= n\n",
    "\n",
    "    return q, m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2)\n",
      "(3, 1)\n",
      "(5, 0)\n"
     ]
    }
   ],
   "source": [
    "print(div_mod_simple(5, 3))\n",
    "print(div_mod_simple(10, 3))\n",
    "print(div_mod_simple(10, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Let's see how long the calculation of $100,000,000:2$ takes ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.17 s, sys: 7.3 ms, total: 2.18 s\n",
      "Wall time: 2.18 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(50000000, 0)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "div_mod_simple(100_000_000, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Efficient solution\n",
    "\n",
    "The function `div_mod(m, n)` takes two natural numbers $m, n \\in \\mathbb{N}$ such that $n > 0$\n",
    "and returns a pair $(q, r)$ where $q$ is the quotient of dividing $m$ by $n$, while $r$ is the remainder.\n",
    "Mathematically, $q$ and $r$ are defined as those number that satisfy the following conditions:\n",
    "  - $m = q \\cdot n + r$,\n",
    "  - $0 \\leq r < n$.\n",
    "\n",
    "We define $m \\,\\texttt{/}\\texttt{/}\\, n := q$ and $m \\,\\texttt{%}\\, n := r$.  Then\n",
    "$m \\,\\texttt{/}\\texttt{/}\\, n$ is called the *quotient* of the division of $m$ by $n$\n",
    "and $m \\,\\texttt{%}\\, n$ is called the *remainder* of this division.\n",
    "\n",
    "Obviously, if $m < n$ we have that  $m \\,\\texttt{/}\\texttt{/}\\, n = 0$\n",
    "and $m \\,\\texttt{%}\\, n = m$.\n",
    "\n",
    "Otherwise, our goal is to compute $m \\,\\texttt{/}\\texttt{/}\\, n$ and\n",
    "$m \\,\\texttt{%}\\, n$ by reducing these values to\n",
    "the computation of $(m \\,\\texttt{/}\\texttt{/}\\, 2)\\,\\texttt{/}\\texttt{/}\\, n$ and\n",
    "$(m \\,\\texttt{/}\\texttt{/}\\,2) \\,\\texttt{%}\\, n$.  We have that\n",
    "$$ m \\,\\texttt{/}\\texttt{/}\\,2 = q_2 \\cdot n + r_2 \\quad\\mbox{where}\\quad 0\\leq r_2 < n. $$\n",
    "Then $q_2 = (m \\,\\texttt{/}\\texttt{/}\\,2) \\,\\texttt{/}\\texttt{/}\\, n$ and\n",
    "$r_2 = (m \\,\\texttt{/}\\texttt{/}\\,2) \\,\\texttt{%}\\, n$.\n",
    "Let us multiply this equation with 2 and add $m \\,\\texttt{%}\\, 2$ on both sides of it.  This yields:\n",
    "$$2 \\cdot (m \\,\\texttt{/}\\texttt{/}\\,2) + m \\,\\texttt{%}\\,2 = 2 \\cdot q_2 \\cdot n + 2 \\cdot r_2 + m \\,\\texttt{%}\\,2. $$\n",
    "We know that $2 \\cdot (m \\,\\texttt{/}\\texttt{/}\\,2) + m \\,\\texttt{%}\\,2 = m$ and\n",
    "therefore the last equation can be written as\n",
    "$$ m = 2 \\cdot q_2 \\cdot n + 2 \\cdot r_2 + m \\,\\texttt{%}\\,2. $$\n",
    "Now there are two cases: Either $2 \\cdot r_2 + m \\,\\texttt{%}\\,2 < n$ or\n",
    "$2 \\cdot r_2 + m \\,\\texttt{%}\\,2 \\geq  n$.\n",
    "1. Case: $2 \\cdot r_2 + m \\,\\texttt{%}\\,2 < n$:\n",
    "   Then we have that\n",
    "   $$ m \\,\\texttt{/}\\texttt{/}\\, n = 2 \\cdot q_2 \\quad \\mbox{and} \\quad\n",
    "      m \\,\\texttt{%}\\,n = 2 \\cdot r_2 + m \\,\\texttt{%}\\,2.\n",
    "   $$\n",
    "2. Case: $2 \\cdot r_2 + m \\,\\texttt{%}\\,2 \\geq n$:  In that case we have that\n",
    "   $2 \\cdot r_2 + m \\,\\texttt{%}\\,2 -n < n$ and we can rewrite the equation for $m$ as\n",
    "   $$ m = (2 \\cdot q_2 + 1) \\cdot n + 2 \\cdot r_2 + m \\,\\texttt{%}\\,2 - n. $$\n",
    "   Therefore we have\n",
    "   $$ m \\,\\texttt{/}\\texttt{/}\\, n = 2 \\cdot q_2 + 1 \\quad \\mbox{and} \\quad\n",
    "     m \\,\\texttt{%}\\,n = 2 \\cdot r_2 + m \\,\\texttt{%}\\,2 - n.\n",
    "   $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def div_mod(m, n):\n",
    "    if m < n:\n",
    "        return 0, m\n",
    "\n",
    "    q, r = div_mod(m // 2, n)\n",
    "\n",
    "    k = 2 * r + m % 2\n",
    "    if k < n:\n",
    "        return 2 * q, k\n",
    "\n",
    "    return 2 * q + 1, k - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2)\n",
      "(3, 1)\n",
      "(5, 0)\n"
     ]
    }
   ],
   "source": [
    "print(div_mod(5, 3))\n",
    "print(div_mod(10, 3))\n",
    "print(div_mod(10, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Let's see how long the calculation of $100,000,000:2$ takes ...\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 17 µs, sys: 9 µs, total: 26 µs\n",
      "Wall time: 29.1 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": "(50000000, 0)"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "div_mod(100_000_000, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.8.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}