p1/izzivi/01 bytecode/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prva funkcija\n",
    "\n",
    "FRI ima, kot gotovo veste, pogodbe z različnimi uglednimi tujimi organizacijami (NSA, MI5, Mossad - you name it) za izvajanje občasnih del. Nekoč je ena od njih prestregla tole funkcijo v Pythonu. No, pravzaprav ne funkcije, temveč že prevedeno kodo te funkcije. Zanimalo jih je, kaj počne, kaj računa, kaj izpiše, kaj vrne (če kaj). Torej?\n",
    "\n",
    "    Eni pravijo, naj bi bil `n` menda argument funkcije. Pa še tega ne smemo pozabiti, da funkcija `print` vrne rezultat (objekt `None`).\n",
    "\n",
    "```\n",
    "  2           0 LOAD_CONST               1 (1)\n",
    "              2 DUP_TOP\n",
    "              4 STORE_FAST               1 (a)\n",
    "              6 STORE_FAST               2 (b)\n",
    "\n",
    "  3     >>    8 LOAD_FAST                0 (n)\n",
    "             10 LOAD_CONST               2 (0)\n",
    "             12 COMPARE_OP               4 (>)\n",
    "             14 POP_JUMP_IF_FALSE       48\n",
    "\n",
    "  4          16 LOAD_GLOBAL              0 (print)\n",
    "             18 LOAD_FAST                1 (a)\n",
    "             20 CALL_FUNCTION            1\n",
    "             22 POP_TOP\n",
    "\n",
    "  5          24 LOAD_FAST                2 (b)\n",
    "             26 LOAD_FAST                1 (a)\n",
    "             28 LOAD_FAST                2 (b)\n",
    "             30 BINARY_ADD\n",
    "             32 ROT_TWO\n",
    "             34 STORE_FAST               1 (a)\n",
    "             36 STORE_FAST               2 (b)\n",
    "\n",
    "  6          38 LOAD_FAST                0 (n)\n",
    "             40 LOAD_CONST               1 (1)\n",
    "             42 INPLACE_SUBTRACT\n",
    "             44 STORE_FAST               0 (n)\n",
    "             46 JUMP_ABSOLUTE            8\n",
    "        >>   48 LOAD_CONST               0 (None)\n",
    "             50 RETURN_VALUE\n",
    "```\n",
    "\n",
    "### Razkrivanje\n",
    "\n",
    "Naloga je že povedala, da gre za funkcijo z argumentom `n`. Čeprav še ne vemo, kako v Pythonu pisati funkcije (pa tudi zank pravzaprav še ne poznamo), kar napišimo\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "```\n",
    "\n",
    "Začetek je preprost: Python na sklad naloži konstanto 1, podvoji zadnji element sklada (tako da sta na skladu dve enici) in shraniti tadva elementa v `a` in `b`.\n",
    "\n",
    "```\n",
    "  2           0 LOAD_CONST               1 (1)\n",
    "              2 DUP_TOP\n",
    "              4 STORE_FAST               1 (a)\n",
    "              6 STORE_FAST               2 (b)\n",
    "```\n",
    "\n",
    "To je prevod prirejanja `a = b = 1`.\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "    a = b = 1\n",
    "```\n",
    "\n",
    "Potem pa se stvari malo zavozlajo. Točneje, zazankajo. Imamo\n",
    "\n",
    "```\n",
    "  3     >>    8 LOAD_FAST                0 (n)\n",
    "             10 LOAD_CONST               2 (0)\n",
    "             12 COMPARE_OP               4 (>)\n",
    "             14 POP_JUMP_IF_FALSE       48\n",
    "```\n",
    "\n",
    "To na sklad naloži vrednost `n` (kjer je `n` argument funkcije, saj mu očitno nihče ni priredil vrednosti) in `0`, ter ju primerja. Če ni res (`POP_JUMP_IF_FALSE`) je da `n > 0`, skoči na bajt 48. Torej nekaj preskoči. To bo najbrž `if` ali, morda, `while`. Dilemo razreši vrstica pred bajtom 48:\n",
    "\n",
    "```\n",
    "             46 JUMP_ABSOLUTE            8\n",
    "```\n",
    "\n",
    "Tu piše, da skočimo na bajt 8, torej ravno na začetek gornjega bloka. Gre torej za zanko: vse med bajtoma 8 in 46 (ali, če hočete, med 16 in 46) se ponavlja, dokler je `n > 0`. Imamo torej\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "    a = b = 1\n",
    "    while n > 0:\n",
    "```\n",
    "\n",
    "Sledi\n",
    "\n",
    "```\n",
    "  4          16 LOAD_GLOBAL              0 (print)\n",
    "             18 LOAD_FAST                1 (a)\n",
    "             20 CALL_FUNCTION            1\n",
    "             22 POP_TOP\n",
    "```\n",
    "\n",
    "To na sklad postavi funkcijo `print` in vrednost `a` ter pokliče to funkcijo (pri čemer ji pošlje en argument - to je pomen enice v `CALL_FUNCTION 1`). Vsaka funkcija v Pythonu vrne rezultat, torej ga vrne tudi `print`. Ker ga ne potrebujemo, ga vržemo stran (`POP_TOP` zavrže zadnji element sklada).\n",
    "\n",
    "Prišli smo torej do\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "    a = b = 1\n",
    "    while n > 0:\n",
    "        print(a)\n",
    "```\n",
    "\n",
    "Sledi najbolj zapletena reč.\n",
    "\n",
    "```\n",
    "  5          24 LOAD_FAST                2 (b)\n",
    "             26 LOAD_FAST                1 (a)\n",
    "             28 LOAD_FAST                2 (b)\n",
    "             30 BINARY_ADD\n",
    "             32 ROT_TWO\n",
    "             34 STORE_FAST               1 (a)\n",
    "             36 STORE_FAST               2 (b)\n",
    "```\n",
    "\n",
    "Na sklad naloži `b`, nato `a`, nato spet `b`. Sklad je torej takšen: `b a b`. Nato sešteje zadnja dva elementa; sklad bo torej `b a + b`. Nato zamenja vrstni red zadnjih dve elementov, torej imamo `a + b b`. Potem shrani zadnji element v `a`; `a` bo torej enak `b`-ju in na skladu ostane `a + b`. Tega shrani v `b`.\n",
    "\n",
    "Naivno bi torej to prepisali v \n",
    "\n",
    "```python\n",
    "a = b\n",
    "b = a + b\n",
    "```\n",
    "\n",
    "vendar gornja bajtkoda ne dela tega. V `b` se shrani vsota *prejšnjega* `a`-ja in `b`-ja, tule pa bi se v `b` v bistvu shranil `b + b`. Tisti, ki še ne znajo Pythona, bi tole lahko imitirali le s tretjo spremenljivko, recimo tako\n",
    "\n",
    "```python\n",
    "t = a + b\n",
    "a = b\n",
    "b = t\n",
    "```\n",
    "\n",
    "Kdor zna Python (in ga zna dovolj dobro), pa ve, da je možno v njem prirejati tudi sočasno,\n",
    "\n",
    "```python\n",
    "a, b = b, a + b\n",
    "```\n",
    "\n",
    "Kaj se skriva za tem in kako to v resnici deluje, bomo izvedeli prihodnji teden.\n",
    "\n",
    "\n",
    "Prišli smo torej do\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "    a = b = 1\n",
    "    while n > 0:\n",
    "        print(a)\n",
    "        a, b = b, a + b  \n",
    "```\n",
    "\n",
    "Sledi\n",
    "\n",
    "```\n",
    "  6          38 LOAD_FAST                0 (n)\n",
    "             40 LOAD_CONST               1 (1)\n",
    "             42 INPLACE_SUBTRACT\n",
    "             44 STORE_FAST               0 (n)\n",
    "```\n",
    "\n",
    "ki naloži `n` in `1`, ju odšteje in to shrani nazaj v `n`, se pravi `n = n - 1` ali `n -= 1`.\n",
    "\n",
    "```python\n",
    "def f(n):\n",
    "    a = b = 1\n",
    "    while n > 0:\n",
    "        print(a)\n",
    "        a, b = b, a + b\n",
    "        n = n - 1\n",
    "```\n",
    "\n",
    "Sledi skok, ki je del `while` zadnji dve vrstici, \n",
    "\n",
    "```\n",
    "        >>   48 LOAD_CONST               0 (None)\n",
    "             50 RETURN_VALUE\n",
    "```\n",
    "\n",
    "pa poskrbita, da funkcija vrne `None`, ker vsaka funkcija v Pythonu pač nekaj vrne. Tidve vrstici se pojavita, četudi v funkcijo ne napišemo eksplicitnega `return None`. \n",
    "\n",
    "Kaj počne funkcija, prepoznajo vsi, ki so že kdaj napisali funkcijo, ki računa Fibonacijeva števila. Računa namreč Fibonacijeva števila, zaporedje 1 1 2 3 5 8 13 21 34 55 ..., v katerem je vsak člen enak vsoti prejšnjih dveh.\n",
    "\n",
    "\n",
    "## Druga funkcija\n",
    "\n",
    "Če ste, draga študentka ali študent, potencialni kandidat za občasna pogodbena dela na FRI, se boste morali izkazati še z nekoliko težjo funkcijo. Kaj izračuna in vrne tale?\n",
    "\n",
    "    Videti je, da naj bi bila `n` in `x` argumenta funkcije, saj jima nihče ne prireja vrednosti. `r` pa je, bi rekel, neka spremenljivka znotraj funkcije. Vsaj meni tako izgleda.\n",
    "\n",
    "```\n",
    "  2           0 LOAD_CONST               1 (1)\n",
    "              2 STORE_FAST               2 (r)\n",
    "\n",
    "  3     >>    4 LOAD_FAST                1 (n)\n",
    "              6 LOAD_CONST               2 (0)\n",
    "              8 COMPARE_OP               4 (>)\n",
    "             10 POP_JUMP_IF_FALSE       50\n",
    "\n",
    "  4          12 LOAD_FAST                1 (n)\n",
    "             14 LOAD_CONST               3 (2)\n",
    "             16 BINARY_MODULO\n",
    "             18 LOAD_CONST               1 (1)\n",
    "             20 COMPARE_OP               2 (==)\n",
    "             22 POP_JUMP_IF_FALSE       32\n",
    "\n",
    "  5          24 LOAD_FAST                2 (r)\n",
    "             26 LOAD_FAST                0 (x)\n",
    "             28 BINARY_MULTIPLY\n",
    "             30 STORE_FAST               2 (r)\n",
    "\n",
    "  6     >>   32 LOAD_FAST                0 (x)\n",
    "             34 LOAD_FAST                0 (x)\n",
    "             36 BINARY_MULTIPLY\n",
    "             38 STORE_FAST               0 (x)\n",
    "\n",
    "  7          40 LOAD_FAST                1 (n)\n",
    "             42 LOAD_CONST               3 (2)\n",
    "             44 BINARY_FLOOR_DIVIDE\n",
    "             46 STORE_FAST               1 (n)\n",
    "             48 JUMP_ABSOLUTE            4\n",
    "\n",
    "  8     >>   50 LOAD_FAST                2 (r)\n",
    "             52 RETURN_VALUE\n",
    "```\n",
    "\n",
    "### Razvozlavanje\n",
    "\n",
    "En kos hitro prepoznamo. Začetnemu prirejanju, `r = 1` sledi zanka `while n > 0`, tako kot v prejšnjem programu. Imamo torej\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "```\n",
    "\n",
    "Sledi\n",
    "\n",
    "```\n",
    "  4          12 LOAD_FAST                1 (n)\n",
    "             14 LOAD_CONST               3 (2)\n",
    "             16 BINARY_MODULO\n",
    "             18 LOAD_CONST               1 (1)\n",
    "             20 COMPARE_OP               2 (==)\n",
    "             22 POP_JUMP_IF_FALSE       32\n",
    "```\n",
    "\n",
    "Na sklad naloži `n` in `2`, izračuna ostanek po deljenju z 2 (po čemer na skladu ostane ta ostanek); na sklad naloži 1 in primerja, če sta enaka. Z drugimi besedami, preveri, ali velja `n % 2 == 1`. Če to ni res, skoči na bajt 40. Tu bi lahko spet šlo za `while`, vendar imamo tokrat `if`, kar vidimo po tem, da v bajtu 40 oziroma tik pred njim ni nobenega skoka nazaj. Tale `POP_JUMP_IF_FALSE` samo preskoči naslednji blokec, naslednjo vrstico programa.\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "```\n",
    "\n",
    "Ta naslednja vrstica, se je prevedla v\n",
    "\n",
    "```\n",
    "  5          24 LOAD_FAST                2 (r)\n",
    "             26 LOAD_FAST                0 (x)\n",
    "             28 BINARY_MULTIPLY\n",
    "             30 STORE_FAST               2 (r)\n",
    "```\n",
    "\n",
    "in zdaj to menda že znamo prebrati: naloži `r` in `x`, ju zmnoži in rezultati shrani nazaj v `r`, torej\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r = r * x\n",
    "```\n",
    "\n",
    "Nato - in to je že izven `if`-a, saj je skok `POP_JUMP_IF_FALSE` skočil natančno sem - se zgodi\n",
    "\n",
    "```\n",
    "  6     >>   32 LOAD_FAST                0 (x)\n",
    "             34 LOAD_FAST                0 (x)\n",
    "             36 BINARY_MULTIPLY\n",
    "             38 STORE_FAST               0 (x)\n",
    "```\n",
    "\n",
    "kar je `x = x * x`,\n",
    "\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r = r * x\n",
    "        x = x * x\n",
    "```\n",
    "\n",
    "Sledi\n",
    "\n",
    "```\n",
    "  7          40 LOAD_FAST                1 (n)\n",
    "             42 LOAD_CONST               3 (2)\n",
    "             44 BINARY_FLOOR_DIVIDE\n",
    "             46 STORE_FAST               1 (n)\n",
    "```\n",
    "\n",
    "To naloži na sklad `n` in `2`, ju celoštevilsko deli in rezultat shrani nazaj v `n`, se pravi\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r = r * x\n",
    "        x = x * x\n",
    "        n = n // 2\n",
    "```\n",
    "\n",
    "Nato imamo skok, ki zaključi zanko. Sledi ji le še\n",
    "\n",
    "```\n",
    "  8     >>   50 LOAD_FAST                2 (r)\n",
    "             52 RETURN_VALUE\n",
    "```\n",
    "\n",
    "Naložimo vrednost `r` in jo vrnemo. Celotna funkcija je torej\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r = r * x\n",
    "        x = x * x\n",
    "        n = n // 2\n",
    "    return r\n",
    "```\n",
    "\n",
    "ali, če imamo raje inkrementalne operatorje\n",
    "\n",
    "```python\n",
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r *= x\n",
    "        x *= x\n",
    "        n //= 2\n",
    "    return r\n",
    "```\n",
    "\n",
    "### Kaj počne ta funkcija?\n",
    "\n",
    "Tole je pomembna funkcija. Uporabljamo jo stalno, ne da bi vedeli, da jo. Za začetek jo preskusimo s par argumenti in poskusimo uganiti, kar pravzaprav računa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r *= x\n",
    "        x *= x\n",
    "        n //= 2\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(2, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(10, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000000"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(10, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stvar je očitna: funkcija vrne $x^n$, pri čemer mora biti `n` celo število (ker celoštevilsko deljenje in tako naprej).\n",
    "\n",
    "Funkcije, ki izračuna $x^n$, ni težko napisati niti, če je `while` edina zanka, za katero vemo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n):\n",
    "    i = 0\n",
    "    r = 1\n",
    "    while i < n:\n",
    "        r *= x\n",
    "        i += 1\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ali, če hočemo z zanko `for`, ki je še ne poznamo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n):\n",
    "    r = 1\n",
    "    for i in range(n):\n",
    "        r *= x\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To deluje čisto dobro, dokler je $n$ majhen. Če je $n$ enak, recimo, `18446744073709551557`, pa bo računanje $x^n$ se pravi $x^{18446744073709551557}$ trajalo kar dolgo, saj imamo zanko, ki se mora obrniti 18446744073709551557-krat. In to je pravzaprav sorazmerno majhen $n$ (tole je, mimogrede, največje 64-bitno praštevilo). V praksi pogosto računamo potence s 1024-bitnim eksponentom, torej potence s skoraj tako velikim eksponentom, kot je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 ** 1024"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ko bi pognali `for i in range(179769313486231590772930519078902473361797697894230657273430081157732675805500963132708\n",
    "47732240753602112011387987139335765878976881441662249284743063947412437776789342486548527630221960124\n",
    "60941194530829520850057688381506823424628814739131105408272371633505106845862982399472459384797163048\n",
    "35356329624224137216)` bi čakali in čakali in potem bi se naveličali čakati, in potem bi vesolje čakalo in čakalo in se naveličalo čakati in se končalo, kakorkoli se že ima namen končati ... zanka pa bi tekla še naprej.\n",
    "\n",
    "Očitno potrebujemo hitrejši način za računanje takšnih gromozanski potenc. Preden ga spoznamo, pa moramo razčistiti dvoje."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Zakaj potrebujemo take ogromne potence?\n",
    "2. Če je to samo eksponent in torej računamo, na primer $2^{179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216}$ - mar ni to število preveliko, da bi ga shranili v pomnilnik?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najprej odgovorimo na drugo vprašanje: da to število ima 17976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753\n",
    "60211201138798713933576587897688144166224928474306394741243777678934248654852763022196012460941194\n",
    "53082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356\n",
    "329624224137216 bitov in je preveliko, da bi ga shranili v vesolje, ne samo v pomnilnik. Vesolje ima namreč samo kakšnih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000000000000000000000000000000000000000000000000000000000000000000000000"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "10 ** 72"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "atomov.\n",
    "\n",
    "Odgovor na drugo vprašanje je: na srečo nas ne zanima to število, temveč ostanek po deljenju tega števila z nekim številom. Ta ostanek je pač samo toliko veliko kot to, drugo število. Recimo, da imam"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 35278642930487629358673498762938467\n",
    "n = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216\n",
    "m = 98367923874693874632559284619834677"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "in matra me firbec, da bi izvedel, koliko je `x ** n % m`. Vtipkati to v Python je slaba ideja, saj bo potenciral in dobil preveliko število, še preden se loti računanja ostanka. Pač pa lahko vpišemo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22872358624663969387800566354005582"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(x, n, m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če sem na prvem predavanju omenil, da ima `pow` skrite supermoči: no, to. Izračunati zna ostanek po potenciranju, pri čemer se ne ustraši astronomsko velikih števil.\n",
    "\n",
    "Preden ugotovimo, kako ta `pow` deluje (spoiler: tako kot skrita funkcija!), odgovorimo na prvo vprašanje: zakaj bi to potrebovali? Takšne potence - pri čemer je eksponent neko veliko praštevilo - so osnova več postopkov kriptografije. Tako deluje izmenjava ključev z RSA, z Diffie-Helmanovim postopkom... Vsakič, ko gre brskalnik na stran, ki podpira https (to je, dandanes: vsakič, ko gre na kakšno stran), se poračuna ena takšna potenca.\n",
    "\n",
    "Zdaj pa k delovanju `pow`. Začeli bomo z (zeh, zeh) pretvarjanjem v dvojiški zapis. Imamo neko število, recimo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "38"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(\"100110\", 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "38 (za katerega sem mimogrede izdal, da se po dvojiško zapiše `100110`), bi rad zapisal po dvojiško. Poznamo dril: ker je število sodo, zadnja števka 0. Nato ga delimo z `2` in dobimo 19 (oziroma `10011` - število v dvojiškem zapisu delimo z 2 tako, da odbijemo zadnjo števko). Ker je 19 liho, je zadnja števka 1. Spet delimo z 2 in dobimo 9 (oziroma, brez zadnje števka, `1001`). 9 je liho, torej je zadnja števka 1. Delimo z 2 in imamo 4 ali `100`. OK, sprogramirajmo to reč."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            print(1)\n",
    "        else:\n",
    "            print(0)\n",
    "        n //= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "1\n",
      "0\n",
      "0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "f(38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj pa mimogrede izpisujmo še dvojiške števke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    b = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            print(b, 1)\n",
    "        else:\n",
    "            print(b, 0)\n",
    "        b *= 2\n",
    "        n //= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0\n",
      "2 1\n",
      "4 1\n",
      "8 0\n",
      "16 0\n",
      "32 1\n"
     ]
    }
   ],
   "source": [
    "f(38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj pa ne izpisujmo tistih ničel; pravzaprav izpisujmo samo števke, ki jih imamo pri enicah."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    b = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            print(b)\n",
    "        b *= 2\n",
    "        n //= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "32\n"
     ]
    }
   ],
   "source": [
    "f(38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Izpisalo se je 2, 4 in 32, kar je ravno prav, saj je 2 + 4 + 32 = 38.\n",
    "\n",
    "Pa recimo, da bi morali izračunati, koliko je $5^{38}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "363797880709171295166015625"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 ** 38"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Počasi: $5^{38} = 5^{2 + 4 + 32} = 5^2 \\times 5^4 \\times 5^{32}$. To bi se dalo sprogramirati tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n):\n",
    "    b = 1\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r *= x ** b\n",
    "        b *= 2\n",
    "        n //= 2\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "363797880709171295166015625"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5, 38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da, številka je ista, torej funkcija deluje. Ampak lahko smo še pametnejši. Pravzaprav moramo biti: v funkciji še vedno uporabljamo potenciranje `x ** b`, kar je pravzaprav goljufija. Tega `x ** b` se moramo znebiti.\n",
    "\n",
    "Poglejmo, kakšne potence uporabljamo: ko je `b` enak `1`, množimo (ali pa tudi ne) z $x$, nato je `b` enak `2` in morda množimo z $x^2$, nato je `b` enak `4` in morda množimo z $x^4$, nato z $x^8$, nato z $x^{16}$, $x^32$. Kako dobimo takšno zaporedje x-ov? S kvadriranjem! $x^8$ je ravno $x^{4+4}$ oziroma $x^4\\times x^4$ oziroma ${x^4}^2$. Vsak naslednji $x$ dobimo s kvadriranjem prejšnjega $x$-a.\n",
    "\n",
    "Ukinemo torej `b`. Namesto z `x ** b` množimo kar z `x` in potem namesto, da bi podvojili `b`, pokvadriramo `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r *= x\n",
    "        x *= x\n",
    "        n //= 2\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "363797880709171295166015625"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5, 38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In to je natančno funkcija iz uganke!\n",
    "\n",
    "Kako hitra je ta funkcija? Še vedno imamo zanko. Vendar se je ona, naivna zanka prejšnje funkcija obrnila tolikokrat, kolikor je bil velik eksponent. Tale pa eksponent v vsakem koraku deli z 2 in se ustavi, ko je eksponent enak 0. Ker deljenje z 2 v bistvu pomeni odbijanje zadnjega bita, se ta zanka obrne tolikokrat, kolikor bitov je velik eksponent. Če imamo 1024 bitni eksponent, se zanka obrne 1024-krat.\n",
    "\n",
    "Samo še nekaj nam manjka: kako je s tistim ostankom? Vemo, da ne smemo najprej potencirati in šele nato računati ostanka.\n",
    "\n",
    "To je pa preprosto: ker gre za sama množenja, lahko ostanke računamo kar sproti: ob vsakem množenju obdržimo le ostanek."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, n, m):\n",
    "    r = 1\n",
    "    while n > 0:\n",
    "        if n % 2 == 1:\n",
    "            r = (r * x) % m\n",
    "        x = (x * x) % m\n",
    "        n //= 2\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22872358624663969387800566354005582"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(x, n, m)"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}