{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Vamos a seguir con nuestra serie sobre '**p**ython, **f**uente de **s**abiduria' hablando sobre la multiplicaci\u00f3n. \n", "\n", "\u00bfTe has preguntado alguna vez c\u00f3mo se multiplican dos n\u00fameros en un ordenador o calculadora? Normalmente, los [circuitos](http://en.wikipedia.org/wiki/Arithmetic_logic_unit) de los procesadores incluyen operaciones b\u00e1sicas como la [multiplicaci\u00f3n de enteros de tama\u00f1o peque\u00f1o](http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add). Sobre estas operaciones b\u00e1sicas se construye todo lo dem\u00e1s.\n", "\n", "El caso que nos ocupa hoy, multiplicar n\u00fameros enteros muy grandes, se consigue mediante el uso de algoritmos v\u00eda software. Una forma sencilla de calcular enteros es usando la misma metodolog\u00eda que us\u00e1bamos en la escuela, con la tabla de multiplicar del uno al diez y con sumas:\n", "\n", " 23958233\n", " 5830 \u00d7\n", " ------------\n", " 00000000 ( = 23,958,233 \u00d7 0)\n", " 71874699 ( = 23,958,233 \u00d7 30)\n", " 191665864 ( = 23,958,233 \u00d7 800)\n", " 119791165 ( = 23,958,233 \u00d7 5,000)\n", " ------------\n", " 139676498390 ( = 139,676,498,390 )\n", "\n", "(ejemplo extra\u00eddo de [wikipedia](http://en.wikipedia.org/wiki/Multiplication_algorithm#Example))\n", "\n", "El algoritmo que hace uso de esa metodolog\u00eda se suele llamar `long`, `grade-school`, `na\u00efve`,..., multiplication. En este caso vamos a hacer una implementaci\u00f3n *sucia* de este algoritmo descomponiendo el 'multiplicador' en d\u00edgitos que multiplicaremos al 'multiplicando':" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def naive(x, y):\n", " total = 0\n", " yy = [int(i) for i in str(y)]\n", " for i, yyy in enumerate(yy[::-1]):\n", " total += x * yyy * (10 ** i)\n", " return total" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Para el ejemplo anterior (multiplicando = 23958233 y multiplicador = 5830) lo que estariamos haciendo ser\u00eda lo siguiente:\n", "\n", " * el multiplicador lo descomponemos en una lista de los d\u00edgitos que lo componen, [5, 8, 3, 0]\n", " * el 0 lo multiplicamos por el multiplicando\n", " * el 3 lo multiplicamos por 10 y por el multiplicando y lo sumamos al resultado del paso anterior\n", " * el 8 lo multiplicamos por 100 y por el multiplicando y lo sumamos al resultado del paso anterior\n", " * el 5 lo multiplicamos por 1000 y por el multiplicando y lo sumamos al resultado del paso anterior\n", " * devolvemos el resultado final" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Esta es una forma de hacer multiplicaciones pero cuando los n\u00fameros involucrados en la multiplicaci\u00f3n son muy grandes podemos encontrarnos con problemas de rendimiento y perder mucho tiempo haciendo un c\u00e1lculo.\n", "\n", "Como en el desarrollo de Python hay gente muy inteligente, si buceas por el [c\u00f3digo fuente de Python](http://hg.python.org/cpython/file/tip/Objects/longobject.c) ver\u00e1s que para multiplicaci\u00f3n de `long`'s se usa el algoritmo de la multiplicaci\u00f3n r\u00e1pida de Karatsuba. \u00bfY qui\u00e9n demonios es este japon\u00e9s? Pues este japon\u00e9s [es un ruso al que, con 23 a\u00f1itos (en 1960), se le ocurri\u00f3 llevar la contraria al mism\u00edsimo Kolmogorov](http://en.wikipedia.org/wiki/Karatsuba_algorithm).\n", "\n", "Lo mejor es que le ech\u00e9is un ojo a la siguiente [entrada](http://www.stoimen.com/blog/2012/05/15/computer-algorithms-karatsuba-fast-multiplication/) (o en la [Wikipedia en espa\u00f1ol](http://es.wikipedia.org/wiki/Algoritmo_de_Karatsuba)) para entender m\u00e1s claramente el funcionamiento ([DRY](http://en.wikipedia.org/wiki/Don%27t_repeat_yourself)). B\u00e1sicamente, de lo que se trata es de minimizar el n\u00famero de multiplicaciones (aunque no siempre se consigue) usando una estrategia de 'divide y vencer\u00e1s'.\n", "\n", "A continuaci\u00f3n os dejo una implementaci\u00f3n muy compacta que he encontrado en [project nayuki](http://nayuki.eigenstate.org/page/karatsuba-multiplication) (si no entend\u00e9is algo del c\u00f3digo preguntad en los comentarios):" ] }, { "cell_type": "code", "collapsed": false, "input": [ "## http://nayuki.eigenstate.org/res/karatsuba-multiplication/karatsuba.py\n", "## http://nayuki.eigenstate.org/page/karatsuba-multiplication\n", "\n", "_CUTOFF = 1024\n", "\n", "def kara(x, y):\n", " if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF: # Base case\n", " #print('naive')\n", " return naive(x, y)\n", " else:\n", " #print('karatsuba')\n", " n = max(x.bit_length(), y.bit_length())\n", " half = (n + 32) // 64 * 32\n", " mask = (1 << half) - 1\n", " xlow = x & mask\n", " ylow = y & mask\n", " xhigh = x >> half\n", " yhigh = y >> half\n", " \n", " a = kara(xhigh, yhigh)\n", " b = kara(xlow + xhigh, ylow + yhigh)\n", " c = kara(xlow, ylow)\n", " d = b - a - c\n", " return (((a << half) + d) << half) + c" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bien, pues vamos a ver si esto es capar de optimizar mi funci\u00f3n `naive`. Para ello vamos a multiplicar el siguiente n\u00famero (tened cuidado si vuestro ordenador no es muy potente ya que el c\u00e1lculo se puede llegar a alargar):" ] }, { "cell_type": "code", "collapsed": false, "input": [ "num = 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890*(10**14000)\n", "#print(num.bit_length())\n", "print(num)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n" ] } ], "prompt_number": 3 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Usando la funci\u00f3n `naive`." ] }, { "cell_type": "code", "collapsed": false, "input": [ "a = naive(num, num)\n", "%timeit naive(num, num)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "1 loops, best of 3: 1.31 s per loop\n" ] } ], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Usando la funci\u00f3n `kara`" ] }, { "cell_type": "code", "collapsed": false, "input": [ "b = kara(num, num)\n", "%timeit kara(num, num)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "10 loops, best of 3: 172 ms per loop\n" ] } ], "prompt_number": 5 }, { "cell_type": "code", "collapsed": false, "input": [ "print(a == b)\n", "print(1.31 / 0.173)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "True\n", "7.572254335260117\n" ] } ], "prompt_number": 6 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vemos que hemos conseguido una ganancia de 7.5x!!!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Aunque si comprobamos como lo hace Python vemos que no hemos hecho una gran optimizaci\u00f3n (aunque no era lo importante de esta entrada):" ] }, { "cell_type": "code", "collapsed": false, "input": [ "%timeit num * num" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "1000 loops, best of 3: 455 \u00b5s per loop\n" ] } ], "prompt_number": 7 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Parece que solo es alrededor de 375 veces m\u00e1s r\u00e1pido ;-)\n", "\n", "Este c\u00f3digo lo he probado en Python 3.3, si veis alguna errata o alguna barbaridad que haya podido decir, por favor, av\u00edsadme.\n", "\n", "Esta entrada la puedes descargar en formato notebook desde [nuestro repositorio en github](https://github.com/Pybonacci/notebooks).\n", "\n", "P.D.: Pretend\u00eda que esta entrada fuera m\u00e1s rigurosa y completa pero mi tiempo se ha visto disminuido de forma dr\u00e1stica \u00faltimamente. La familia manda :-)" ] } ], "metadata": {} } ] }