Метод Карацуби.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# stores ad+bc occurences\n",
    "saves = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# decorator for caching\n",
    "def memoize(f):\n",
    "    cache = {}\n",
    "    def wrapper(a, b):\n",
    "        if a > b:\n",
    "            a, b = b, a\n",
    "        if str((a, b)) not in cache:\n",
    "            cache[str((a, b))] = f(a, b)\n",
    "        return cache[str((a, b))]\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# used for ab+cd occurences\n",
    "def save(i):\n",
    "    global saves\n",
    "    if not i in saves:\n",
    "        saves[i] = 0\n",
    "    saves[i] += 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# decorator for transforming values to strings\n",
    "def to_str(f):\n",
    "    def wrapper(x, y):\n",
    "        return f(str(x), str(y))\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# decorator for passing aligned strings\n",
    "def align(f):\n",
    "    @to_str\n",
    "    def wrapper(x, y):\n",
    "        x_l = len(x)\n",
    "        y_l = len(y)\n",
    "        if(max(x_l, y_l) != 1):\n",
    "            mask = ((max(x_l, y_l) + 1) // 2 * 2) * \"0\"\n",
    "            x, y = (mask[:-x_l] + str(x), mask[:-y_l] + str(y))\n",
    "        return f(x, y)\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@memoize\n",
    "@align\n",
    "def karazuba(x_s, y_s):\n",
    "    n = len(x_s)\n",
    "    if(max(len(str(int(x_s))), len(str(int(y_s)))) == 1): return int(x_s) * int(y_s)\n",
    "    split = lambda num_s: (int(num_s[:n//2]), int(num_s[n//2:]))\n",
    "    a, b = split(x_s)\n",
    "    c, d = split(y_s)\n",
    "    return 10 ** n * karazuba(a, c) + 10 ** (n // 2) * save(karazuba(a + b, c + d) - karazuba(a, c) - karazuba(b, d)) + karazuba(b, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "612034229974193771933365616245752393583275"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 79623957692385689235\n",
    "y = 7686558765876587657865\n",
    "karazuba(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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}