03-prime-count-debug-bench.ipynb

{
  "metadata": {
    "orig_nbformat": 4,
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3 (ipykernel)",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.10",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    }
  },
  "nbformat_minor": 4,
  "nbformat": 4,
  "cells": [
    {
      "cell_type": "markdown",
      "source": "# Lecture 3 - *is_prime()* , debugging, benchmarking and counting\n\n## `is_prime` - continued from last week\nWe can achieve faster processing times by not processing what we don't have to.\n\n* 1 should be always skipped because all numbers are divisible by 1\n* the number itself should be skipped because all numbers are divisible by itself\n* all numbers that are greater than half of the value should be skipped\n* early termination, if a number is divisible by 3, there's no need to check against following numbers, this will not be faster to find if a number prime or not instead it will be quicker to eliminate if a number is prime or not\n\nLet's use the latest function we had written in previous notebook and name it as `is_prime_v1()`",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v1(left):  \n    right_numbers = range(2, left - 1)\n    output = 0\n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n            \n    return output is 0",
      "metadata": {},
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "is_prime_v1(15485863)",
      "metadata": {},
      "execution_count": 2,
      "outputs": [
        {
          "execution_count": 2,
          "output_type": "execute_result",
          "data": {
            "text/plain": "True"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "Let's start improving the function",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v2(left):\n    left_half  = left // 2 # <-- changed, integer division\n\n    right_numbers = range(2, left_half) # <-- changed, test divisibility up to half of the numbers\n    output = 0\n    \n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n            \n    return output is 0\n",
      "metadata": {},
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "is_prime_v2(15485863)",
      "metadata": {},
      "execution_count": 4,
      "outputs": [
        {
          "execution_count": 4,
          "output_type": "execute_result",
          "data": {
            "text/plain": "True"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "Let's do one more improvement. We can skip even numbers while generating the numbers. The `range()` function accepts `step` argument as third argument.",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "list(range(3,10,2))",
      "metadata": {},
      "execution_count": 5,
      "outputs": [
        {
          "execution_count": 5,
          "output_type": "execute_result",
          "data": {
            "text/plain": "[3, 5, 7, 9]"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v3(left):\n    left_half  = left // 2\n\n    right_numbers = range(3, left_half, 2) # <-- changed, generate odd numbers only (minor problem about 2)\n    output = 0\n    \n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n            \n    return output is 0",
      "metadata": {},
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "%time is_prime_v3(15485863)",
      "metadata": {},
      "execution_count": 7,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "CPU times: user 314 ms, sys: 0 ns, total: 314 ms\nWall time: 313 ms\n"
        },
        {
          "execution_count": 7,
          "output_type": "execute_result",
          "data": {
            "text/plain": "True"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "is_prime_v3(15485863)",
      "metadata": {},
      "execution_count": 8,
      "outputs": [
        {
          "execution_count": 8,
          "output_type": "execute_result",
          "data": {
            "text/plain": "True"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v3_1(left):\n    left_half  = left // 2\n\n    right_numbers = range(3, left_half, 2) \n    output = 0\n    \n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n        \n        if output > 0:  #\n            break       # <-- changed, if output is above 0, then stop the for loop\n            \n    return output is 0",
      "metadata": {},
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "%time is_prime_v3_1(15485869)",
      "metadata": {},
      "execution_count": 10,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "CPU times: user 7 µs, sys: 1 µs, total: 8 µs\nWall time: 9.78 µs\n"
        },
        {
          "execution_count": 10,
          "output_type": "execute_result",
          "data": {
            "text/plain": "False"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v3_2(left):\n    left_half  = left // 2\n\n    right_numbers = range(3, left_half, 2) \n    output = 0\n    \n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n        \n        if output > 0:  \n            return False       # <-- changed, if output is above 0, then \n                               # return False and ignore rest of the steps in function\n    return output is 0",
      "metadata": {},
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "%time is_prime_v3_2(15485869)",
      "metadata": {},
      "execution_count": 12,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "CPU times: user 10 µs, sys: 0 ns, total: 10 µs\nWall time: 14.5 µs\n"
        },
        {
          "execution_count": 12,
          "output_type": "execute_result",
          "data": {
            "text/plain": "False"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "is_prime_v3_1(1)",
      "metadata": {},
      "execution_count": 13,
      "outputs": [
        {
          "execution_count": 13,
          "output_type": "execute_result",
          "data": {
            "text/plain": "True"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "How can you fix the minor problem about 2? Let's use similar approach as in early termination. If the number to be checked is 2, then function should return `True` and exit.",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "def is_prime_v4(left):\n    if left is 2:           # <-- changed, if number to be checked is 2 \n        return True         # then return True and ignore rest of the steps in function\n    left_half  = left // 2\n\n    right_numbers = range(3, left_half, 2) \n    output = 0\n    \n    for right in right_numbers:\n        result = left % right\n\n        if result is 0:         \n            output += 1\n        \n        if output > 0:  \n            return False       \n                               \n    return output is 0",
      "metadata": {},
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "> Adding one more `if` statement for gaining speed might be used with caution. Because, adding one more `if` into the function will slow down the function overall because now the interpreter needs to check the result of that `if` statement. For long loops that will introduce a huge penalty.",
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": "## Benchmarking\n\nWe already used `%time` magic to calculate how long a statement takes to run. If a function is running too quick, i.e nanoseconds (`ns`) scale, `%time` won't help us measure run time. Thus, there's another magic command, `%timeit`, which runs a statement 100-1000 times and then provides the average runtime, along with other info. ",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "%timeit is_prime_v1(511)",
      "metadata": {},
      "execution_count": 15,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "36.2 µs ± 684 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "%timeit is_prime_v2(511)",
      "metadata": {},
      "execution_count": 16,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "16.3 µs ± 70.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "%timeit is_prime_v3(511)",
      "metadata": {},
      "execution_count": 17,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "8.68 µs ± 43.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "%timeit is_prime_v4(511)",
      "metadata": {},
      "execution_count": 18,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "792 ns ± 13 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "## Debugging\n\nThis is an essential and inevitable part of coding. When we make syntax errors, the interpreter will tell us line number and type of error. But, apart from those mistakes, we can make logical mistakes which will not generate error message, they will generate an unexpected result. Even worse, they might fail silently without any indicator.\n\nIn those cases, we have a \"bug\" in our code and we have to debug it.  \n\nThere are couple ways to debug code. A simple approach would be adding `print()` statements into the code to check if the variable has the expected value at certain step.\n\nAnother way would be using \"variable inspector\" which will print about current status at each step of the code. For that purpose http://pythontutor.com can be used. We'll be using that site to debug a function.",
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": "## Counting\n\nWhen there's a loop, there's usually a counter. A counter is usually used to direct the flow of program. For example, \"when a certain number is reached exit the loop\" is achievable by a counter.\n\nIn many languages you'll see such lines:\n\n```\ncounter++\n```\n\nWhich is the short form of `counter = counter + 1`. Python does not support that notation and short form of increment operation is `counter += 1`\n\nLet's count how many prime numbers are found smaller than 20:",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "counter = 0\nfor i in range(2,20):\n    if is_prime_v4(i):\n        counter+=1\nprint(counter)",
      "metadata": {},
      "execution_count": 19,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "14\n"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "That's way too many than expected. Let's see what is going on. Let's see what the function says for each number up to 20.",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "for i in range(2,20):\n    print(i,is_prime_v4(i))",
      "metadata": {},
      "execution_count": 20,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "2 True\n3 True\n4 True\n5 True\n6 True\n7 True\n8 True\n9 False\n10 True\n11 True\n12 False\n13 True\n14 True\n15 False\n16 True\n17 True\n18 False\n19 True\n"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "is_prime_v1(4)",
      "metadata": {},
      "execution_count": 21,
      "outputs": [
        {
          "execution_count": 21,
          "output_type": "execute_result",
          "data": {
            "text/plain": "False"
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": "It is time for debugging. Please head over to http://pythontutor.com and debug the `is_prime_v4()` function.",
      "metadata": {}
    },
    {
      "cell_type": "markdown",
      "source": "## Exercise\n\n1. Twin primes are [defined](https://en.wikipedia.org/wiki/Twin_prime) as \"a prime number that is either 2 less or 2 more than another prime number\". Please write down a code which will return twin primes up to 1000. Please count the pairs of primes and check online if you get the correct count.",
      "metadata": {}
    }
  ]
}