MITx_Cython_01 Fibs

MITx_Cython_01_Fibs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "def fibr(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    elif n == 2:\n",
    "        return 2\n",
    "    else:\n",
    "        return fibr(n-1) + fibr(n-2)\n",
    "\n",
    "def fib_r_dic(n):\n",
    "    def fib_efficient(n, d):\n",
    "        if n in d:\n",
    "            return d[n]\n",
    "        else:\n",
    "            ans = fib_efficient(n-1, d) + fib_efficient(n-2, d)\n",
    "            d[n] = ans\n",
    "            return ans\n",
    "        \n",
    "    d = {1:1, 2:2}\n",
    "    return fib_efficient(n, d)\n",
    "\n",
    "def fib(n):\n",
    "    e, f = 1, 2\n",
    "    for i in range (3, n + 1):\n",
    "        e, f = f, e + f\n",
    "    return f\n",
    "\n",
    "sys.setrecursionlimit(200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fib_r outputs: 165580141\n",
      "fib_efficient outputs: 165580141\n",
      "fib iterative outputs: 165580141\n",
      "                     : 9223372036854775807\n",
      "fib recursive 35.52743101119995\n",
      "fib_efficient 16.6 µs ± 68.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n",
      "fib iterative 2.05 µs ± 18.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "now = time()\n",
    "n = 40\n",
    "\n",
    "print(f\"fib_r outputs: {fibr(n)}\")\n",
    "fib_r_time = time() - now\n",
    "print(f\"fib_efficient outputs: {fib_r_dic(n)}\")\n",
    "print(f\"fib iterative outputs: {fib(n)}\")\n",
    "print(f\"                     : {2**63 - 1}\")\n",
    "print(f\"fib recursive {fib_r_time}\")\n",
    "print(f\"fib_efficient \", end='')\n",
    "%timeit fib_r_dic(n)\n",
    "print(f\"fib iterative \", end='')\n",
    "%timeit fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2,140,361  17,331,707  8\n"
     ]
    }
   ],
   "source": [
    "# print(f\"{35.53/0.0000166:0,.0f}  {35.53/0.00000205:0,.0f}  {0.0000166/0.00000205:0,.0f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "2,140,361  17,331,707  8"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}