GreatestCommonDivisor.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to find a the largest number in an unsorted list(array)?\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67\n"
     ]
    }
   ],
   "source": [
    "mylist = [1,4,67,2,7,2]\n",
    "print(max(mylist))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lets implement our naive max algorithm\n",
    "# or as they call it Brute Force\n",
    "def find_my_max(seq):\n",
    "    my_max = None\n",
    "    for n in seq:\n",
    "        if my_max == None or n > my_max:\n",
    "            my_max = n\n",
    "    return my_max\n",
    "    # set max to negative infinitty\n",
    "    # loop through seq\n",
    "    # if any number is larger than max we set max to this number\n",
    "    # return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67\n"
     ]
    }
   ],
   "source": [
    "print(find_my_max(mylist))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23\n"
     ]
    }
   ],
   "source": [
    "print(find_my_max([-4,23,-6,2,0,0,5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000000"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "big_list = [random.randint(1,100_000_000) for _ in range(1_000_000)]\n",
    "len(big_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17.2 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "max(big_list) # most likely this is already cached so running it 1000 times will not prove nothing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "97.5 ms ± 13.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "find_my_max(big_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "huge_list = [random.randint(1,1_000_000_000) for _ in range(10_000_000)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "174 ms ± 2.95 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "max(huge_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "926 ms ± 31.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "find_my_max(huge_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "959 ms ± 69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "find_my_max(huge_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted_big_list = sorted(big_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67.5 ms ± 463 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "max(sorted_big_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67.3 ms ± 1.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "min(sorted_big_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(178, 99999962)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted_big_list[0], sorted_big_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " True,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " True,\n",
       " True,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False,\n",
       " False]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How about finding some value in a list\n",
    "over_9000 = [n in big_list for n in range(9000,9200)]\n",
    "over_9000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "True in over_9000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "over_9000.index(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.1 ms ± 116 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "9021 in big_list # so this check took a while"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.82 µs ± 12.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "9021 in sorted_big_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(648803, 82)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "big_list.index(9021),sorted_big_list.index(9021)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "big_set = set(big_list) # another data structure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "104 ns ± 4.52 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "9021 in big_set\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Key takeaway - choosing a right data structure can be crucial\n",
    "# in set is O(1)\n",
    "# in list is O(n) - on average, sometimes the value is found quickly sometimes you have to go through whole list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20.8 ms ± 782 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "9000 in big_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "90.3 ns ± 10.2 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "9000 in big_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11.2 ms ± 86.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "count = 100_000\n",
    "nums = [] # lets image we do not know about list comprehension\n",
    "for n in range(count):\n",
    "    nums.append(n)\n",
    "nums.reverse() # in place number reversal\n",
    "# of course list(range(count))\n",
    "# nums[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# can we try to do better ? why reverse if we could already make reverse immediate...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.78 s ± 9.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "count = 100_000\n",
    "nums2 = []\n",
    "for n in range(count):\n",
    "    nums2.insert(0, n)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([999999, 999998, 999997, 999996, 999995], [99999, 99998, 99997, 99996, 99995])"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums[:5],nums2[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What is GCD?\n",
    "## the largest number that divides two numbers evenly (no reminder)\n",
    "## 12 8 will have GCD of 4, and 21, 18, will have GCD of 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# one algorithm to solve would be this\n",
    "* divide numbers in prime factors\n",
    "* GCD will be the common prime factors in both numbers multiplied"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# GCD or 30 and 12 would be 6 because:\n",
    "# 30 = 2*3*5\n",
    "# 12 = 2*2*3\n",
    "# so GCD is 2*3\n",
    "# the only catch being that you have to find prime factors for a number\n",
    "# well"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "# if we did not know about Euclid\n",
    "# brute force algorithm\n",
    "def naiveGCD(x, y):\n",
    "    gcd = 1 # so 1 will always be a fallback GCD\n",
    "    for n in range(2, min(x,y)+1): # also those off by one errors you have to watch out\n",
    "        if x%n == 0 and y%n ==0:\n",
    "            gcd = n # wow we got a new high gcd\n",
    "    return gcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "naiveGCD(12,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "naiveGCD(30,12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "97.7 ms ± 3.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "naiveGCD(10_000_200,900_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This 2000 years old algorithm\n",
    "# https://en.wikipedia.org/wiki/Euclidean_algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(x, y):\n",
    "    while(y):\n",
    "        x, y = y, x % y # calculate the reminder and then swap the values, in other languages you'd use a temp variable\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "600"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(10_000_200,900_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "927 ns ± 57.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "gcd(10_000_200,900_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(12, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(21,18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(100, 93)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(10, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(24,12)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}