Project Euler - Problem 14 - Longest Collatz Sequence.ipynb

Project Euler - Problem 14 - Longest Collatz Sequence.ipynb

{
  "cells": [
    {
      "metadata": {
        "toc": true
      },
      "cell_type": "markdown",
      "source": "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n<div class=\"toc\"><ul class=\"toc-item\"></ul></div>"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numba, pandas, time, os\nimport numpy as np\nfrom math import sqrt, ceil\nimport multiprocessing as mp\n%reload_ext cython\n%reload_ext line_profiler",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "os.environ['CC'] = 'clang-mp-8.0'\n# os.environ['CC'] = 'gcc-mp-9'",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def collatz(N: int) -> int:\n    count = 1\n    while N > 1:\n        if N & 1 == 0: # n is even\n            N = N >> 1\n        else:\n            N = 3 * N + 1\n        count += 1\n    return count\n\ndef result(MAX_N: int) -> (int, int):\n    max_c, n = 0, 0\n    for i in range(1, MAX_N):\n        c = collatz(i)\n        if c > max_c:\n            max_c, n = c, i\n    return max_c, n\n\ndef result_p(MAX_N: int) -> (int, int):\n    max_c, n = 0, 0\n    i = 0\n    with mp.Pool(mp.cpu_count()-1) as p: # keep one core for unpacking the results\n        res = p.map(collatz, range(1, MAX_N))\n    max_c = max(res)\n    n = res.index(max_c)\n    return n, max_c",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "MAX_N = int(1e6)\n# %time c, i = result(MAX_N)\n%time c, i = result_p(MAX_N)\nprint(c, i)",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 144 ms, sys: 31.8 ms, total: 175 ms\nWall time: 11.6 s\n837798 525\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "@numba.jit(nopython=True)\ndef collatz_n(N: int) -> int:\n    count = 1\n    while N > 1:\n        if N & 1 == 0: # n is even\n            N = N >> 1\n        else:\n            N = 3 * N + 1\n        count += 1\n    return count\n\n@numba.njit(parallel=False)\ndef result_n(MAX_N: int) -> (int, int):\n    max_c, n = 0, 0\n    for i in numba.prange(1, MAX_N):\n        c = collatz_n(i)\n        if c > max_c:\n            max_c, n = c, i\n    return n, max_c",
      "execution_count": 5,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "MAX_N = int(1e6)\n%time c, i = result_n(MAX_N)\nprint(c, i)",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 383 ms, sys: 42 ms, total: 425 ms\nWall time: 430 ms\n837799 525\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "%%cython -c=-Ofast -c=-fopenmp --link-args=-fopenmp -c=-march=native --link-args=-march=native -c=-flto=thin\n# cython: cdivision=True\n# cython: nonecheck=False\n# cython: wraparound=False\n# cython: boundscheck=False\n## cython: linetrace=True\n## cython: binding=True\n## distutils: define_macros=CYTHON_TRACE_NOGIL=1\n\ncimport numpy as np\nfrom libc.math cimport sqrt, ceil\nfrom cython.parallel cimport prange\nfrom cpython.mem cimport PyMem_RawMalloc, PyMem_RawFree\n\ncdef np.uint64_t collatz_c(unsigned long N) nogil:\n    cdef np.uint64_t count = 1\n    while N > 1:\n        if N & 1 == 0: # n is even\n            N = N >> 1\n        else:\n            N = 3 * N + 1\n        count += 1\n    return count\n\n\ncpdef tuple result_c(int MAX_N):\n    cdef np.uint64_t c, max_c = 0\n    cdef np.uint64_t n = 0\n    cdef int i\n    cdef np.uint64_t *C = <np.uint64_t*> PyMem_RawMalloc(MAX_N * sizeof(np.uint64_t))\n    C[0] = 0\n    \n    for i in prange(1, MAX_N, nogil=True, schedule='dynamic'):\n        C[i] = collatz_c(i)\n    \n    for i in range(MAX_N):\n        if C[i] > max_c:\n            max_c = C[i]\n            n = i\n    \n    PyMem_RawFree(C)\n    return n, max_c\n\ndef blank():\n    \"\"\"Required for line profiling\"\"\"\n    pass",
      "execution_count": 12,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "MAX_N = int(1e7)\n%time c, i = result_c(MAX_N)\nprint(c, i)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 2.81 s, sys: 194 ms, total: 3.01 s\nWall time: 838 ms\n8400511 686\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "scrolled": true
      },
      "cell_type": "code",
      "source": "%lprun -f result_c result_c(1e5)",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": "/Users/kvedala/anaconda3/lib/python3.7/site-packages/line_profiler/line_profiler.py:328: UserWarning: Could not extract a code object for the object <built-in function result_c>\n  profile = LineProfiler(*funcs)\n",
          "name": "stderr"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "MAX_N = int(1e6)\n%timeit result_p(MAX_N)\n%timeit result_n(MAX_N)\n%timeit result_c(MAX_N)",
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": "12.4 s ± 530 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n166 ms ± 444 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n64.7 ms ± 452 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "result_p(MAX_N), result_n(MAX_N), result_c(MAX_N)",
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 11,
          "data": {
            "text/plain": "((837798, 525), (837799, 525), (837799, 525))"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.6",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "hide_input": false,
    "varInspector": {
      "window_display": true,
      "cols": {
        "lenName": 16,
        "lenType": 16,
        "lenVar": 40
      },
      "kernels_config": {
        "python": {
          "library": "var_list.py",
          "delete_cmd_prefix": "del ",
          "delete_cmd_postfix": "",
          "varRefreshCmd": "print(var_dic_list())"
        },
        "r": {
          "library": "var_list.r",
          "delete_cmd_prefix": "rm(",
          "delete_cmd_postfix": ") ",
          "varRefreshCmd": "cat(var_dic_list()) "
        }
      },
      "types_to_exclude": [
        "module",
        "function",
        "builtin_function_or_method",
        "instance",
        "_Feature"
      ]
    },
    "nbTranslate": {
      "hotkey": "alt-t",
      "sourceLang": "en",
      "targetLang": "fr",
      "displayLangs": [
        "*"
      ],
      "langInMainMenu": true,
      "useGoogleTranslate": true
    },
    "toc": {
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": false,
      "base_numbering": 1,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": true,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": false
    },
    "gist": {
      "id": "56c3c155b6e0bd502cf1efdabe0eddd8",
      "data": {
        "description": "Project Euler - Problem 14 - Longest Collatz Sequence.ipynb",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/56c3c155b6e0bd502cf1efdabe0eddd8"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}