python/Problem_25.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Task 25: 1000-digit Fibonacci number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As Python cannot optimize tailrec, we'll implement basic fibonacci algorithm with a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4782\nSolution took 3.9149811267852783 seconds\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "start = time.time()\n",
    "\n",
    "def fibonacci(n):\n",
    "    fibs = [1, 1]\n",
    "    for j in range(2, n):\n",
    "        fibs.append(fibs[j-1] + fibs[j-2])\n",
    "    return max(fibs)\n",
    "\n",
    "i = 12\n",
    "\n",
    "while True:\n",
    "    a = fibonacci(i)\n",
    "    if len(str(a)) == 1000:\n",
    "        print(i)\n",
    "        break\n",
    "    i += 1\n",
    "    \n",
    "print(\"Solution took\", time.time() - start, \"seconds\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complexity of this algorithm is O(N^2) and can be improved by the following algorithm. that I used in Task 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4782\nSolution took 0.30280113220214844 seconds\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "\n",
    "\n",
    "def generate_fibonacci(N):\n",
    "    basis_a = 1\n",
    "\n",
    "    basis_b = 1\n",
    "\n",
    "    basis_c = 1\n",
    "\n",
    "    basis_d = 0\n",
    "\n",
    "    rc = 0\n",
    "\n",
    "    rd = 1\n",
    "\n",
    "    while N != 0:\n",
    "        if N & 1:\n",
    "            tc = rc\n",
    "            rc = rc * basis_a + rd * basis_c\n",
    "            rd = tc * basis_b + rd * basis_d\n",
    "\n",
    "        ta = basis_a\n",
    "        tb = basis_b\n",
    "        tc = basis_c\n",
    "\n",
    "        basis_a = basis_a * basis_a + basis_b * basis_c\n",
    "        basis_b = ta * basis_b + basis_b * basis_d\n",
    "        basis_c = basis_c * ta + basis_d * basis_c\n",
    "        basis_d = tc * tb + basis_d * basis_d\n",
    "\n",
    "        N >>= 1\n",
    "    return rc\n",
    "\n",
    "\n",
    "for i in range(0, 100000000):\n",
    "    fib = generate_fibonacci(i)\n",
    "    if len(str(fib)) == 1000:\n",
    "        print(i)\n",
    "        break\n",
    "        \n",
    "print(\"Solution took\", time.time() - start, \"seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This algorithm is much better and takes just O(N*log(N)) complexity"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}