Fibonacci.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "important-borough",
   "metadata": {},
   "source": [
    "# Codewars The Millionth Fibonacci Kata"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aquatic-bidder",
   "metadata": {},
   "source": [
    "fib(0) = 0  \n",
    "fib(1) = 1  \n",
    "fib(n + 2) = fib(n + 1) + fib(n)  \n",
    "\n",
    "Write an algorithm that can handle n up to 2000000  \n",
    "\n",
    "Your algorithm must output the exact integer answer, to full precision. Also, it must correctly handle negative numbers as input.  \n",
    "\n",
    "**HINT** I: Can you rearrange the equation fib(n + 2) = fib(n + 1) + fib(n) to find fib(n) if you already know fib(n + 1) and fib(n + 2)? Use this to reason what value fib has to have for negative values.  \n",
    "\n",
    "**HINT** II: See https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "upper-cleaning",
   "metadata": {},
   "source": [
    "Fibonacci Numbers  \n",
    "0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "double-performance",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Simplest Solution: Recursion \n",
    "## very time consuming\n",
    "\n",
    "def f(n):\n",
    "    if n == 0:\n",
    "        return n\n",
    "    elif n == 1:\n",
    "        return n\n",
    "    else:\n",
    "        return f(n-2) + f(n-1)\n",
    "\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "equal-music",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Some optimization: Dynamic Programming, Memorization\n",
    "# We can optimize the space by storing the previous two numbers \n",
    "# only because that is all we need to get the next Fibonacci number \n",
    "# in series. \n",
    "## faster than recursion, but still unable to handle n = 2 million\n",
    "\n",
    "def f(n):\n",
    "    a = 0\n",
    "    b = 1\n",
    "    if n == 0:\n",
    "        return a\n",
    "    elif n ==1:\n",
    "        return b\n",
    "    else:\n",
    "        for i in range(2,n+1): #loop add all previous numbers\n",
    "            c = a + b\n",
    "            a = b\n",
    "            b = c\n",
    "        return b\n",
    "\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "confirmed-volleyball",
   "metadata": {},
   "source": [
    "# Further Optimization: power of the matrix {{1, 1}, {1, 0}}\n",
    "\n",
    "calculate power(M, n)), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.  \n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{n+1} & F_{n} \\\\\n",
    "F_{n} & F_{n-1}\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Note: in Matrix Algebra,   \n",
    "the ij-th entry of the product matrix C is the dot product of the i-th row of A with the j-th column of B.  \n",
    "\n",
    "Therefore, the 00-th entry $F_{n+1}$ is the dot product of 0-th row of \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$ and 0-th column of \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "western-worker",
   "metadata": {},
   "source": [
    "Fibonacci Numbers  \n",
    "0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "studied-report",
   "metadata": {},
   "source": [
    "Example:  \n",
    "$F_{2}$ &#8594; n = 1  \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^1$\n",
    "\n",
    "$F_{3}$ &#8594; n = 2 \n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^2$ &#8594;\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}$ x \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "higher-companion",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Using Numpy numpy.linalg.matrix_power\n",
    "import numpy as np\n",
    "\n",
    "def f(n):\n",
    "    if n == 0:\n",
    "        return n\n",
    "    elif n ==1:\n",
    "        return n\n",
    "    else:\n",
    "        i = np.array([[1,1],[1,0]])\n",
    "        return np.linalg.matrix_power(i,n-1)[0,0] # to the power of n-1\n",
    "\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "german-pizza",
   "metadata": {},
   "source": [
    "# Optimization of Exponentiation \n",
    "[link](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4)  \n",
    "\n",
    "Consider the problem of computing the exponential of a given number.   \n",
    "base b and a positive integer exponent n and computes $b^n$. \n",
    "\n",
    "One way to do this is via the recursive definition  \n",
    "$b^0 = 1$  \n",
    "$b^n = b \\cdot b^{n-1}$\n",
    "\n",
    "This is a linear recursive process, which requires $\\theta(n)$ steps and $\\theta (n)$ space. \n",
    "\n",
    "### Optimization\n",
    "\n",
    "We can compute exponentials in fewer steps by using successive squaring. For instance, rather than computing $b^8$ as  \n",
    "$ b \\cdot(b \\cdot(b \\cdot(b \\cdot(b \\cdot(b \\cdot(b \\cdot(b)))))))$  \n",
    "\n",
    "We can compute it using three multiplications:  \n",
    "$b^2 = b \\cdot b$  \n",
    "$b^4 = b^2 \\cdot b^2$  \n",
    "$b^8 = b^4 \\cdot b^4$\n",
    "\n",
    "We can take advantage of successive squaring in computing exponentials in general if we use the rule  \n",
    "$b^n = (b^{n/2})^2$ if n is even  \n",
    "$b^n = b \\cdot b^{n-1}$ if n is odd\n",
    "\n",
    "the number of multiplications required for an exponent of n grows about as fast as the logarithm of n to the base 2. The process has $\\theta (log_n)$ growth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "contrary-defense",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Exponential recursive\n",
    "\n",
    "def expt(b,n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return b * expt(b,n-1)\n",
    "    \n",
    "expt(5,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "still-driving",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#optimize exponential\n",
    "\n",
    "def expt(b,n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    elif n % 2 == 0:\n",
    "        return expt(b,n/2) ** 2\n",
    "    else:\n",
    "        return b * expt(b,n-1)\n",
    "    \n",
    "expt(5,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "individual-cleaning",
   "metadata": {},
   "source": [
    "# Power of Matrix Optimization\n",
    "\n",
    "Recall the power of matrix equation for fibonacci number $F_{n+1}$:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{n+1} & F_{n} \\\\\n",
    "F_{n} & F_{n-1}\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Taking determinant on both sides, we get  \n",
    "$(-1)^n = F_{n+1}\\cdot F_{n-1} – F_{n}^2$ \n",
    "\n",
    "Moreover, since $A^n \\cdot A^m = A^{n+m}$ for any square matrix A  \n",
    "\n",
    "$F_m \\cdot F_n + F_{m-1} \\cdot F_{n-1} = F_{m+n-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tracked-envelope",
   "metadata": {},
   "source": [
    "To come up with above equation:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{n+1} & F_{n} \\\\\n",
    "F_{n} & F_{n-1}\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^m$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{m+1} & F_{m} \\\\\n",
    "F_{m} & F_{m-1}\n",
    "\\end{pmatrix}$\n",
    "\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^n$ x\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^m$ =\n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n+m}$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{m+n+1} & F_{m+n} \\\\\n",
    "F_{m+n} & F_{m+n-1}\n",
    "\\end{pmatrix}$ = \n",
    "$\\begin{pmatrix}\n",
    "F_{n+1} & F_{n} \\\\\n",
    "F_{n} & F_{n-1}\n",
    "\\end{pmatrix}$ x\n",
    "$\\begin{pmatrix}\n",
    "F_{m+1} & F_{m} \\\\\n",
    "F_{m} & F_{m-1}\n",
    "\\end{pmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "qualified-helicopter",
   "metadata": {},
   "source": [
    "Let's simplify the matrix muliplication:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "F_{n+1} & F_{n} \\\\\n",
    "F_{n} & F_{n-1}\n",
    "\\end{pmatrix}$ x\n",
    "$\\begin{pmatrix}\n",
    "F_{m+1} & F_{m} \\\\\n",
    "F_{m} & F_{m-1}\n",
    "\\end{pmatrix}$ =\n",
    "$\\begin{pmatrix}\n",
    "F_{m+1} \\cdot F_{n+1} + F_m \\cdot F_n & F_{m} \\cdot F_{n+1} + F_{m-1} \\cdot F_n \\\\\n",
    "F_{m+1} \\cdot F_n + F_m \\cdot F_{n-1} & F_{m} \\cdot F_n + F_{m-1} \\cdot F_{n-1}\n",
    "\\end{pmatrix}$ "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "historic-pulse",
   "metadata": {},
   "source": [
    "Therefore, we have  \n",
    "$F_m \\cdot F_n + F_{m-1} \\cdot F_{n-1} = F_{m+n-1}$  \n",
    "$F_m \\cdot F_{n+1} + F_{m-1} \\cdot F_{n} = F_{m+n}$\n",
    "\n",
    "Let m = n:  \n",
    "$F_n^2 + F_{n-1}^2 = F_{2n-1}$  \n",
    "$F_n \\cdot (F_{n+1} + F_{n-1}) = F_{2n}$\n",
    "\n",
    "Given that:  \n",
    "$F_{n+1} = F_n + F_{n-1}$  \n",
    "Therefore,  \n",
    "$F_{2n} = (2 \\cdot F_{n-1} + F_n) \\cdot F_n$  \n",
    "$F_{2n-1} = F_n^2 + F_{n-1}^2$  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "closing-activity",
   "metadata": {},
   "source": [
    "If n is even then k = n/2:  \n",
    "$F_n = (2 \\cdot F_{k-1} + F_k) \\cdot F_k$ \n",
    "\n",
    "$2 \\cdot F_{k-1} \\cdot F_k + F_k^2$\n",
    "\n",
    "If n is odd then k = (n + 1)/2  \n",
    "$F_n = F_k \\cdot F_k + F_{k-1} \\cdot F_{k-1}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "anonymous-throat",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Power of Matrix optimization\n",
    "\n",
    "def f(n):\n",
    "    if n == 0:\n",
    "        return n\n",
    "    elif n ==1:\n",
    "        return n\n",
    "    else:\n",
    "        if n % 2 ==0:\n",
    "            k = n // 2\n",
    "            return 2 * f(k-1) * f(k) + f(k) ** 2\n",
    "        else:\n",
    "            k = (n+1) // 2\n",
    "            return f(k) ** 2 + f(k-1) ** 2\n",
    "\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "passing-switzerland",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Power of matrix optimization, memorization\n",
    "\n",
    "def f(n):\n",
    "    m = [0] * (n+1)\n",
    "    if n == 0:\n",
    "        return n\n",
    "    elif n ==1 or n ==2:\n",
    "        m[n] = 1\n",
    "        return m[n]\n",
    "    else:      \n",
    "        if n % 2 ==0:\n",
    "            k = n // 2\n",
    "            m[n] = 2 * f(k-1) * f(k) + f(k) ** 2\n",
    "        else:\n",
    "            k = (n+1) // 2\n",
    "            m[n] = f(k) ** 2 + f(k-1) ** 2\n",
    "        return m[n]\n",
    "\n",
    "f(4)        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hairy-sheffield",
   "metadata": {},
   "source": [
    "# Power of Matrix, Optimization exponentiation\n",
    "\n",
    "$F_n$ = \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}$\n",
    "\n",
    "if n-1 is even:  \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}$ = \n",
    "$(\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{(n-1)/2})^2$\n",
    "\n",
    "if n-1 is odd:  \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}$ = \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}$ x \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-2}$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "american-garlic",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Matrix exponentiation optimization\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def m(b,n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    if n % 2 == 0:\n",
    "        return np.dot(m(b,n/2),m(b,n/2))\n",
    "    else:\n",
    "        return np.dot(b,m(b,n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "dangerous-evening",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Power of Matrix, Optimization exponentiation\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def f(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n ==1 or n == -1:\n",
    "        return 1\n",
    "    elif n > 1:\n",
    "        i = np.array([[1,1],[1,0]])\n",
    "    elif n < -1: \n",
    "        i = np.array([[-1,1],[1,0]])\n",
    "    return m(i,abs(n)-1)[0,0] # to the power of n-1         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "french-immigration",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1845853122"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(-75)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "southeast-plumbing",
   "metadata": {},
   "source": [
    "# Negative Fibonacci\n",
    "\n",
    "... −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8\n",
    "\n",
    "[wikipedia](https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Extension_to_negative_integers)\n",
    "\n",
    "[Negafibonacci Numbers via Matrices](http://www.viam.science.tsu.ge/others/ticmi/blt/vol23_1/3_triana.pdf)\n",
    "\n",
    "if n is positive:\n",
    "\n",
    "$F_n$ = \n",
    "$\\begin{pmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}$\n",
    "\n",
    "if n is negative:\n",
    "\n",
    "$F_n$ = \n",
    "$\\begin{pmatrix}\n",
    "-1 & 1 \\\\\n",
    "1 & 0\n",
    "\\end{pmatrix}^{n-1}$"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}