MyThinkJulia-Ch07-Iteration.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ch 7: Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reassignment\n",
    "\n",
    "It is legal to make more than one assignment to the same variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Updating Variables\n",
    "\n",
    "A common kind of reassignment is an update, where the new value of the variable depends on the old.  Make sure you initialize a variable before you update it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = 0\n",
    "y = y + 1 # increment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The while statement\n",
    "\n",
    "Here is the flow of execution for a `while` statement:\n",
    "\n",
    "1. Determine whether the condition is true or false.\n",
    "2. If false, exit the while statement and continue execution at the next statement.\n",
    "3. If the condition is true, run the body and then go back to step 1.\n",
    "\n",
    "This type of flow is called a loop because the third step loops back around to the top."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "countdown (generic function with 1 method)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function countdown(n)\n",
    "    while n > 0\n",
    "        print(n, \" \")\n",
    "        n = n - 1\n",
    "    end\n",
    "    println(\"Blastoff!\")\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 4 3 2 1 Blastoff!\n"
     ]
    }
   ],
   "source": [
    "countdown(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The body of the loop should change the value of one or more variables so that the condition becomes false eventually and\n",
    "the loop terminates. Otherwise the loop will repeat forever, which is called an infinite loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7-1\n",
    "\n",
    "Rewrite the function `printntimes` from Chapter 5 using iteration instead of recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "printntimes (generic function with 1 method)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function printntimes(s, n)\n",
    "    \n",
    "    while n > 0\n",
    "        println(s)\n",
    "        n = n-1\n",
    "    end\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "spam\n",
      "spam\n",
      "spam\n",
      "spam\n",
      "spam\n"
     ]
    }
   ],
   "source": [
    "printntimes(\"spam\",5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Break\n",
    "\n",
    "Sometimes you don’t know it’s time to end a loop until you get half way through the body. In that case you can use the break statement to jump out of the loop.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> stdin> 1+2\n",
      "1+2\n",
      "> stdin> 3*4+sqrt(2)\n",
      "3*4+sqrt(2)\n",
      "> stdin> done\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "while true\n",
    "    print(\"> \")\n",
    "    line = readline()\n",
    "    if line == \"done\"\n",
    "        break\n",
    "    end\n",
    "    println(line)\n",
    "end\n",
    "\n",
    "println(\"Done!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This way of writing while loops is common because you can check the condition anywhere in the loop (not just at the top)\n",
    "and you can express the stop condition affirmatively (“stop when this happens”) rather than negatively (“keep going until\n",
    "that happens”)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Continue\n",
    "\n",
    "When a continue statement is encountered inside a loop, control jumps to the beginning of the loop for the next iteration, skipping the execution of statements inside the body of the loop for the current iteration. \n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8 10 "
     ]
    }
   ],
   "source": [
    "for i in 1:10\n",
    "    if i % 3 == 0\n",
    "        continue\n",
    "    end\n",
    "    print(i, \" \")\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Square Roots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way of computing square roots is Newton’s method. Suppose that you want to know the square root of $a$. If you start with almost any estimate, $x$, you can compute a better estimate with the following formula:\n",
    "\n",
    "$$y = \\frac{1}{2}\\left(x+\\frac{a}{x}\\right)$$\n",
    "\n",
    "Ideally, we want to repeat this process to improve our estimate until it stops changing, that is, we reach convergence ( $y=x$ ).  But it is generally dangerous to test float equality as floating-point values are only approximately right.  We instead test whether the absolute value of the difference is smaller than a small number $\\varepsilon$ (\\varepsilon TAB)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2.0\n",
      "1.75\n",
      "1.7321428571428572\n",
      "1.7320508100147274\n",
      "1.7320508075688772\n"
     ]
    }
   ],
   "source": [
    "a = 3\n",
    "x = 3\n",
    "ε = 1e-10\n",
    "\n",
    "while true\n",
    "\n",
    "    println(x)\n",
    "    \n",
    "    y = (x + a/x) / 2\n",
    "    \n",
    "    if abs(y-x) < ε\n",
    "        break\n",
    "    end\n",
    "    \n",
    "    x = y\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithm\n",
    "\n",
    "Newton's method is an example of algorithm, which is a mechanical process for solving a category of problems.\n",
    "\n",
    "Executing algorithms manually is boring, but designing them is interesting, intellectually challenging, and a central part of computer science.\n",
    "\n",
    "Some of the things that people do naturally, without difficulty or conscious thought, are the hardest to express algorithmically. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Debugging by Bisection\n",
    "\n",
    "One way to cut your debugging time is “debugging by bisection”. For example, if there are 100 lines in your program and you check them one at a time, it would take 100 steps.\n",
    "\n",
    "Instead, try to break the problem in half. Look at the middle of the program, or near it, for an intermediate value you can check. Add a print statement (or something else that has a verifiable effect) and run the program. If the mid-point check is incorrect, there must be a problem in the first half of the program. If it is correct, the problem is in the second half.\n",
    "\n",
    "In practice it is not always clear what the “middle of the program” is and not always possible to check it. It doesn’t make sense to count lines and find the exact midpoint. Instead, think about places in the program where there might be errors and places where it is easy to put a check. Then choose a spot where you think the chances are about the same that the bug is before or after the check."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7-2\n",
    "\n",
    "Copy the loop from Square Roots and encapsulate it in a function called `mysqrt` that takes $a$ as a parameter, chooses a reasonable initial guess for $x$, and returns an estimate of the square root of $a$.  \n",
    "\n",
    "\n",
    "To test it, we can print a table for $a$ = 1, 2, 3, ..., 7.\n",
    "\n",
    "\n",
    "```\n",
    "a   mysqrt             sqrt               diff\n",
    "-   ------             ----               ----\n",
    "1.0 1.0                1.0                0.0\n",
    "2.0 1.414213562373095  1.4142135623730951 2.220446049250313e-16\n",
    "3.0 1.7320508075688772 1.7320508075688772 0.0\n",
    "4.0 2.0                2.0                0.0\n",
    "5.0 2.23606797749979   2.23606797749979   0.0\n",
    "6.0 2.449489742783178  2.449489742783178  0.0\n",
    "7.0 2.6457513110645907 2.6457513110645907 0.0\n",
    "8.0 2.82842712474619   2.8284271247461903 4.440892098500626e-16\n",
    "9.0 3.0                3.0                0.0\n",
    "```\n",
    "\n",
    "The first column is a number, a ; the second column is the square root of a computed with mysqrt ; the third column is the square root computed by `sqrt` ; the fourth column is the absolute value of the difference between the two estimates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysqrt (generic function with 1 method)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#const ε = 1e-19\n",
    "\n",
    "function mysqrt(a)\n",
    "    \n",
    "    x = 1.0\n",
    "    \n",
    "    while true\n",
    "        y = (x + a/x) / 2\n",
    "        if abs(y-x) < ε\n",
    "            return y\n",
    "        end\n",
    "        x = y\n",
    "    end\n",
    "    \n",
    "end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "testsquareroot (generic function with 1 method)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function pad(content, n)\n",
    "  str = string(content)\n",
    "  len = length(str)\n",
    "  str = str * \" \" ^ (n-len)\n",
    "end\n",
    "\n",
    "function testsquareroot()\n",
    "  print(pad(\"a\", 4))\n",
    "  print(pad(\"mysqrt\", 19))\n",
    "  print(pad(\"sqrt\", 19))\n",
    "  println(\"diff\")\n",
    "  print(pad(\"-\", 4))\n",
    "  print(pad(\"------\", 19))\n",
    "  print(pad(\"----\", 19))\n",
    "  println(\"----\")\n",
    "  for a in 1.0:9.0\n",
    "    mysq = mysqrt(a)\n",
    "    sq = sqrt(a)\n",
    "    print(pad(a, 4))\n",
    "    print(pad(mysq, 19))\n",
    "    print(pad(sq, 19))\n",
    "    println(abs(mysq - sq))\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a   mysqrt             sqrt               diff\n",
      "-   ------             ----               ----\n",
      "1.0 1.0                1.0                0.0\n",
      "2.0 1.414213562373095  1.4142135623730951 2.220446049250313e-16\n",
      "3.0 1.7320508075688772 1.7320508075688772 0.0\n",
      "4.0 2.0                2.0                0.0\n",
      "5.0 2.23606797749979   2.23606797749979   0.0\n",
      "6.0 2.449489742783178  2.449489742783178  0.0\n",
      "7.0 2.6457513110645907 2.6457513110645907 0.0\n",
      "8.0 2.82842712474619   2.8284271247461903 4.440892098500626e-16\n",
      "9.0 3.0                3.0                0.0\n"
     ]
    }
   ],
   "source": [
    "testsquareroot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7-3\n",
    "\n",
    "The built-in function Meta.parse takes a string and transforms it into an expression. This expression can be evaluated in Julia with the function Core.eval. For example:\n",
    "\n",
    "```\n",
    "julia> expr = Meta.parse(\"1+2*3\")\n",
    ":(1 + 2 * 3)\n",
    "\n",
    "julia> eval(expr)\n",
    "7\n",
    "\n",
    "julia> expr = Meta.parse(\"sqrt(π)\")\n",
    ":(sqrt(π))\n",
    "\n",
    "julia> eval(expr)\n",
    "1.7724538509055159\n",
    "```\n",
    "\n",
    "Write a function called `evalloop` that iteratively prompts the user, takes the resulting input and evaluates it using eval,\n",
    "and prints the result. It should continue until the user enters done, and then return the value of the last expression it\n",
    "evaluated.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "evalloop (generic function with 1 method)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function evalloop()\n",
    "    \n",
    "    myvalue = 0  # We need to declare this variable outside the while loop\n",
    "                 # Otherwise, it is \"forgotten\" after each iteration loop.  \n",
    "                 # See the discussion on the variable scoping below.\n",
    "    \n",
    "    while true\n",
    "              \n",
    "        print(\"> \")\n",
    "        line = readline()\n",
    "              \n",
    "        if line == \"done\"\n",
    "            return myvalue\n",
    "        end\n",
    "\n",
    "        myvalue = eval(Meta.parse(line))\n",
    "        println(myvalue)\n",
    "        \n",
    "    end\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> stdin> 2+3\n",
      "5\n",
      "> stdin> 4*5*sqrt(2)+4\n",
      "32.2842712474619\n",
      "> stdin> done\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "32.2842712474619"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lasteval = evalloop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32.2842712474619"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lasteval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7-4\n",
    "\n",
    "The mathematician Srinivasa Ramanujan found an infinite series that can be used to generate a numerical approximation of $\\frac{1}{\\pi}$:\n",
    "\n",
    "$$\\frac{1}{\\pi} = \\frac{2 \\sqrt{2}}{9801} \\sum_{k=0}^{\\infty} \\frac{(4k)!(1103+26390k)}{(k!)^{4} 396^{4k}}$$\n",
    "\n",
    "\n",
    "Write a function called `estimatepi` that uses this formula to compute and return an estimate of π. It should use a while loop to compute terms of the summation until the last term is smaller than 1e-15 (which is Julia notation for $10^{-15}$). You can check the result by comparing it to π ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "estimatepi (generic function with 1 method)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function estimatepi()\n",
    "    \n",
    "    sum = 0.0\n",
    "    k = 0\n",
    "    \n",
    "    while true\n",
    "        \n",
    "        term = factorial(4*k)*(1103.0+26390.0*k)/((factorial(k))^4*396.0^(4*k))\n",
    "        sum = sum + term\n",
    "        \n",
    "        if abs(term) < 1e-15\n",
    "            break\n",
    "        end\n",
    "\n",
    "        k = k + 1\n",
    "        \n",
    "    end\n",
    "    \n",
    "    mypi = 9801.0/2.0/sqrt(2.0)/sum\n",
    "    \n",
    "end\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.141592653589793"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "estimatepi()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some Advanced Topics on Variable Scoping\n",
    "\n",
    "* The following rules and examples pertain to local scopes. A newly introduced variable in a local scope cannot be referenced by a parent scope. For example, in the following, the variable $z$ is not introduced into the top-level scope:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "ename": "UndefVarError",
     "evalue": "UndefVarError: z not defined",
     "output_type": "error",
     "traceback": [
      "UndefVarError: z not defined",
      "",
      "Stacktrace:",
      " [1] top-level scope at In[1]:4"
     ]
    }
   ],
   "source": [
    "for i = 1:10\n",
    "    z = i\n",
    "end\n",
    "\n",
    "z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Inner local scopes can, however, update variables in their parent scopes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "for i = 1:1\n",
    "    \n",
    "    z = i\n",
    "    \n",
    "    for j = 1:1\n",
    "        z = 0\n",
    "    end\n",
    "    \n",
    "    println(z)\n",
    "    \n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `for` loops, `while` loops, and comprehensions have the following behavior: any new variables introduced in their body scopes are freshly allocated for each loop iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* An iteration variable in the `for` loop or comprehension is always a new variable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f()\n",
    "    \n",
    "    i = 0\n",
    "    \n",
    "    for i = 1:3\n",
    "    end\n",
    "    \n",
    "    return i\n",
    "    \n",
    "end\n",
    "       \n",
    "f()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* However, it is occasionally useful to reuse an existing local variable as the iteration variable. This can be done conveniently by adding the keyword outer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function f()\n",
    "    \n",
    "    i = 0\n",
    "    \n",
    "    for outer i = 1:3\n",
    "    end\n",
    "    \n",
    "    return i\n",
    "\n",
    "end\n",
    "\n",
    "f()"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.4.0",
   "language": "julia",
   "name": "julia-1.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}