Algoritmo de multiplicación

Este ejemplo utiliza la multiplicación larga para multiplicar 23.958.233 (multiplicando) por 5.830 (multiplicador) y llega a 139.676.498.390 como resultado (producto).

 23958233 × 5830 ——————————————— 00000000 ( = 23.958.233 × 0) 71874699 ( = 23.958.233 × 30) 191665864 ( = 23.958.233 × 800) + 119791165 ( = 23.958.233 × 5.000) ——————————————— 139676498390 ( = 139.676.498.390)

23958233 · 5830 ——————————————— 119791165 191665864 71874699 00000000 ——————————————— 139676498390

multiplicar ( a [ 1 .. p ] , b [ 1 .. q ] , base ) // Operandos que contienen los dígitos más a la derecha en el índice 1producto = [ 1 .. p + q ] // Asignar espacio para el resultadopara b_i = 1 a q // para todos los dígitos en bacarreo = 0para a_i = 1 a p // para todos los dígitos en aproducto [ a_i + b_i - 1 ] += acarreo + a [ a_i ] * b [ b_i ]acarreo = producto [ a_i + b_i - 1 ] / baseproducto [ a_i + b_i - 1 ] = producto [ a_i + b_i - 1 ] mod baseproducto [ b_i + p ] = acarreo // el último dígito proviene del acarreo finalproducto de devolución

Algunos chips implementan la multiplicación larga, ya sea en hardware o en microcódigo , para diversos tamaños de palabra de enteros y coma flotante. En aritmética de precisión arbitraria , es común usar la multiplicación larga con la base establecida en ^2w , donde w es el número de bits en una palabra, para multiplicar números relativamente pequeños. Para multiplicar dos números de n dígitos usando este método, se necesitan aproximadamente n² operaciones. De manera más formal, multiplicar dos números ^de n dígitos usando la multiplicación larga requiere Θ ( n² ) operaciones ^de un solo dígito (sumas y multiplicaciones).

Cuando se implementan en software, los algoritmos de multiplicación largos deben manejar el desbordamiento durante las sumas, lo cual puede ser costoso. Una solución típica es representar el número en una base pequeña, b , de modo que, por ejemplo, 8 b sea un entero representable por la máquina. De esta manera, se pueden realizar varias sumas antes de que ocurra un desbordamiento. Cuando el número se vuelve demasiado grande, se agrega una parte al resultado, o se realiza un acarreo y se asigna la parte restante a un número menor que b . Este proceso se denomina normalización . Richard Brent utilizó este enfoque en su paquete de Fortran, MP. ^{[ 2 ]}

Inicialmente, las computadoras utilizaban un algoritmo muy similar a la multiplicación larga en base 2, pero los procesadores modernos han optimizado los circuitos para multiplicaciones rápidas mediante algoritmos más eficientes, a costa de una implementación de hardware más compleja. En base dos, la multiplicación larga a veces se denomina "desplazamiento y suma" , porque el algoritmo se simplifica y consiste simplemente en desplazar a la izquierda (multiplicar por potencias de dos) y sumar. La mayoría de los microprocesadores disponibles actualmente implementan este u otros algoritmos similares (como la codificación Booth ) para diversos tamaños de enteros y coma flotante en multiplicadores de hardware o en microcódigo .

En los procesadores actuales, una instrucción de desplazamiento de bits suele ser (aunque no siempre) más rápida que una instrucción de multiplicación y puede utilizarse para multiplicar (desplazamiento a la izquierda) y dividir (desplazamiento a la derecha) por potencias de dos. La multiplicación y la división por una constante pueden implementarse mediante una secuencia de desplazamientos y sumas o restas. Por ejemplo, existen varias maneras de multiplicar por 10 utilizando únicamente desplazamiento de bits y suma.

(( x << 2 ) + x ) << 1 # Aquí 10*x se calcula como (x*2^2 + x)*2 ( x << 3 ) + ( x << 1 ) # Aquí 10*x se calcula como x*2^3 + x*2

En algunos casos, tales secuencias de desplazamientos y sumas o restas superarán a los multiplicadores de hardware y especialmente a los divisores. Una división por un número de la forma${\displaystyle 2^{n}}$o${\displaystyle 2^{n}\pm 1}$A menudo se puede convertir en una secuencia tan corta.

El método de la cuadrícula (o método de la caja) es un método introductorio para la multiplicación de números de varias cifras que se suele enseñar a los alumnos de primaria . Forma parte del currículo nacional de matemáticas de primaria en Inglaterra y Gales desde finales de la década de 1990. ^{[ 3 ]}

