{ "metadata": { "name": "", "signature": "sha256:076139b5e1c7eaa3f66f89682a0f26fb880c871fcade2709e6452f1c42e3bd6f" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "code", "collapsed": false, "input": [ "def compute_convergents(sum_term, quotient_term):\n", " \"\"\"\n", " compute next term in convergents 1/(s + q)\n", " returns a tuple (num, denum)\n", " \"\"\"\n", " num, denum = quotient_term\n", " num += sum_term * denum\n", " num, denum = denum, num\n", " return (num, denum)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "code", "collapsed": false, "input": [ "compute_convergents(2, (1, 2))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "(2, 5)" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "def compute_square_root(order):\n", " \"\"\"\n", " 1 should return 3/2, \n", " 2 should return 7/5, ...\n", " \"\"\"\n", " num, denum = 1, 2\n", " for i in range(1, order):\n", " num, denum = compute_convergents(2, (num, denum))\n", " return (denum + num, denum) " ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 8 }, { "cell_type": "code", "collapsed": false, "input": [ "from IPython.html.widgets import interact" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 9 }, { "cell_type": "code", "collapsed": false, "input": [ "interact(lambda order: print(compute_square_root(order)),\n", " order=(1, 10))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "(41, 29)\n" ] } ], "prompt_number": 10 }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can plot the convergence of the rational approximations compared to the \"true value\":" ] }, { "cell_type": "code", "collapsed": false, "input": [ "%matplotlib inline" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 11 }, { "cell_type": "code", "collapsed": false, "input": [ "from pylab import plot, sqrt, hlines" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 16 }, { "cell_type": "code", "collapsed": false, "input": [ "n = range(1, 101)\n", "div = lambda t: t[0] / float(t[1])\n", "div_sqrt = lambda order: div(compute_square_root(order))\n", "plot(n, list(map(div_sqrt, n)))\n", "hlines(sqrt(2), 1, 100, linestyles='dotted')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 25, "text": [ "" ] }, { "metadata": {}, "output_type": "display_data", "png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEACAYAAAC08h1NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAEkVJREFUeJzt3X+MXWWdx/H3p9NWYVHQdIMKjUUjCRjciPJj3SVtlLDV\nIN3oGiGLEhLZaADRdV2BbNKJfxgxMZa4QFBpo0ZLstWw7coPdXXcbjZBDOhWfqkrxoJSmi2gQuJ2\n2u/+cW+dsZ25d+jM6T3Meb+Sydx7znOfPvdJ+rnfPuc5t6kqJEndsWTUA5AkHVkGvyR1jMEvSR1j\n8EtSxxj8ktQxBr8kdczA4E+yMcmuJDtmOb8mydNJ7uv//NO0c2uTPJTkp0k+ttADlyQdngzax5/k\nHOB3wJeq6rQZzq8B/r6qLjjo+BjwMHAu8BhwD3BRVT24cEOXJB2OgRV/VW0HnhzSR2Y4dibws6r6\nRVXtBW4F1h3eECVJC2m+a/wFvCnJj5LcnuTU/vETgJ3T2j3aPyZJGrGl83z9vcDKqno2yVuB24CT\n5z8sSVJT5hX8VfXbaY/vSHJjkpfSq/BXTmu6sn/sEEn8siBJOgxVNdNS+1DzWupJcnyS9B+fSe9i\n8R7gB8BrkqxKshx4N7B1tn6qiq1bi/PPL6q6+7N+/fqRj6EtP86Fc+FcDP6Zj4EVf5LNwGpgRZKd\nwHpgWT+sbwb+BvhAkkngWeDC/rnJJFcAdwFjwC01ZEfP0qUwOTmv9yJJmoOBwV9VFw05fwNwwyzn\n7gDumPNADH5JOiJac+euwQ9r1qwZ9RBaw7mY4lxMcS4WxsAbuI7IAJKqKrZvh2uvhe3bRzocSXpe\nSEKN4uLuQhobs+KXpCOhNcG/dCns2zfqUUjS4teq4Lfil6TmGfyS1DEGvyR1jMEvSR3TmuB3V48k\nHRmtCX539UjSkdGq4Lfil6TmGfyS1DEGvyR1jMEvSR3TmuB3V48kHRmtCX539UjSkdGq4Lfil6Tm\ntSb4x8Z6Ff+I/3sASVr0WhP8yVT4S5Ka05rgB5d7JOlIaFXwu7NHkprXquC34pek5rUu+F3jl6Rm\ntS74rfglqVkGvyR1jMEvSR3TquB3V48kNa9VwW/FL0nNa13wu6tHkprVuuC34pekZhn8ktQxBr8k\ndUyrgt9dPZLUvFYFvxW/JDWvdcHvrh5Jalbrgt+KX5KaNTD4k2xMsivJjiHtzkgymeSd045dk+T+\nJDuSfDXJC4YNxuCXpOYNq/g3AWsHNUgyBlwH3Dnt2CrgMuD0qjoNGAMuHDYYg1+Smjcw+KtqO/Dk\nkD6uBLYAu6cd+w2wFzg6yVLgaOCxYYMx+CWpefNa409yArAOuKl/qACqag/waeCXwK+Ap6rq28P6\nczunJDVv6TxfvwG4uqoqSYAAJHk18CFgFfA08C9J/raqvjJTJ+Pj4wA89BDs2LGGd71rzTyHJUmL\ny8TEBBMTEwvSV6pqcIPeev22/lr9wed+Tj/sgRXAs8DfAS8Azquq9/XbvQc4u6oun6GPOjCGiy+G\ntWt7vyVJs0tCVWV4y0PNa6mnql5VVSdV1Un01vk/UFX/CjwMnJ3kqP6/BM4FHhjWn2v8ktS8gUs9\nSTYDq4EVSXYC64FlAFV182yvq6ofJfkS8ANgP3Av8LmhgzH4JalxA4O/qi6aa0dVdelBzz8FfOo5\nDcbgl6TGterOXXf1SFLzWhX8VvyS1LzWBb9f0iZJzWpd8FvxS1KzDH5J6hiDX5I6plXB764eSWpe\nq4Lfil+Smte64HdXjyQ1q3XBb8UvSc0y+CWpYwx+SeqYVgW/u3okqXmtCn4rfklqXuuC3109ktSs\n1gW/Fb8kNcvgl6SOMfglqWNaFfzu6pGk5rUq+K34Jal5rQt+d/VIUrNaF/xW/JLULINfkjrG4Jek\njmlV8LurR5Ka16rgt+KXpOYZ/JLUMa0LfrdzSlKzWhf8VvyS1CyDX5I6plXB764eSWpeq4Lfil+S\nmmfwS1LHtC743dUjSc1qXfBb8UtSswYGf5KNSXYl2TGk3RlJJpO8Y9qx45JsSfJgkgeSnD1sMAa/\nJDVvWMW/CVg7qEGSMeA64E4g005dD9xeVacArwMeHDYYg1+Smjcw+KtqO/DkkD6uBLYAuw8cSHIs\ncE5Vbez3M1lVTw8bjNs5Jal581rjT3ICsA64qX+o+r9PAnYn2ZTk3iSfT3L0sP6s+CWpefO9uLsB\nuLqqit4yz4GlnqXA6cCNVXU68Axw9dDBLIEq2L9/nqOSJM1q6Txf/wbg1iQAK4C3JtkL3A08WlX3\n9NttYUDwj4+P/+HxkiVr2LdvDUtatd9IkkZrYmKCiYmJBekrvWJ9QINkFbCtqk4b0m5Tv93X+8//\nA3hfVf0kyThwVFV9bIbX1fQxHHUU7NnT+y1JmlkSqirDWx5qYMWfZDOwGliRZCewHlgGUFU3D+n7\nSuArSZYD/wNcOqcBuc4vSY0aWvE3PoCDKv7jjoNHHoGXvGSEg5KklptPxd+6lXQrfklqViuD3+/r\nkaTmtDL4rfglqTkGvyR1jMEvSR3TuuD3+3okqVmtC34rfklqlsEvSR3TyuB3O6ckNaeVwW/FL0nN\nMfglqWNaF/zu6pGkZrUu+K34JalZBr8kdUwrg99dPZLUnFYGvxW/JDXH4Jekjmld8LurR5Ka1brg\nt+KXpGYZ/JLUMa0Mfnf1SFJzWhn8VvyS1ByDX5I6pnXB764eSWpW64Lfil+SmmXwS1LHGPyS1DGt\nDH63c0pSc1oZ/Fb8ktSc1gW/u3okqVmtC34rfklqlsEvSR1j8EtSx7Qy+N3VI0nNaWXwW/FLUnMM\nfknqmIHBn2Rjkl1Jdgxpd0aSySTvOOj4WJL7kmyb64DczilJzRpW8W8C1g5qkGQMuA64E8hBp68C\nHgBqrgOy4pekZg0M/qraDjw5pI8rgS3A7ukHk5wIvA34Aod+IMzK4JekZs1rjT/JCcA64Kb+oemV\n/WeAjwL7n0uf7uqRpGbN9+LuBuDqqip6VX0AkpwPPFFV9/Ecqn2w4pekpi2d5+vfANyaBGAF8NYk\nk8BZwAVJ3ga8EHhxki9V1Xtn6mR8fPwPj5ctW8Pk5Jp5DkuSFpeJiQkmJiYWpK/0ivUBDZJVwLaq\nOm1Iu039dl8/6Phq4B+q6u2zvK6mj+Eb34AbboDbb5/T+CWpk5JQVc9pReWAgRV/ks3AamBFkp3A\nemAZQFXd/Bz+HHf1SFJLDAz+qrporh1V1aWzHP8e8L05D8jgl6RGtfLOXXf1SFJzWhn8VvyS1ByD\nX5I6pnXB73f1SFKzWhf8VvyS1CyDX5I6xuCXpI5pZfC7nVOSmtPK4Lfil6TmtC743dUjSc1qXfBb\n8UtSswx+SeoYg1+SOqaVwe+uHklqTiuD34pfkprTuuB3V48kNat1wX+g4h/yP0JKkg5T64J/yRJI\nYP/+UY9Ekhan1gU/uM4vSU1qbfC7s0eSmtHa4Lfil6RmtDL43dkjSc1pZfBb8UtScwx+SeoYg1+S\nOqa1we+uHklqRmuD34pfkpph8EtSx7Qy+N3OKUnNaWXwW/FLUnMMfknqGINfkjqmtcHvdk5JakZr\ng9+KX5Ka0crgd1ePJDWnlcFvxS9JzRka/Ek2JtmVZMeQdmckmUzyjv7zlUm+m+T+JD9O8sG5Dsrg\nl6TmzKXi3wSsHdQgyRhwHXAnkP7hvcCHq+q1wNnA5UlOmcugDH5Jas7Q4K+q7cCTQ5pdCWwBdk97\n3eNV9cP+498BDwKvmMug3NUjSc2Z9xp/khOAdcBN/UM1Q5tVwOuBu+fSpxW/JDVn6QL0sQG4uqoq\nSZha6gEgyTH0/jVwVb/yP8T4+PgfHq9Zs4axsTUGvyRNMzExwcTExIL0lapDCvRDG/Uq9m1VddoM\n537OVNivAJ4FLquqrUmWAf8G3FFVG2bpuw4ew3vfC295C1xyyXN4J5LUIUmoqgxveah5V/xV9app\nA9lE7wNia7/6vwV4YLbQn3VQLvVIUmOGBn+SzcBqYEWSncB6YBlAVd084KV/AVwM/HeS+/rHrqmq\nO4cOyuCXpMYMDf6qumiunVXVpdMe/yeHefHYXT2S1Bzv3JWkjmll8PtdPZLUnFYG/8EV/yc/CVu2\njG48krSYPC+Cf2ICPvIR+P3vRzYkSVo0nhfBv2sXLFkCn/vc6MYkSYtFa4N/+q6eXbvgs5+FT3wC\nnnlmdOOSpMWgtcF/oOLfvx9274bzzoNzzul9AEiSDt9CfFfPgpu+q2fPHnjRi2D5cvj4x3vh//73\nwzHH9Nb+77oLEjj2WHjxi2HZst6Hxb59cPC3UeSwbm6WpMWlVcF/4MvajjlmnMnJ3vMnnvhTjj/+\ncgBuvXWcE09cx3nnvZ5HHoHlyx/j5JMfZu3aN/P003Dbbd+naglnnvlGliyBe+7pfRnoWWedRRXc\nfffUc/C5z33u8+fv8/mY05e0NWmmL2nbsAEeeQSuvx6+851epX/gS+l+/Wv42tfg7W+HV77yyI9X\nktpgpF/S1oTpa/y7dsHxx0+de/nL4YorRjMuSVoMWn9x9+DglyTNT2uD/8B2ToNfkhZWK4N/+q4e\ng1+SFlYrg9+lHklqjsEvSR1j8EtSx7Q6+KvgiScMfklaSK0N/n374Kmn4IUv7P1IkhZGK4P/wK4e\nl3kkaeG1MvgPLPUY/JK08Ax+SeoYg1+SOsbgl6SOaW3w79tn8EtSE1ob/Acq/pe9bNSjkaTFpZXB\n73ZOSWpOK4PfNX5Jak5rg3/vXnj8cYNfkhZaa4N/zx5YtgyOPnrUo5GkxaXVwW+1L0kLr7XBDwa/\nJDWhlcE/Ntb7bfBL0sJrZfBb8UtScwx+SeqYgcGfZGOSXUl2DGl3RpLJJO+cdmxtkoeS/DTJx57L\noAx+SWrOsIp/E7B2UIMkY8B1wJ0HHfvn/mtPBS5KcspcB9XV4J+YmBj1EFrDuZjiXExxLhbGwOCv\nqu3Ak0P6uBLYAuyeduxM4GdV9Yuq2gvcCqyb66AMfjkXU5yLKc7FwpjXGn+SE+gF+k39Q9X/fQKw\nc1rTR/vH5sRdPZLUnPle3N0AXF1VBaT/A1MfAIclgeXLDX5JakJ6mT2gQbIK2FZVp81w7udMhf0K\n4FngMuAJYLyq1vbbXQPsr6rrZuhjXh8SktRVVZXhrQ61dJ5/6KsOPE6yid4HxNYkS4HX9D80fgW8\nG7holj4Oa+CSpMMzMPiTbAZWAyuS7ATWA8sAqurm2V5XVZNJrgDuAsaAW6rqwQUbtSTpsA1d6pEk\nLS4ju3N3Pjd4Pd8lWZnku0nuT/LjJB/sH39pkm8l+UmSbyY5btRjPVKSjCW5L8m2/vNOzkWS45Js\nSfJgkgeSnNXhubim/3dkR5KvJnlBV+ZipptnB733/lz9tJ+p5w3rfyTBP98bvBaBvcCHq+q1wNnA\n5f33fzXwrao6Gfj3/vOuuAp4gKkdYV2di+uB26vqFOB1wEN0cC761wcvA07vbywZAy6kO3Mx082z\nM773JKfSu456av81NyYZmO2jqvjndYPX811VPV5VP+w//h3wIL37HC4Avthv9kXgr0czwiMryYnA\n24AvMLVLrHNzkeRY4Jyq2gi9a2VV9TQdnAvgN/QKpKP7m0WOprdRpBNzMcvNs7O993XA5qraW1W/\nAH5GL2NnNargn9cNXotJv7J5PXA3cHxV7eqf2gV05U6GzwAfBfZPO9bFuTgJ2J1kU5J7k3w+yZ/Q\nwbmoqj3Ap4Ff0gv8p6rqW3RwLqaZ7b2/gl6GHjA0T0cV/F5RBpIcA3wNuKqqfjv9XP+muEU/T0nO\nB56oqvuYqvb/SFfmgt4uu9OBG6vqdOAZDlrK6MpcJHk18CFgFb1gOybJxdPbdGUuZjKH9z5wXkYV\n/I8BK6c9X8kff2ItekmW0Qv9L1fVbf3Du5K8rH/+5fRuhFvs3gRckOQRYDPw5iRfpptz8SjwaFXd\n03++hd4HweMdnIs3Av9VVf9bVZPA14E/p5tzccBsfycOztMT+8dmNarg/wH9G7ySLKd3YWLriMZy\nxCUJcAvwQFVtmHZqK3BJ//ElwG0Hv3axqaprq2plVZ1E7+Ldd6rqPXRzLh4HdiY5uX/oXOB+YBsd\nmwt6F7XPTnJU/+/LufQu/ndxLg6Y7e/EVuDCJMuTnAS8Bvj+wJ6qaiQ/wFuBh+ldiLhmVOMY0Xv/\nS3rr2T8E7uv/rAVeCnwb+AnwTeC4UY/1CM/LamBr/3En5wL4M+Ae4Ef0qtxjOzwX/0jvg28HvYuZ\ny7oyF/T+9fsr4P/oXQ+9dNB7B67tZ+lDwF8N698buCSpY1r5Xy9Kkppj8EtSxxj8ktQxBr8kdYzB\nL0kdY/BLUscY/JLUMQa/JHXM/wMuf7MOOxqMAwAAAABJRU5ErkJggg==\n", "text": [ "" ] } ], "prompt_number": 25 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Indeed, this thing converges nicely to the square root of 2. \n", "\n", "Let's try to get to our next step: evaluating continuous fractions with sequences other than just always the same number." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def compute_continued_fraction(order, starting_number, repeating_sequence):\n", " \"\"\"\n", " evaluate continued fraction defined \u221a2 = [1;(2)] or \u221a23 = [4;(1,3,1,8)]\n", " \"\"\"\n", " num, denum = 1, repeating_sequence[(order - 1) % (len(repeating_sequence))]\n", " for i in range(order - 1, 0, -1):\n", " lhs_factor = repeating_sequence[(i-1) % len(repeating_sequence)]\n", " num, denum = compute_convergents(lhs_factor, (num, denum))\n", " return (starting_number * denum + num, denum) " ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 122 }, { "cell_type": "code", "collapsed": false, "input": [ "pdb.runcall(compute_continued_fraction, 3, 2, (1, 4, 3))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "> (5)compute_continued_fraction()\n", "-> num, denum = 1, repeating_sequence[(order - 1) % (len(repeating_sequence))]\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (6)compute_continued_fraction()\n", "-> for i in range(order - 1, 0, -1):\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) num, denum\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "(1, 3)\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (7)compute_continued_fraction()\n", "-> lhs_factor = repeating_sequence[(i-1) % len(repeating_sequence)]\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (8)compute_continued_fraction()\n", "-> num, denum = compute_convergents(lhs_factor, (num, denum))\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) lhs_factor\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (6)compute_continued_fraction()\n", "-> for i in range(order - 1, 0, -1):\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) num, denum\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "(3, 13)\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (7)compute_continued_fraction()\n", "-> lhs_factor = repeating_sequence[(i-1) % len(repeating_sequence)]\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (8)compute_continued_fraction()\n", "-> num, denum = compute_convergents(lhs_factor, (num, denum))\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) lhs_factor\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (6)compute_continued_fraction()\n", "-> for i in range(order - 1, 0, -1):\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "> (9)compute_continued_fraction()\n", "-> return (starting_number * denum + num, denum)\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) n\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "--Return--\n", "> (9)compute_continued_fraction()->(45, 16)\n", "-> return (starting_number * denum + num, denum)\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) c\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 123, "text": [ "(45, 16)" ] } ], "prompt_number": 123 }, { "cell_type": "code", "collapsed": false, "input": [ "compute_continued_fraction(3, 2, (1, 4, 3))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 124, "text": [ "(45, 16)" ] } ], "prompt_number": 124 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see if our code works for the square root of 2." ] }, { "cell_type": "code", "collapsed": false, "input": [ "interact(lambda order: print(compute_continued_fraction(order, 1, (2,))),\n", " order=(1, 10))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "(577, 408)\n" ] } ], "prompt_number": 125 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Yes, seems to work. Let's see how this goes with the square root of 23." ] }, { "cell_type": "code", "collapsed": false, "input": [ "interact(lambda order: print(compute_continued_fraction(order, 4, (1,3,1,8))),\n", " order=(1, 10))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "(211, 44)\n" ] } ], "prompt_number": 126 }, { "cell_type": "code", "collapsed": false, "input": [ "import pdb" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 58 }, { "cell_type": "code", "collapsed": false, "input": [ "pdb.runcall(compute_continued_fraction, 1, 4, (1,3,1,8))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "> (5)compute_continued_fraction()\n", "-> repeating_sequence = repeating_sequence[::-1]\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(Pdb) q\n" ] } ], "prompt_number": 61 }, { "cell_type": "code", "collapsed": false, "input": [ "sqrt(23)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 127, "text": [ "4.7958315233127191" ] } ], "prompt_number": 127 }, { "cell_type": "code", "collapsed": false, "input": [ "19/4" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 128, "text": [ "4.75" ] } ], "prompt_number": 128 }, { "cell_type": "code", "collapsed": false, "input": [ "24/ 5" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 129, "text": [ "4.8" ] } ], "prompt_number": 129 }, { "cell_type": "code", "collapsed": false, "input": [ "211 /44 " ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 130, "text": [ "4.795454545454546" ] } ], "prompt_number": 130 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now on to the exponential:\n", " \n", " e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]\n", " \n", " The convergents are:\n", " \n", " 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536" ] }, { "cell_type": "code", "collapsed": false, "input": [ "interact(lambda order: print(compute_continued_fraction(order, 2, (1,2,1,1,4,1))),\n", " order=(1, 10))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "(492, 181)\n" ] } ], "prompt_number": 131 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Interlude: we write a function that generates the right coefficients until rank $n$." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def exponential_coefs(n):\n", " coefs = []\n", " for i in range(n):\n", " if (i % 3) == 0 or (i % 3) == 2:\n", " coefs.append(1)\n", " else:\n", " coefs.append(int((i + 2) / 3 * 2))\n", " return coefs" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 136 }, { "cell_type": "code", "collapsed": false, "input": [ "exponential_coefs(9)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 139, "text": [ "[1, 2, 1, 1, 4, 1, 1, 6, 1]" ] } ], "prompt_number": 139 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, let's compute the 10th partial of the exponential." ] }, { "cell_type": "code", "collapsed": false, "input": [ "compute_continued_fraction(9, 2, exponential_coefs(9))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 142, "text": [ "(1457, 536)" ] } ], "prompt_number": 142 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now the 100th partial:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "compute_continued_fraction(99, 2, exponential_coefs(99))" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 143, "text": [ "(6963524437876961749120273824619538346438023188214475670667,\n", " 2561737478789858711161539537921323010415623148113041714756)" ] } ], "prompt_number": 143 }, { "cell_type": "markdown", "metadata": {}, "source": [ "And the solution is:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "sum([int(s) for s in \"6963524437876961749120273824619538346438023188214475670667\"])" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 144, "text": [ "272" ] } ], "prompt_number": 144 } ], "metadata": {} } ] }