removed cython annotations

Project Euler - Problem 16, 20 - Power digit sum & Factorial digit sum.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\"><li><span><a href=\"#Problem-16-—-Large-power-digit-sum\" data-toc-modified-id=\"Problem-16-—-Large-power-digit-sum-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Problem 16 — Large power digit sum</a></span></li><li><span><a href=\"#Problem-20-—-Factorial-digit-Sum\" data-toc-modified-id=\"Problem-20-—-Factorial-digit-Sum-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Problem 20 — Factorial digit Sum</a></span></li></ul></div>"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numba, pandas, time, os\nimport numpy as np\nfrom math import sqrt, ceil, floor, log10\nimport multiprocessing as mp\nfrom math import factorial as fact2\n%reload_ext cython\n%reload_ext line_profiler",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "os.environ['CC'] = 'clang'\n# os.environ['CC'] = 'gcc'",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Problem 16 &mdash; Large power digit sum"
    },
    {
      "metadata": {
        "trusted": true,
        "scrolled": false
      },
      "cell_type": "code",
      "source": "%%cython -c=-Ofast -c=-fopenmp --link-args=-fopenmp -c=-march=native --link-args=-march=native --link-args=-Ofast --force -c=-flto\n# cython: cdivision=True\n# cython: nonecheck=False\n# cython: wraparound=False\n# cython: boundscheck=False\n## cython: language=c++\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, round\nfrom cython.parallel cimport prange\nfrom cpython.mem cimport PyMem_RawMalloc, PyMem_RawFree\n\n# pointer to the linked list\nctypedef num* numptr\n\n# linked list to store individual digits of the result\ncdef struct num:\n    np.uint8_t val\n    numptr next_ptr\n    numptr prev_ptr\n#     bint next_exists\n\nprint(\"sizeof(num) = {} bytes\".format(sizeof(num)))\n\n\ncdef numptr new_num(np.uint8_t val=0, numptr prev_ptr=NULL, numptr next_ptr=NULL) nogil:\n    \"\"\"\n    Support function to create a new node in the linked list.\n    The returned object *MUST* be freed using `del_num` function.\n    \n    Parameters\n    ------------\n    val: int\n        divit value to store \n    prev_ptr: numptr\n        pointer to parent node\n    next_ptr: numptr\n        pointer to child node\n    \n    Returns\n    -------------\n    numptr\n    \"\"\"\n    cdef numptr out = <numptr> PyMem_RawMalloc(sizeof(num))\n    if out == NULL:\n        raise MemoryError(\"Unable to allocate memory.\")\n\n    out.val = val\n    out.prev_ptr = prev_ptr\n    out.next_ptr = next_ptr\n#     out.next_exists = True if next_ptr != NULL else False\n    return out\n\n\ncdef void del_num(numptr ptr=NULL) nogil:\n    \"\"\"\n    Support function to delete a node and all its child nodes \n    in the linked list.\n    \n    Parameters\n    ------------\n    ptr: numptr\n        pointer to node to delete from\n    \"\"\"\n    if ptr == NULL:\n        return\n\n    if ptr.next_ptr != NULL:\n        del_num(ptr.next_ptr)\n    PyMem_RawFree(ptr)\n\n    \ncdef list num_to_list(numptr number):\n    \"\"\"\n    Support function to convert the diits in the linked list \n    to a python list for convenient use.\n    \n    Parameters\n    ------------\n    number: numptr\n        pointer to parent node\n    \n    Returns\n    -------------\n    list\n    \"\"\"\n    cdef:\n        list out = []\n        numptr ptr = number\n        numptr ptr2\n    \n    if number == NULL:\n        raise Exception(\"Cannot convert NULL pointer to list.\")\n#         return out\n\n    while ptr != NULL:\n        ptr2 = ptr\n        ptr = ptr.next_ptr\n    \n    while ptr2 != NULL:\n        out.append(ptr2.val)\n        ptr2 = ptr2.prev_ptr\n    \n    return out\n\n\ndef sum_of_digits_power(int N, int P) -> int:\n    cdef list result = power(N, P)\n    return sum(result)\n\n\ncpdef list power(int N = 2, int P = 4):\n    \"\"\"\n    Function to compute any power P of base N, i.e,\n    $N^P$ of arbitrary lengths. Returns the result \n    as a list of digits in base 10 with the \n    most-significant-digit at index 0.\n    \n    Parameters\n    ------------\n    N: int\n        base integer\n    P: int\n        power value\n    \n    Returns\n    -------------\n    list\n    \"\"\"\n    cdef:\n        numptr head = new_num(1)\n        numptr ptr\n        int i, carry, temp, L\n        list result\n    \n    with nogil:\n        for i in range(P):\n            carry = 0\n            ptr = head\n            while ptr != NULL:\n                temp = ptr.val * N + carry\n    #             print(\"{} = {} * {} + {}\".format(temp, ptr.val, N, carry))\n                ptr.val = temp % 10\n                carry = temp // 10\n    #             print(temp, ptr.val, carry)\n                if carry > 0:\n                    if ptr.next_ptr == NULL:\n                        ptr.next_ptr = new_num(0, prev_ptr=ptr)\n                ptr = ptr.next_ptr\n\n    result = num_to_list(head)\n    L = len(result)\n    \n#     print(\"Depth: {}\\nMemory: {} bytes\".format(L, L*sizeof(num)))\n    \n    del_num(head)\n    \n    return result\n\n\ndef blank():\n    \"\"\"Required for line profiling\"\"\"\n    pass",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": "sizeof(num) = 24 bytes\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "P = 1000\n%lprun -f power -f sum_of_digits_power r = sum_of_digits_power(2, P)\n# print(r, \"\\n\", 1<<P)\nprint(\"Sum of digits: {}\\n--------------------\".format(r))",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Sum of digits: 1366\n--------------------\n",
          "name": "stdout"
        },
        {
          "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 power>\n  profile = LineProfiler(*funcs)\n/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 sum_of_digits_power>\n  profile = LineProfiler(*funcs)\n",
          "name": "stderr"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "%timeit r1 = power(2, 1000)\n%timeit r2 = sum_of_digits_power(2, 1000)\n# print(r1, \"\\n\", r2)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": "950 µs ± 26.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n995 µs ± 55.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "P = 1000\n%time r1 = power(2, P)\n%time r2 = sum_of_digits_power(2, P)\nprint(r1, \"\\n\", 1<<P)\nprint(\"Sum of digits: {}\\n--------------------\".format(r2))",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 2.29 ms, sys: 1.71 ms, total: 4 ms\nWall time: 3.94 ms\nCPU times: user 1.73 ms, sys: 231 µs, total: 1.96 ms\nWall time: 1.98 ms\n[1, 0, 7, 1, 5, 0, 8, 6, 0, 7, 1, 8, 6, 2, 6, 7, 3, 2, 0, 9, 4, 8, 4, 2, 5, 0, 4, 9, 0, 6, 0, 0, 0, 1, 8, 1, 0, 5, 6, 1, 4, 0, 4, 8, 1, 1, 7, 0, 5, 5, 3, 3, 6, 0, 7, 4, 4, 3, 7, 5, 0, 3, 8, 8, 3, 7, 0, 3, 5, 1, 0, 5, 1, 1, 2, 4, 9, 3, 6, 1, 2, 2, 4, 9, 3, 1, 9, 8, 3, 7, 8, 8, 1, 5, 6, 9, 5, 8, 5, 8, 1, 2, 7, 5, 9, 4, 6, 7, 2, 9, 1, 7, 5, 5, 3, 1, 4, 6, 8, 2, 5, 1, 8, 7, 1, 4, 5, 2, 8, 5, 6, 9, 2, 3, 1, 4, 0, 4, 3, 5, 9, 8, 4, 5, 7, 7, 5, 7, 4, 6, 9, 8, 5, 7, 4, 8, 0, 3, 9, 3, 4, 5, 6, 7, 7, 7, 4, 8, 2, 4, 2, 3, 0, 9, 8, 5, 4, 2, 1, 0, 7, 4, 6, 0, 5, 0, 6, 2, 3, 7, 1, 1, 4, 1, 8, 7, 7, 9, 5, 4, 1, 8, 2, 1, 5, 3, 0, 4, 6, 4, 7, 4, 9, 8, 3, 5, 8, 1, 9, 4, 1, 2, 6, 7, 3, 9, 8, 7, 6, 7, 5, 5, 9, 1, 6, 5, 5, 4, 3, 9, 4, 6, 0, 7, 7, 0, 6, 2, 9, 1, 4, 5, 7, 1, 1, 9, 6, 4, 7, 7, 6, 8, 6, 5, 4, 2, 1, 6, 7, 6, 6, 0, 4, 2, 9, 8, 3, 1, 6, 5, 2, 6, 2, 4, 3, 8, 6, 8, 3, 7, 2, 0, 5, 6, 6, 8, 0, 6, 9, 3, 7, 6] \n 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376\nSum of digits: 1366\n--------------------\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Problem 20 &mdash; Factorial digit Sum"
    },
    {
      "metadata": {
        "trusted": true,
        "scrolled": false
      },
      "cell_type": "code",
      "source": "%%cython -c=-Ofast -c=-fopenmp --link-args=-fopenmp -c=-march=native --link-args=-march=native --link-args=-Ofast -c=-flto --link-args=-flto --force\n# cython: cdivision=True\n# cython: nonecheck=False\n# cython: wraparound=False\n# cython: boundscheck=False\n#-# cython: language=c++\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, round\nfrom cython.parallel cimport prange\nfrom cpython.mem cimport PyMem_RawMalloc, PyMem_RawFree\n\n# pointer to the linked list\nctypedef num* numptr\n\n# linked list to store individual digits of the result\ncdef struct num:\n    np.uint8_t val\n    numptr next_ptr\n    numptr prev_ptr\n#     bint next_exists\n\nprint(\"sizeof(num)    = {} bytes\".format(sizeof(num)))\n\ncdef numptr new_num(np.uint8_t val=0, numptr prev_ptr=NULL, numptr next_ptr=NULL) nogil:\n    \"\"\"\n    Support function to create a new node in the linked list.\n    The returned object *MUST* be freed using `del_num` function.\n    \n    Parameters\n    ------------\n    val: int\n        divit value to store \n    prev_ptr: numptr\n        pointer to parent node\n    next_ptr: numptr\n        pointer to child node\n    \n    Returns\n    -------------\n    numptr\n    \"\"\"\n    cdef numptr out = <numptr> PyMem_RawMalloc(sizeof(num))\n    if out == NULL:\n        raise MemoryError(\"Unable to allocate memory.\")\n\n    out.val = val\n    out.prev_ptr = prev_ptr\n    out.next_ptr = next_ptr\n#     out.next_exists = True if next_ptr != NULL else False\n    return out\n\n\ncdef void del_num(numptr ptr=NULL) nogil:\n    \"\"\"\n    Support function to delete a node and all its child nodes \n    in the linked list.\n    \n    Parameters\n    ------------\n    ptr: numptr\n        pointer to node to delete from\n    \"\"\"\n    if ptr == NULL:\n        return\n\n    if ptr.next_ptr != NULL:\n        del_num(ptr.next_ptr)\n    PyMem_RawFree(ptr)\n\n    \ncdef list num_to_list(numptr number):\n    \"\"\"\n    Support function to convert the diits in the linked list \n    to a python list for convenient use.\n    \n    Parameters\n    ------------\n    number: numptr\n        pointer to parent node\n    \n    Returns\n    -------------\n    list\n    \"\"\"\n    cdef:\n        list out = []\n        numptr ptr = number\n        numptr ptr2\n    \n    if number == NULL:\n        raise Exception(\"Cannot convert NULL pointer to list.\")\n#         return out\n\n    while ptr != NULL:\n        ptr2 = ptr\n        ptr = ptr.next_ptr\n    \n    while ptr2 != NULL:\n        out.append(ptr2.val)\n        ptr2 = ptr2.prev_ptr\n    \n    return out\n\n\ncpdef int sum_of_digits_factorial(int N):\n    cdef list result = factorial(N)\n    return sum(result)\n\n\ncpdef list factorial(int N = 2):\n    \"\"\"\n    Function to compute any power P of base N, i.e,\n    $N^P$ of arbitrary lengths. Returns the result \n    as a list of digits in base 10 with the \n    most-significant-digit at index 0.\n    \n    Parameters\n    ------------\n    N: int\n        base integer\n    P: int\n        power value\n    \n    Returns\n    -------------\n    list\n    \"\"\"\n    cdef:\n        numptr head = new_num(1)\n        numptr ptr\n        int i, carry, temp, L\n        list result\n    \n    with nogil:\n        for i in range(1, N+1):\n            carry = 0\n            ptr = head\n            while ptr != NULL:\n                temp = ptr.val * i + carry\n    #             print(\"{} = {} * {} + {}\".format(temp, ptr.val, N, carry))\n                ptr.val = temp % 10\n                carry = temp // 10\n    #             print(temp, ptr.val, carry)\n                if carry > 0:\n                    if ptr.next_ptr == NULL:\n                        ptr.next_ptr = new_num(0, prev_ptr=ptr)\n                ptr = ptr.next_ptr\n        \n    result = num_to_list(head)\n    L = len(result)\n    \n#     print(\"Depth: {}\\nMemory: {} bytes\".format(L, L*sizeof(num)))\n    \n    del_num(head)\n    \n    return result\n\n\ndef blank():\n    \"\"\"Required for line profiling\"\"\"\n    pass",
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": "sizeof(num)    = 24 bytes\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "N = 120\n%time r = factorial(N)\n%time fact2(N)\nprint(r)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "CPU times: user 204 µs, sys: 76 µs, total: 280 µs\nWall time: 286 µs\nCPU times: user 10 µs, sys: 1 µs, total: 11 µs\nWall time: 15 µs\n[6, 6, 8, 9, 5, 0, 2, 9, 1, 3, 4, 4, 9, 1, 2, 7, 0, 5, 7, 5, 8, 8, 1, 1, 8, 0, 5, 4, 0, 9, 0, 3, 7, 2, 5, 8, 6, 7, 5, 2, 7, 4, 6, 3, 3, 3, 1, 3, 8, 0, 2, 9, 8, 1, 0, 2, 9, 5, 6, 7, 1, 3, 5, 2, 3, 0, 1, 6, 3, 3, 5, 5, 7, 2, 4, 4, 9, 6, 2, 9, 8, 9, 3, 6, 6, 8, 7, 4, 1, 6, 5, 2, 7, 1, 9, 8, 4, 9, 8, 1, 3, 0, 8, 1, 5, 7, 6, 3, 7, 8, 9, 3, 2, 1, 4, 0, 9, 0, 5, 5, 2, 5, 3, 4, 4, 0, 8, 5, 8, 9, 4, 0, 8, 1, 2, 1, 8, 5, 9, 8, 9, 8, 4, 8, 1, 1, 1, 4, 3, 8, 9, 6, 5, 0, 0, 0, 5, 9, 6, 4, 9, 6, 0, 5, 2, 1, 2, 5, 6, 9, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "N = 200\nprint(\"\", str(fact2(N)), \"\\n\", \"\".join(str(x) for x in factorial(N)))",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": " 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 \n 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000\n",
          "name": "stdout"
        }
      ]
    },
    {
      "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"
      ],
      "position": {
        "left": "1218px",
        "top": "100px",
        "width": "350px",
        "height": "144px",
        "right": "20px"
      }
    },
    "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": "b73d4137cd36d63ec1093456430abd97",
      "data": {
        "description": "removed cython annotations",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/b73d4137cd36d63ec1093456430abd97"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}