{
 "metadata": {
  "name": "recitation3"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# CS1001.py\n",
      "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n",
      "# Recitation 3 - 14-18.3.2013\n",
      "## Last update: 18.3.2013"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Divisors\n",
      "\n",
      "In the previous recitation we wrote a function to find the divisors of a number:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def divisors(n):\n",
      "    return [div for div in range(1,n) if n % div == 0]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here is a faster and slightly more complex way to do it:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import ceil\n",
      "def divisors2(n):\n",
      "    divs = [1]\n",
      "    for m in range(2, ceil(n ** 0.5)):#1 and n**0.5 will be handled separately. why?\n",
      "        if n % m == 0:\n",
      "            divs += [m, n // m]\n",
      "    if n % n ** 0.5 == 0:\n",
      "        divs += [int(n ** 0.5)]\n",
      "    return divs"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(divisors(36))\n",
      "print(sorted(divisors2(36)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 2, 3, 4, 6, 9, 12, 18]\n",
        "[1, 2, 3, 4, 6, 9, 12, 18]\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Timing operations\n",
      "\n",
      "Here is the simplest way to measure the time an operation takes. \n",
      "This method uses the `clock` function of the `time` module.\n",
      "It is the simplest way to do it and as such it is a crude way of doing it with very little statistical power and significance."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import time\n",
      "help(time.clock)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Help on built-in function clock in module time:\n",
        "\n",
        "clock(...)\n",
        "    clock() -> floating point number\n",
        "    \n",
        "    Return the CPU time or real time since the start of the process or since\n",
        "    the first call to clock().  This has as much precision as the system\n",
        "    records.\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(time.clock()) \n",
      "print(time.clock())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "25.99883061412379\n",
        "25.99907632401105\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This way of timing operations is often called the *tic-toc* way, we save the time before and after the operation and subtract to find the time interval.\n",
      "Run this a few times to see how crude it is."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 1234567890\n",
      "tic = time.clock()\n",
      "divisors(n)\n",
      "toc = time.clock()\n",
      "print(\"divisors: \",(toc-tic))\n",
      "tic = time.clock()\n",
      "divisors2(n)\n",
      "toc = time.clock()\n",
      "print(\"divisors2:\",(toc-tic))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "divisors:  467.4390757203012\n",
        "divisors2: 0.014307922181728827\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## The binary system and base conversions\n",
      "\n",
      "A binary number is a number in the base 2, which means that it only uses 2 digits - 0 and 1.\n",
      "The \"regular\" numbers we use, the decimal numbers, are in base 10, which means they use 10 digits - 0,1,2,3,4,5,6,7,8,9.\n",
      "\n",
      "What is a base? To understand base X imagine you have X fingers instead of 10. **How would you count with X fingers?**\n",
      "\n",
      "### Converting binary to decimal\n",
      "\n",
      "Looking at a binary number, 10011010, the **Least Significant Digit** (or **bit** for binary digits), in this case 0, is  the right most digit, and if it is 1 then it is worth $2^0=1$, otherwise it is worth 0. The next bit (in this case 1) is worth $2^1=2$. The next one is worth $2^2=4$, and the *k*-th digit/bit from the right (starting with *k=0*) is worth $2^k$. In general, denoting the binary number $x_{base 2} = a_n a_{n-} ... a_1 a_0$, it's decimal value can be evaluated by\n",
      "$$\n",
      "x_{base 10} = \\sum_{n \\ge k \\ge 0} a_k 2^k\n",
      "$$.\n",
      "Let's write python code for this:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x_bin = \"11110\"\n",
      "x_bin = x_bin[::-1] # reverse it so that LSB is on the left for the iteration\n",
      "x_dec = 0\n",
      "for k in range(len(x_bin)):\n",
      "    bit = int(x_bin[k])\n",
      "    print(k,bit)\n",
      "    x_dec += bit * 2**k\n",
      "print(x_dec)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0 0\n",
        "1 1\n",
        "2 1\n",
        "3 1\n",
        "4 1\n",
        "30\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Converting decimal to binary"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Converting from decimal to binary is done by integer division. Remember that taking the modulo 10 of a number gives the LSD in base 10, and diving by 10 removes the LSD. This is the basic idea:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x_dec = 42\n",
      "x_bin = ''\n",
      "while x_dec > 0:\n",
      "    bit = x_dec % 2\n",
      "    x_bin = str(bit) + x_bin\n",
      "    x_dec = x_dec // 2\n",
      "print(x_bin)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "101010\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Builtin functions\n",
      "\n",
      "There are some python functions to do these operations:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bin(42)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "'0b101010'"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "int('101010',2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "42"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You can also use base 16 - hexadecimal numbers:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "hex(42)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "'0x2a'"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "int('2a',16)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "42"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### General conversion\n",
      "\n",
      "We want to convert from base 10 to base b $(2 \\le b < 10)\\;$ :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def convert_base(n,b):\n",
      "    '''convert_base(integer, integer) -> string\n",
      "    Return the textual representation of n (decimal) in base 2 <= b <= 10.\n",
      "    '''\n",
      "    result = ''\n",
      "    while n > 0:\n",
      "        digit = n % b\n",
      "        n = n // b\n",
      "        print(digit)\n",
      "        result = str(digit) + result\n",
      "    return result"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(23,12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "1+12+12**2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(10,16)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "and now to base b for $10 < b \\le 36\\;$ :"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def convert_base(n,b):\n",
      "    '''convert_base(integer, integer) -> string\n",
      "    Return the textual representation of n (decimal) in base 2 <= b <= 10.\n",
      "    '''\n",
      "    assert 2 <= b <= 36\n",
      "    \n",
      "    if n == 0:\n",
      "        result = '0'\n",
      "    elif n < 0:\n",
      "        result = '-'\n",
      "    else:\n",
      "        result = ''\n",
      "    n = abs(n)\n",
      "    while n > 0:\n",
      "        digit = n % b\n",
      "        n = n // b\n",
      "        # str(digit) only works for b <= 10\n",
      "        result = '0123456789abcdefghijklmnopqrstuvwxyz'[digit] + result \n",
      "    return result"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(23,12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(10,6)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(10,16)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(40,32)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(0,5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "convert_base(100,55)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Python's memory model"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=x+%3D+%5B1,+2,+3%5D%0Ay+%3D+%5B4,+5,+6%5D%0Az+%3D+y%0Ay+%3D+x%0Ax+%3D+z%0A%0Ax+%3D+%5B1,+2,+3%5D+%23+a+different+%5B1,+2,+3%5D+list!%0Ay+%3D+x%0Ax.append(4)%0Ay.append(5)%0Az+%3D+%5B1,+2,+3,+4,+5%5D+%23+a+different+list!%0Ax.append(6)%0Ay.append(7)%0Ay+%3D+%22hello%22%0A%0A%0Adef+foo(lst)%3A%0A++++lst.append(%22hello%22)%0A++++bar(lst)%0A%0Adef+bar(myLst)%3A%0A++++print(myLst)%0A%0Afoo(x)%0Afoo(z)&cumulative=true&heapPrimitives=false&drawParentPointers=false&textReferences=false&py=3&curInstr=0\"> </iframe>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "See more examples at the [Python Tutor website](http://www.pythontutor.com/visualize.html)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Fin\n",
      "This notebook is part of the [Extended introduction to computer science](http://tau-cs1001-py.wikidot.com/) course at Tel-Aviv University.\n",
      "\n",
      "The notebook was written using Python 3.2 and IPython 0.13.1.\n",
      "\n",
      "The code is available at <https://raw.github.com/yoavram/CS1001.py/master/recitation3.ipynb>.\n",
      "\n",
      "The notebook can be viewed online at <http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation3.ipynb>.\n",
      "\n",
      "The notebooks is also available as a PDF at <https://github.com/yoavram/CS1001.py/blob/master/recitation3.pdf?raw=true>.\n",
      "\n",
      "This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}