example_notebooks/fibonacci.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This program demonstrates using cached procedures for improving the computation\n",
    "of Fibonacci numbers\n",
    "\n",
    "The Fibonacci numbers are computed as follows:\n",
    "\n",
    "f(0) := 0;\n",
    "\n",
    "f(1) := 1;\n",
    "\n",
    "f(n) := f(n-1) + f(n-2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fibonacci Sequence: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025]\n",
      "(635594 ticks)\n",
      "Fibonacci Sequence: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025]\n",
      "(26 ticks, {[\"cache hits\", 48], [\"cached items\", 26]})\n",
      "~< Result: om >~\n"
     ]
    }
   ],
   "source": [
    "class tracker() {\n",
    "    static {\n",
    "        ticks := 0;\n",
    "    }\n",
    "}\n",
    "\n",
    "// first the uncached version:\n",
    "fibonacci_1 := procedure(n) {\n",
    "    tracker.ticks += 1;\n",
    "    if (n in [0,1]) {\n",
    "        return n;\n",
    "    }\n",
    "    return fibonacci_1(n-1) + fibonacci_1(n-2);\n",
    "};\n",
    "\n",
    "start := now(); tracker.ticks := 0;\n",
    "print(\"Fibonacci Sequence: $[fibonacci_1(n) : n in [0..25]]$\");\n",
    "//nPrint(\"Computation took $0.001 * (now() - start)$seconds. \");\n",
    "print(\"($tracker.ticks$ ticks)\");\n",
    "\n",
    "// second the cached version:\n",
    "fibonacci_2 := cachedProcedure(n) {\n",
    "    tracker.ticks += 1;\n",
    "    if (n in [0,1]) {\n",
    "        return n;\n",
    "    }\n",
    "    return fibonacci_2(n-1) + fibonacci_2(n-2);\n",
    "};\n",
    "\n",
    "start := now(); tracker.ticks := 0;\n",
    "print(\"Fibonacci Sequence: $[fibonacci_2(n) : n in [0..25]]$\");\n",
    "//nPrint(\"Computation took $0.001 * (now() - start)$seconds. \");\n",
    "print(\"($tracker.ticks$ ticks, $cacheStats(fibonacci_2)$)\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "iSetlX",
   "language": "SetlX",
   "name": "isetlx"
  },
  "language_info": {
   "codemirror_mode": "text/x-java",
   "file_extension": ".stlx",
   "mimetype": "text/setlx",
   "name": "SetlX"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}