{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Comparison of time efficiency for JVM, python, scheme , C and pypy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Sum of primes below 1000000 in python, scheme, java and C, and pypy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import Euler as eu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sum_primes_below(n):\n",
    "    sum = 0\n",
    "    i = 2\n",
    "    while i <= n:\n",
    "        if eu.miller_rabin(i):\n",
    "            sum +=i\n",
    "            i += 1\n",
    "        else:\n",
    "            i += 1\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "CPU times: user 16 s, sys: 0 ns, total: 16 s\n",
      "Wall time: 16 s\n"
     ]
    }
   ],
   "source": [
    "#cpython:\n",
    "%time print(sum_primes_below(1000000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "CPU times: user 248 ms, sys: 28 ms, total: 276 ms\n",
      "Wall time: 14 s\n"
     ]
    }
   ],
   "source": [
    "#racket scheme:\n",
    "% time! racket racket_tests.rkt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "! touch Benchmarks.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "! javac Benchmarks.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "1 loop, best of 3: 5.5 s per loop\n"
     ]
    }
   ],
   "source": [
    "#java:\n",
    "%timeit ! java Benchmarks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "375504020233755040202337550402023375504020231 loop, best of 3: 487 ms per loop\n"
     ]
    }
   ],
   "source": [
    "# c++:\n",
    "%timeit ! ./benchmarks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing benchmarks_pypy_2.py\n"
     ]
    }
   ],
   "source": [
    "# writting pypy file\n",
    "%%writefile -a benchmarks_pypy_2.py\n",
    "import Euler as eu\n",
    "def sum_primes_below(n):\n",
    "    sum = 0\n",
    "    i = 2\n",
    "    while i <= n:\n",
    "        if eu.miller_rabin(i):\n",
    "            sum +=i\n",
    "            i += 1\n",
    "        else:\n",
    "            i += 1\n",
    "    return sum\n",
    "print(sum_primes_below(1000000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Finally python with JIT, i.e. pypy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "1 loop, best of 3: 1.47 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit ! pypy benchmarks_pypy_2.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Results***\n",
    "\n",
    "Taking, obviously the best,  c++ as 100%:\n",
    "1. c++ -> 100% , 0.487ms\n",
    "2. pypy -> 301.8%, 1.47 s\n",
    "3. java -> 1129.3%, 5.5 s\n",
    "4. scheme -> 2874.7%, 14 s\n",
    "5. cpython -> 3285.4%, 16 s\n",
    "\n",
    "While the firs place is not a surprise, I don't know why java is so slow comparing to pypy (I compiled file with no flags added [javac 'filename']...).\n",
    "All the  algorithms are similar, while loop, and miller rabin test. Listings (python code above):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\r\n",
      "import java.math.BigInteger;\r\n",
      "import java.util.*;\r\n",
      "\r\n",
      "public class Benchmarks {\r\n",
      "\tpublic static long sumOfPrimes(long n) {\r\n",
      "\t\tlong sum = 0;\r\n",
      "\t\tlong i = 2;\r\n",
      "\t\twhile (i <= n) {\r\n",
      "\t\t\tBigInteger tmp = new BigInteger(Long.toString(i));\r\n",
      "\t\t\tif (tmp.isProbablePrime(50)) {\r\n",
      "\t\t\t\tsum += i;\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t\t}\r\n",
      "\t\t\telse\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t}\r\n",
      "\t\treturn sum;\r\n",
      "\t}\r\n",
      "\tpublic static void main(String [] args) {\r\n",
      "\t\t//final long startTime = System.currentTimeMillis();\r\n",
      "\t\tSystem.out.println(sumOfPrimes(1000000));\r\n",
      "\t\t//final long endTime = System.currentTimeMillis();\r\n",
      "\t\t//System.out.println(\"Total execution time: \" + (endTime - startTime));\r\n",
      "\t}\r\n",
      "}\r\n"
     ]
    }
   ],
   "source": [
    "! cat Benchmarks.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#lang racket\r\n",
      "(require racket/include)\r\n",
      "(include \"millerrabin.rkt\")\r\n",
      " \r\n",
      "\r\n",
      "(define (reduce xs f start)\r\n",
      "  (if (empty? xs) start\r\n",
      "      (reduce (cdr xs) f (f start (car xs)))))\r\n",
      "\r\n",
      "(reduce (filter prime? (range 2 1000000)) + 0)"
     ]
    }
   ],
   "source": [
    "! cat racket_tests.rkt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** Edit ***\n",
    "After changes to algorithms (java and pypy only) - function is_prime is a simply loop, and there is no \n",
    "bigintegers in java file, results after listings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting pypy_vs_java_test.py\n"
     ]
    }
   ],
   "source": [
    "# pypy:\n",
    "%%writefile  pypy_vs_java_test.py\n",
    "import math\n",
    "def is_prime(n):\n",
    "    if n == 2 or n == 3 or n == 5: return True\n",
    "    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:\n",
    "        return False\n",
    "    i = 7\n",
    "    limit = int(math.sqrt(n))\n",
    "    while i < limit + 1:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        else:\n",
    "            i += 2\n",
    "    return True\n",
    "def f(n):\n",
    "    sum = 0\n",
    "    i = 2\n",
    "    while i <= n:\n",
    "        if is_prime(i):\n",
    "            sum += i\n",
    "            i += 1\n",
    "        else:\n",
    "            i += 1\n",
    "    return sum\n",
    "print(f(1000000))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\r\n",
      "import java.lang.Math.*;\r\n",
      "import java.math.BigInteger;\r\n",
      "import java.util.*;\r\n",
      "\r\n",
      "public class Benchmarks {\r\n",
      "\t\r\n",
      "\tpublic static boolean is_prime(long n) {\r\n",
      "\t\tif (n == 2 || n == 3 | n == 5) return true;\r\n",
      "\t\tif ((n%2==0) || (n%3==0) || (n%5==0)) {\r\n",
      "\t\t\treturn false;\r\n",
      "\t\t}\r\n",
      "\t\telse {\r\n",
      "\t\t\tlong i = 7;\r\n",
      "\t\t\tlong limit = (long) java.lang.Math.sqrt(n);\r\n",
      "\t\t\twhile (i <= limit + 1) {\r\n",
      "\t\t\t\tif (n % i == 0) {\r\n",
      "\t\t\t\t\treturn false;\r\n",
      "\t\t\t\t}\r\n",
      "\t\t\t\telse {\r\n",
      "\t\t\t\t\ti += 2;\r\n",
      "\t\t\t\t}\r\n",
      "\t\t\t}\r\n",
      "\t\t\treturn true;\r\n",
      "\t\t}\r\n",
      "\t}\r\n",
      "\t\r\n",
      "\tpublic static long sum_0f_primes2(long n) {\r\n",
      "\t\tlong sum = 0;\r\n",
      "\t\tlong i = 2;\r\n",
      "\t\twhile (i <= n) {\r\n",
      "\t\t\tif (is_prime(i)) {\r\n",
      "\t\t\t\tsum += i;\r\n",
      "\t\t\t\ti++;\r\n",
      "\t\t\t}\r\n",
      "\t\t\telse {\r\n",
      "\t\t\t\ti++;\r\n",
      "\t\t\t}\r\n",
      "\t\t}\r\n",
      "\t\treturn sum;\r\n",
      "\t}\r\n",
      "\t\r\n",
      "\tpublic static long sumOfPrimes(long n) {\r\n",
      "\t\tlong sum = 0;\r\n",
      "\t\tlong i = 2;\r\n",
      "\t\tBigInteger ZERO = BigInteger.ZERO;\r\n",
      "\t\twhile (i <= n) {\r\n",
      "\t\t\tBigInteger tmp = new BigInteger(Long.toString(i));\r\n",
      "\t\t\tif (tmp.isProbablePrime(50)) {\r\n",
      "\t\t\t\tsum += i;\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t\t}\r\n",
      "\t\t\telse\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t}\r\n",
      "\t\treturn sum;\r\n",
      "\t}\r\n",
      "\tpublic static void main(String [] args) {\r\n",
      "\t\t\r\n",
      "\t\t//System.out.println(sumOfPrimes(1000000));\r\n",
      "\t\tSystem.out.println(sum_0f_primes2(1000000));\r\n",
      "\t\t\r\n",
      "\t}\r\n",
      "}\r\n"
     ]
    }
   ],
   "source": [
    "#java\n",
    "! cat Benchmarks.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "benchamrks_racket.rkt  Deque_list_queue.py\t\tprofiling.ipynb\r\n",
      "benchmarks\t       design_of_comp_programs_n.ipynb\t__pycache__\r\n",
      "Benchmarks1.ipynb      Euler.py\t\t\t\tpypy_vs_java_test.py\r\n",
      "Benchmarks2.ipynb      factorize.txt\t\t\tracket_tests.rkt\r\n",
      "Benchmarks.java        hacker_rank.ipynb\t\tracket_tests.rkt~\r\n",
      "benchmarks.py\t       millerrabin.rkt\t\t\tsmall_things.ipynb\r\n",
      "benchmarks_pypy_2.py   prime_res.txt\r\n"
     ]
    }
   ],
   "source": [
    "! ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "! javac Benchmarks.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "1 loop, best of 3: 559 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit ! java  Benchmarks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "37550402023\n",
      "1 loop, best of 3: 664 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit ! pypy pypy_vs_java_test.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting bigint_java_vs_pypy.py\n"
     ]
    }
   ],
   "source": [
    "\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now java slightly (19.1%) faster than pypy:\n",
    "1. java -> 559 ms\n",
    "2. pypy -> 672 ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "1 loop, best of 3: 1.48 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit ! pypy bigint_java_vs_pypy.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** Change algorithm to sum of the fourth powers of primes belowe 1000000(using bigint and miller rabin again):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting bigint_java_vs_pypy.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile bigint_java_vs_pypy.py\n",
    "import math\n",
    "import Euler as eu\n",
    "def is_prime(n):\n",
    "    if n == 2 or n == 3 or n == 5: return True\n",
    "    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:\n",
    "        return False\n",
    "    i = 7\n",
    "    limit = int(math.sqrt(n))\n",
    "    while i < limit + 1:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        else:\n",
    "            i += 2\n",
    "    return True\n",
    "\n",
    "def sum_of_prime_forth_powers(n):\n",
    "    sum = 0\n",
    "    i = 2\n",
    "    while i <= n:\n",
    "        if eu.miller_rabin(i):\n",
    "            sum += i *i * i * i\n",
    "            i += 1\n",
    "        else:\n",
    "            i += 1\n",
    "    return sum\n",
    "print(sum_of_prime_forth_powers(1000000))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "1 loop, best of 3: 1.51 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit ! pypy bigint_java_vs_pypy.py\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "! javac Bigint_sum.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "1 loop, best of 3: 2.49 s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit! java Bigint_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** But with bigintegers pypy is better again (over one and a half times faster).\n",
    "Java code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "import java.lang.Math.*;\r\n",
      "import java.math.BigInteger;\r\n",
      "import java.util.*;\r\n",
      "\r\n",
      "public class Bigint_sum {\r\n",
      "\r\n",
      "public static BigInteger sum_of_forth_power_primes(long n) {\r\n",
      "\t\tlong i = 2;\r\n",
      "\t\tBigInteger SUM = BigInteger.ZERO;\r\n",
      "\t\t\r\n",
      "\t\twhile (i <= n) {\r\n",
      "\t\t\tBigInteger tmp = new BigInteger(Long.toString(i));\r\n",
      "\t\t\tif (tmp.isProbablePrime(10)) {\r\n",
      "\t\t\t\t\r\n",
      "\t\t\t\tSUM = SUM.add(tmp.multiply(tmp.multiply(tmp.multiply(tmp))));\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t\t}\r\n",
      "\t\t\telse\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t}\r\n",
      "\t\treturn SUM;\r\n",
      "\t}\r\n",
      "\tpublic static void main(String [] args) {\r\n",
      "\t\t\r\n",
      "\t\t\r\n",
      "\t\tSystem.out.println(sum_of_forth_power_primes(1000000).toString());\r\n",
      "\t\t\r\n",
      "\t}\r\n",
      "}\r\n",
      "\r\n"
     ]
    }
   ],
   "source": [
    "! cat Bigint_sum.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "! javac Bigint_sum.java"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edit 2, as suggested, changed new BigInteger to BigInteger.valueOf(long arg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "import java.lang.Math.*;\r\n",
      "import java.math.BigInteger;\r\n",
      "import java.util.*;\r\n",
      "\r\n",
      "public class Bigint_sum {\r\n",
      "\r\n",
      "public static BigInteger sum_of_forth_power_primes(long n) {\r\n",
      "\t\tlong i = 2;\r\n",
      "\t\tBigInteger SUM = BigInteger.ZERO;\r\n",
      "\t\t\r\n",
      "\t\twhile (i <= n) {\r\n",
      "\t\t\tBigInteger tmp = BigInteger.valueOf(i);\r\n",
      "\t\t\tif (tmp.isProbablePrime(8)) {\r\n",
      "\t\t\t\t\r\n",
      "\t\t\t\tSUM = SUM.add(tmp.multiply(tmp.multiply(tmp.multiply(tmp))));\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t\t}\r\n",
      "\t\t\telse\r\n",
      "\t\t\t\ti += 1;\r\n",
      "\t\t}\r\n",
      "\t\treturn SUM;\r\n",
      "\t}\r\n",
      "\tpublic static void main(String [] args) {\r\n",
      "\t\t\r\n",
      "\t\t\r\n",
      "\t\tSystem.out.println(sum_of_forth_power_primes(1000000).toString());\r\n",
      "\t\t\r\n",
      "\t}\r\n",
      "}\r\n",
      "\r\n"
     ]
    }
   ],
   "source": [
    "# java code now\n",
    "! cat Bigint_sum.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "1 loop, best of 3: 1.42 s per loop\n"
     ]
    }
   ],
   "source": [
    "# recall python with JIT test...\n",
    "%timeit ! pypy bigint_java_vs_pypy.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14652318741043597759074732978\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "14652318678776560130517006257\n",
      "1 loop, best of 3: 1.93 s per loop\n"
     ]
    }
   ],
   "source": [
    "# java now...\n",
    "%timeit ! java Bigint_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#####\n",
    "#####"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this change plus lowering the precision of Miller Rabin test (to 8), java is doing slightly better.\n",
    "1. pypy -> 1.42 s\n",
    "2. java -> 1.93 s\n"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}