day 10 - karatsuba multiplication.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import zip_longest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def add(x, y):\n",
    "    z, carry = [], 0\n",
    "\n",
    "    for r, s in zip_longest(x, y, fillvalue=0):\n",
    "        t = r + s + carry\n",
    "        carry = t // 10\n",
    "        z.append(t % 10)\n",
    "    if carry:\n",
    "        z.append(carry)\n",
    "\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sub(x, y):\n",
    "    z, carry = [], 0\n",
    "\n",
    "    for r, s in zip_longest(x, y, fillvalue=0):\n",
    "        t = r - s + carry\n",
    "        carry = t // 10\n",
    "        z.append(t % 10)\n",
    "\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def karatsuba(x, y):\n",
    "    # ensure same length\n",
    "    while len(x) < len(y):\n",
    "        x.append(0)\n",
    "    while len(x) > len(y):\n",
    "        y.append(0)\n",
    "\n",
    "    # length and split\n",
    "    n = len(x)\n",
    "    n_2 = (n + 1) >> 1\n",
    "\n",
    "    # trivial case\n",
    "    if n == 1:\n",
    "        return add([x[0] * y[0]], [])\n",
    "\n",
    "    # split\n",
    "    x0, x1 = x[:n_2], x[n_2:]\n",
    "    y0, y1 = y[:n_2], y[n_2:]\n",
    "\n",
    "    # karatsuba algorithm\n",
    "    z0 = karatsuba(x0, y0)\n",
    "    z1 = karatsuba(x1, y1)\n",
    "    z2 = karatsuba(add(x0, x1), add(y0, y1))\n",
    "    z2 = sub(sub(z2, z0), z1)\n",
    "\n",
    "    z = add(z0, [0] * (n_2 << 1) + z1)\n",
    "    z = add(z, [0] * n_2 + z2)\n",
    "\n",
    "    return z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mult(x, y):\n",
    "    print(x, '*', y, '=', int(x) * int(y), end=' = ')\n",
    "\n",
    "    x = list(map(int, reversed(x)))\n",
    "    y = list(map(int, reversed(y)))\n",
    "    z = karatsuba(x, y)\n",
    "\n",
    "    print(''.join(map(str, reversed(z))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1234 * 4321 = 5332114 = 5332114\n"
     ]
    }
   ],
   "source": [
    "mult('1234', '4321')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5678 * 8765 = 49767670 = 49767670\n"
     ]
    }
   ],
   "source": [
    "mult('5678', '8765')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9999 * 9999 = 99980001 = 99980001\n"
     ]
    }
   ],
   "source": [
    "mult('9999', '9999')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "60504 * 36056 = 2181532224 = 2181532224\n",
      "7644 * 2034 = 15547896 = 15547896\n",
      "2 * 1 = 2 = 2\n",
      "939 * 700 = 657300 = 657300\n",
      "977707258 * 389036934 = 380364234001866972 = 380364234001866972\n",
      "1079459668 * 7762768164 = 8379595145072409552 = 08379595145072409552\n",
      "4609807 * 2350979 = 10837559451053 = 10837559451053\n",
      "36740 * 97490 = 3581782600 = 3581782600\n",
      "29 * 19 = 551 = 0551\n",
      "913789 * 733694 = 670441506566 = 670441506566\n",
      "476646777 * 451303071 = 215112154242352167 = 215112154242352167\n",
      "23369 * 43069 = 1006479461 = 1006479461\n",
      "9185982 * 3983922 = 36596235781404 = 036596235781404\n",
      "7806584211 * 8415537629 = 65696603181627775719 = 65696603181627775719\n",
      "317 * 106 = 33602 = 33602\n",
      "507729648 * 898501571 = 456195886371277008 = 456195886371277008\n",
      "780843 * 778950 = 608237654850 = 608237654850\n",
      "61 * 79 = 4819 = 4819\n",
      "310094 * 443993 = 137679565342 = 137679565342\n",
      "1564 * 7634 = 11939576 = 11939576\n",
      "746602083 * 909270015 = 678862887208441245 = 678862887208441245\n",
      "2 * 6 = 12 = 12\n",
      "1798067708 * 3523547357 = 6335576720230447756 = 06335576720230447756\n",
      "7 * 0 = 0 = 0\n",
      "6290 * 0797 = 5013130 = 5013130\n",
      "9958199 * 6994130 = 69648938371870 = 069648938371870\n",
      "1661 * 0701 = 1164361 = 1164361\n",
      "022046 * 410144 = 9042034624 = 09042034624\n",
      "8505673479 * 1870256036 = 15907787164344869244 = 15907787164344869244\n",
      "5 * 2 = 10 = 10\n"
     ]
    }
   ],
   "source": [
    "for _ in range(30):\n",
    "    n = np.random.randint(1, 11)\n",
    "    x = ''.join(map(str, np.random.randint(0, 10, n)))\n",
    "    y = ''.join(map(str, np.random.randint(0, 10, n)))\n",
    "    mult(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}