Ambos factores se dividen ("particionan") en sus partes de centenas, decenas y unidades, y luego se calculan explícitamente los productos de las partes en una etapa de multiplicación relativamente simple, antes de que estas contribuciones se sumen para dar la respuesta final en una etapa de suma separada.

El cálculo 34 × 13, por ejemplo, podría realizarse utilizando la cuadrícula:

 300 40 90 + 12 ———— 442

seguido de la suma para obtener 442, ya sea en una sola suma (ver a la derecha) o mediante la formación de los totales fila por fila.

(300 + 40) + (90 + 12) = 340 + 102 = 442.

Este método de cálculo (aunque no necesariamente con la disposición explícita de la cuadrícula) también se conoce como algoritmo de productos parciales . Su esencia radica en el cálculo de las multiplicaciones simples por separado, dejando todas las sumas para la etapa final de agregación.

En principio, el método de la cuadrícula puede aplicarse a factores de cualquier tamaño, aunque el número de subproductos se vuelve engorroso a medida que aumenta el número de dígitos. No obstante, se considera un método explícito y útil para introducir la idea de las multiplicaciones de varios dígitos; y, en una época en la que la mayoría de los cálculos de multiplicación se realizan con una calculadora o una hoja de cálculo , en la práctica puede ser el único algoritmo de multiplicación que algunos estudiantes necesiten.

La multiplicación reticular, o por criba, es algorítmicamente equivalente a la multiplicación larga. Requiere la preparación de una retícula (una cuadrícula dibujada en papel) que guía el cálculo y separa todas las multiplicaciones de las sumas . Fue introducida en Europa en 1202 en el Liber Abaci de Fibonacci . Fibonacci describió la operación como mental, usando sus manos derecha e izquierda para llevar a cabo los cálculos intermedios. Matrakçı Nasuh presentó 6 variantes diferentes de este método en su libro del siglo XVI, Umdet-ul Hisab. Fue ampliamente utilizado en las escuelas Enderun de todo el Imperio Otomano. ^{[ 4 ]} Los huesos de Napier , o varillas de Napier, también usaban este método, como publicó Napier en 1617, el año de su muerte.

Como se muestra en el ejemplo, el multiplicando y el multiplicador se escriben encima y a la derecha de una cuadrícula o tamiz. Se encuentra en la "Aritmética" de Muhammad ibn Musa al-Khwarizmi , una de las fuentes de Leonardo mencionadas por Sigler, autor de "El Liber Abaci de Fibonacci" (2002).

• Durante la fase de multiplicación, la cuadrícula se rellena con productos de dos dígitos de los dígitos correspondientes que etiquetan cada fila y columna: el dígito de las decenas se coloca en la esquina superior izquierda.
• Durante la fase de adición, la red se suma en las diagonales.
• Finalmente, si es necesaria una fase de acarreo, la respuesta que se muestra a lo largo de los lados izquierdo e inferior de la cuadrícula se convierte a la forma normal llevando los dígitos de las decenas como en la suma o multiplicación larga.

El método binario también se conoce como multiplicación campesina, porque ha sido ampliamente utilizado por personas clasificadas como campesinas y, por lo tanto, no han memorizado las tablas de multiplicar necesarias para la multiplicación larga. ^{[ 5 ]} El algoritmo se utilizaba en el antiguo Egipto. ^{[ 6 ]} Sus principales ventajas son que se puede enseñar rápidamente, no requiere memorización y se puede realizar utilizando fichas, como fichas de póker , si no se dispone de papel y lápiz. La desventaja es que requiere más pasos que la multiplicación larga, por lo que puede resultar engorroso para números grandes.

Decimal: Binario: 11 3 1011 11 5 6 101 110 2 12 10 1100 1 24 1 11000 ——————— 33 100001

Decimal: Binario: 5830 23958233 1011011000110 1011011011001001011011001 2915 47916466 101101100011 10110110110010010110110010 1457 95832932 10110110001 101101101100100101101100100 728 191665864 1011011000 1011011011001001011011001000 364 383331728 101101100 10110110110010010110110010000 182 766663456 10110110 101101101100100101101100100000 91 1533326912 1011011 1011011011001001011011001000000 45 3066653824 101101 10110110110010010110110010000000 22 6133307648 10110 101101101100100101101100100000000 11 12266615296 1011 1011011011001001011011001000000000 5 24533230592 101 10110110110010010110110010000000000 2 49066461184 10 101101101100100101101100100000000000 1 98132922368 1 1011011011001001011011001000000000000 ———————————— 1022143253354344244353353243222210110 (antes de llevar) 139676498390 10000010000101010111100011100111010110

