Lesson7-Performance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lesson 7 - Performance \n",
    "\n",
    "time: 30 min\n",
    "\n",
    "\n",
    "## Learning outcomes\n",
    "\n",
    "- learn basic methods of measuring performance\n",
    "- 'timeit'\n",
    "- %prun\n",
    "\n",
    "An alternative representation of the Riemann zeta function is as a product over prime numbers\n",
    "$$\n",
    "\\zeta(s) = \\sum_{n=1}^{\\infty} n^{-s} = \\prod_{p\\,\\text{prime}}\\frac{1}{1-p^{-s}}\n",
    "$$\n",
    "this is usually called an **Euler product**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def zeta_as_product(s, pmax=50):\n",
    "    return prod((1 - p**-s)**-1 for p in prime_range(pmax))\n",
    "\n",
    "def zeta_as_sum(s, nmax=50):\n",
    "    return sum(s.parent()(n)**(-s) for n in range(1, nmax))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# In theory this is of course OK but does it converge? \n",
    "zeta_as_product(2., 1000) - zeta(2.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "zeta_as_sum(2., 4800) - zeta(2.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To get a similar convergence we need many more terms in the sum compared to the product\n",
    "prime_pi(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which of these methods are more efficient? \n",
    "We can use the magic function `%timeit` or the normal function `timeit`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "timeit(\"zeta_as_sum(2., 4800)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "timeit(\"zeta_as_product(2., 1000)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to see where a function spends most time using `%prun`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%prun zeta_as_sum(2., 40800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more complete profiling, including profiling Cython code and libraries etc. it is possible to use valgrind with Sage. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**\n",
    "Compare the builtin `zeta` and the previous `euler_mac_laurin` method using `timeit` and see where the E-M function spend most time using `%prun`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prime numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It follows from the Euler product that there are infinitely many primes, since if there were not, then zeta could not have a pole at $s=1$. There are in fact deeper connections bweteen $\\zeta$ and prime numbers but we won't go into that here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are many different builtin functions for working with prime numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(primes(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(prime_range(2,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prime_pi(100)  # Count primes up to 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(prime_pi, 1, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prime_powers(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**\n",
    "Write a function which counts primes in residue classes. Input: positive integers n and m.\n",
    "Output: either \n",
    " - a list of length $n-1$ containing the numbers of primes less han equal to $m$, in different residue classes modulo $n$, or\n",
    " - a dict with keys $0,1,...,n-1$ and the counts as values.\n",
    "\n",
    "**Exercise**\n",
    "Make a plot which combines the plots of the counting functions for primes congruent to 1 and 3 modulo 4.\n",
    "\n",
    "**Additional Exercise**\n",
    "Look at n=4. Do you see any pattern? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}