En algunos casos, esta fórmula puede utilizarse para facilitar la realización de tareas de multiplicación:

${\displaystyle {\frac {\left(x+y\right)^{2}}{4}}-{\frac {\left(xy\right)^{2}}{4}}=\left({\frac {x+y}{2}}\right)^{2}-\left({\frac {xy}{2}}\right)^{2}=xy}$

En el caso donde${\displaystyle x}$y${\displaystyle y}$son enteros, tenemos que

${\displaystyle (x+y)^{2}\equiv (xy)^{2}{\bmod {4}}}$

porque${\displaystyle x+y}$y${\displaystyle xy}$son ambos pares o ambos impares. Esto significa que

${\displaystyle {\begin{aligned}xy&={\frac {1}{4}}(x+y)^{2}-{\frac {1}{4}}(xy)^{2}\\&=\left((x+y)^{2}{\text{ div }}4\right)-\left((xy)^{2}{\text{ div }}4\right)\end{aligned}}}$

y es suficiente con (pre)calcular la parte entera de los cuadrados divididos por 4 como en el siguiente ejemplo.

La multiplicación de Karatsuba es un algoritmo de divide y vencerás O( n ^{log ₂ 3} ) ≈ O( n ^1.585 ) que utiliza recursión para fusionar subcálculos.

Al reescribir la fórmula, se posibilita realizar subcálculos/recursión. Mediante la recursión, se puede resolver esto de forma rápida.

Dejar${\displaystyle x}$y${\displaystyle y}$ser representado como${\displaystyle n}$-cadenas de dígitos en alguna base${\displaystyle B}$Para cualquier entero positivo${\displaystyle m}$menos que${\displaystyle n}$, se pueden escribir los dos números dados como

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

dónde${\displaystyle x_{0}}$y${\displaystyle y_{0}}$son menos que${\displaystyle B^{m}}$El producto es entonces

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

dónde

${\displaystyle z_{2}=x_{1}y_{1},}$

${\ Displaystyle z_ {1} = x_ {1} y_ {0} + x_ {0} y_ {1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

Estas fórmulas requieren cuatro multiplicaciones y eran conocidas por Charles Babbage . ^{[ 15 ]} Karatsuba observó que${\displaystyle xy}$se puede calcular en solo tres multiplicaciones, a costa de algunas sumas adicionales. Con${\displaystyle z_{0}}$y${\displaystyle z_{2}}$como antes se puede observar que

${\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{ 1}+x_{0}y_{0}-x_{0}y_{0}\\&=x_{1}y_{0}+x_{0}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}-x_{0}y _{0}\\&=(x_{1}+x_{0})y_{0}+(x_{0}+x_{1})y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.\\\end{aligned}}}$

Debido a la sobrecarga de la recursión, la multiplicación de Karatsuba es más lenta que la multiplicación larga para valores pequeños de n ; por lo tanto, las implementaciones típicas cambian a la multiplicación larga para valores pequeños de n .

Otro método de multiplicación se denomina Toom-Cook o Toom-3. Este método divide cada número a multiplicar en varias partes. El método Toom-Cook es una generalización del método Karatsuba. Un método Toom-Cook de tres partes puede realizar una multiplicación de tamaño 3N con el coste de cinco multiplicaciones de tamaño N. Esto acelera la operación en un factor de 9/5, mientras que el método Karatsuba la acelera en un factor de 4/3.

Si bien el uso de más partes puede reducir aún más el tiempo dedicado a las multiplicaciones recursivas, la sobrecarga derivada de las sumas y la gestión de dígitos también aumenta. Por esta razón, el método de transformadas de Fourier suele ser más rápido para números con varios miles de dígitos, y asintóticamente más rápido para números aún mayores.

Todo número en base B se puede escribir como un polinomio:

$${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$$

Además, la multiplicación de dos números podría considerarse como el producto de dos polinomios:

$${\displaystyle XY=(\sum _{i=0}^{N}{x_{i}B^{i}})\,(\sum _{j=0}^{N}{y_{i}B^{j}})}$$

Dado que el coeficiente de${\displaystyle B^{k}}$en el producto es$${\displaystyle z_{k}=\sum _{(i,j):i+j=k}{x_{i}y_{j}}=\sum _{i=0}^{k}{x_{i}y_{k-i}},}$$ Se puede utilizar una convolución o la transformada rápida de Fourier (FFT): $${\displaystyle {\hat {f}}(XY)={\hat {f}}(\sum _{i=0}^{k}{x_{i}y_{k-i}})={\hat {f}}(X)\cdot {\hat {f}}(Y).}$$

Por lo tanto, la multiplicación se reduce a una FFT ,${\displaystyle N}$multiplicaciones y una FFT inversa. El resultado es una complejidad temporal de O ( n  log( n  ) log (log n )) .

En 2007, el matemático suizo Martin Fürer, de la Universidad Estatal de Pensilvania, mejoró la complejidad asintótica de la multiplicación de enteros.${\textstyle O(n\log n\cdot {2}^{\Theta (\log ^{*}(n))})}$usando transformadas de Fourier sobre números complejos , ^{[ 18 ]} donde log ^* denota el logaritmo iterado . Anindya De, Chandan Saha, Piyush Kurur y Ramprasad Saptharishi dieron un algoritmo similar usando aritmética modular en 2008 logrando el mismo tiempo de ejecución. ^{[ 19 ]} En el contexto del material anterior, lo que estos últimos autores han logrado es encontrar N mucho menor que 2 ^{3 k} + 1, de modo que Z / NZ tenga una raíz (2 m )-ésima de la unidad. Esto acelera el cálculo y reduce la complejidad temporal. Sin embargo, estos últimos algoritmos solo son más rápidos que Schönhage–Strassen para entradas impracticablemente grandes.

En 2014, Harvey, Joris van der Hoeven y Lecerf ^{[ 20 ]} presentaron un nuevo algoritmo que logra un tiempo de ejecución de${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$, haciendo explícita la constante implícita en la${\displaystyle O(\log ^{*}n)}$exponente. También propusieron una variante de su algoritmo que logra${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$pero cuya validez se basa en conjeturas estándar sobre la distribución de los primos de Mersenne . En 2016, Covanov y Thomé propusieron un algoritmo de multiplicación de enteros basado en una generalización de los primos de Fermat que, según conjeturas, alcanza un límite de complejidad de${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$Esto coincide con el resultado condicional de 2015 de Harvey, van der Hoeven y Lecerf, pero utiliza un algoritmo diferente y se basa en una conjetura diferente. ^{[ 21 ]} En 2018, Harvey y van der Hoeven utilizaron un enfoque basado en la existencia de vectores reticulares cortos garantizados por el teorema de Minkowski para demostrar una cota de complejidad incondicional de${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$. ^{[ 22 ]}

En marzo de 2019, David Harvey y Joris van der Hoeven anunciaron su descubrimiento de un algoritmo de multiplicación O ( n log n ) . ^{[ 23 ]} Fue publicado en los Annals of Mathematics en 2021. ^{[ 14 ]} Debido a que Schönhage y Strassen predijeron que n  log( n ) es el resultado "mejor posible", Harvey dijo: "...  se espera que nuestro trabajo sea el final del camino para este problema, aunque todavía no sabemos cómo demostrarlo rigurosamente". ^{[ 24 ]} Sin embargo, el nuevo algoritmo es muy poco práctico: es más rápido que el algoritmo de Schönhage-Strassen solo si el número de dígitos excede ^{[ 14 ]}

${\displaystyle {\begin{aligned}2^{{1729}^{12}}&=2^{713\,739\,807\,325\,663\,489\,766\,475\,852\,620\,783\,120\,641}\\&\approx 4.145331\times 10^{214\,857\,091\,104\,455\,254\,035\,802\,532\,723\,729\,912\,717}\\&\approx 10^{2.148571\times 10^{38}}.\end{aligned}}}$

Existe una cota inferior trivial de Ω ( n ) para multiplicar dos números de n bits en un solo procesador; no se conoce ningún algoritmo equivalente (en máquinas convencionales, es decir, en máquinas equivalentes a Turing) ni ninguna cota inferior más precisa. La conjetura de Hartmanis-Stearns implicaría que${\displaystyle O(n)}$no se puede lograr. La multiplicación está fuera de AC ⁰ [ p ] para cualquier primo p , lo que significa que no hay una familia de circuitos de profundidad constante y tamaño polinomial (o incluso subexponencial) que utilicen compuertas AND, OR, NOT y MOD _p que puedan calcular un producto. Esto se deduce de una reducción de profundidad constante de MOD _q a la multiplicación. ^{[ 25 ]} También se conocen cotas inferiores para la multiplicación para algunas clases de programas de ramificación . ^{[ 26 ]}

• Las diversas formas de utilizar la aritmética en las matemáticas cotidianas de UCSMP
• Una presentación de PowerPoint sobre matemáticas antiguas
• Vídeo Flash de multiplicación reticular

• Algoritmos de multiplicación utilizados por GMP