Algoritmo de multiplicación

Algoritmo para multiplicar dos números

Un algoritmo de multiplicación es un algoritmo (o método) para multiplicar dos números. Dependiendo del tamaño de los números, algunos algoritmos son más eficientes que otros. Se conocen numerosos algoritmos y se ha investigado mucho sobre el tema.

El método más antiguo y simple, conocido desde la antigüedad como multiplicación larga o multiplicación escolar , consiste en multiplicar cada dígito del primer número por cada dígito del segundo y sumar los resultados. Esto tiene una complejidad temporal de , donde n es el número de dígitos. Cuando se hace a mano, esto también puede reformularse como multiplicación por método de cuadrícula o multiplicación reticular . En software, esto puede llamarse "desplazamiento y suma" debido a que los desplazamientos de bits y la suma son las únicas dos operaciones necesarias. ${\displaystyle O(n^{2})}$

En 1960, Anatoly Karatsuba descubrió la multiplicación de Karatsuba , lo que desató una avalancha de investigaciones sobre algoritmos de multiplicación rápida. Este método utiliza tres multiplicaciones en lugar de cuatro para multiplicar dos números de dos dígitos. (También se puede utilizar una variante de esto para multiplicar números complejos rápidamente). Si se realiza de forma recursiva , esto tiene una complejidad temporal de . Dividir números en más de dos partes da como resultado la multiplicación de Toom-Cook ; por ejemplo, el uso de tres partes da como resultado el algoritmo Toom-3 . El uso de muchas partes puede hacer que el exponente se acerque arbitrariamente a 1, pero el factor constante también crece, lo que lo hace poco práctico. ${\displaystyle O(n^{\log _{2}3})}$

En 1968, se descubrió el algoritmo de Schönhage-Strassen , que utiliza una transformada de Fourier sobre un módulo . Tiene una complejidad temporal de . En 2007, Martin Fürer propuso un algoritmo con una complejidad . En 2014, Harvey, Joris van der Hoeven y Lecerf propusieron uno con una complejidad , haciendo explícita la constante implícita; esto se mejoró a en 2018. Por último, en 2019, Harvey y van der Hoeven propusieron un algoritmo galáctico con una complejidad . Esto coincide con una suposición de Schönhage y Strassen de que este sería el límite óptimo, aunque esto sigue siendo una conjetura hoy en día. ${\displaystyle O(n\log n\log \log n)}$ ${\displaystyle O(n\log n2^{\Theta (\log ^{*}n)})}$ ${\displaystyle O(n\log n2^{3\log ^{*}n})}$ ${\displaystyle O(n\log n2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n)}$

Los algoritmos de multiplicación de enteros también se pueden utilizar para multiplicar polinomios mediante el método de sustitución de Kronecker .

Multiplicación larga

Si se utiliza un sistema de numeración posicional , en las escuelas se enseña una forma natural de multiplicar números: la multiplicación larga , a veces llamada multiplicación escolar primaria , a veces llamada algoritmo estándar : se multiplica el multiplicando por cada dígito del multiplicador y luego se suman todos los resultados correctamente desplazados. Requiere memorizar la tabla de multiplicar de un solo dígito.

Este es el algoritmo habitual para multiplicar números grandes a mano en base 10. Una persona que realiza una multiplicación larga en un papel escribirá todos los productos y luego los sumará; un usuario de ábaco sumará los productos tan pronto como se calcule cada uno.

Ejemplo

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)

Otras notaciones

En algunos países como Alemania , la multiplicación anterior se representa de manera similar, pero con el producto original mantenido horizontal y el cálculo comenzando con el primer dígito del multiplicador: ^[1]

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

El pseudocódigo que se muestra a continuación describe el proceso de multiplicación anterior. Solo se conserva una fila para mantener la suma que finalmente se convierte en el resultado. Tenga en cuenta que el operador '+=' se utiliza para indicar la suma del valor existente y la operación de almacenamiento (similar a lenguajes como Java y C) para lograr una mayor compacidad.

multiplicar ( a [ 1 .. p ] , b [ 1 .. q ] , base ) // Operandos que contienen dígitos más a la derecha en el índice 1    producto = [ 1 .. p + q ] // Asignar espacio para el resultado    para b_i = 1 a q // para todos los dígitos en b       llevar = 0   para a_i = 1 a p // para todos los dígitos en a       producto [ a_i + b_i - 1 ] += acarreo + a [ a_i ] * b [ b_i ]           acarreo = producto [ a_i + b_i - 1 ] / base         producto [ a_i + b_i - 1 ] = producto [ a_i + b_i - 1 ] módulo base             producto [ b_i + p ] = acarreo // el último dígito proviene del acarreo final      devolver producto 

Uso en ordenadores

Algunos chips implementan la multiplicación larga, en hardware o en microcódigo , para varios tamaños de palabras enteras y de punto flotante. En aritmética de precisión arbitraria , es común usar la multiplicación larga con la base establecida en 2 ^w , donde w es el número de bits en una palabra, para multiplicar números relativamente pequeños. Para multiplicar dos números con n dígitos utilizando este método, se necesitan aproximadamente n ² operaciones. Más formalmente, multiplicar dos números de n dígitos utilizando 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 lidiar con el desbordamiento durante las sumas, lo que 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 máquina. Luego se pueden realizar varias sumas antes de que se produzca un desbordamiento. Cuando el número se vuelve demasiado grande, agregamos parte de él al resultado, o trasladamos y mapeamos la parte restante nuevamente a un número que sea menor que b . Este proceso se llama normalización . Richard Brent utilizó este enfoque en su paquete Fortran, MP. ^[2]

Los ordenadores utilizaban inicialmente un algoritmo muy similar a la multiplicación larga en base 2, pero los procesadores modernos han optimizado los circuitos para multiplicaciones rápidas utilizando algoritmos más eficientes, al precio de una realización de hardware más compleja. ^{[ cita requerida ]} En base dos, la multiplicación larga a veces se llama "desplazamiento y suma" , porque el algoritmo se simplifica y solo consiste 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 varios tamaños de números enteros y de punto flotante en multiplicadores de hardware o en microcódigo . ^{[ cita requerida ]}

En los procesadores disponibles actualmente, una instrucción de desplazamiento bit a bit suele ser (pero no siempre) más rápida que una instrucción de multiplicación y se puede utilizar para multiplicar (desplazar a la izquierda) y dividir (desplazar a la derecha) por potencias de dos. La multiplicación por una constante y la división por una constante se pueden implementar utilizando una secuencia de desplazamientos y sumas o restas. Por ejemplo, hay varias formas de multiplicar por 10 utilizando solo 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, estas secuencias de desplazamientos y sumas o restas superan a los multiplicadores de hardware y, especialmente, a los divisores. Una división por un número de la forma o a menudo se puede convertir en una secuencia corta de este tipo. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}\pm 1}$

Algoritmos para multiplicar a mano

Además de la multiplicación larga estándar, existen otros métodos que se utilizan para realizar la multiplicación a mano. Estos algoritmos pueden idearse para aumentar la velocidad, facilitar el cálculo o tener un valor educativo, en particular cuando no se dispone de computadoras o tablas de multiplicar .

Método de cuadrícula

El método de cuadrícula (o método de caja) es un método introductorio para la multiplicación de varios dígitos que se suele enseñar a los alumnos de la escuela primaria o de la escuela elemental . Ha sido una parte estándar del plan de estudios nacional de matemáticas de la escuela primaria en Inglaterra y Gales desde finales de la década de 1990. ^[3]

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

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

 300 40 90 + 12 ———— 442

seguido de la adición para obtener 442, ya sea en una sola suma (ver a la derecha), o formando 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 es el cálculo de las multiplicaciones simples por separado, dejando todas las sumas para la etapa final de recopilación.

En principio, el método de cuadrícula se puede aplicar 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 lo considera un método explícito ú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, puede ser en la práctica el único algoritmo de multiplicación que algunos estudiantes necesitarán.

Multiplicación reticular

Primero, arma la cuadrícula marcando las filas y columnas con los números que se van a multiplicar. Luego, llena los recuadros con las decenas en los triángulos superiores y las unidades en los inferiores.

Finalmente, sume a lo largo de las diagonales y lleve el resultado según sea necesario para obtener la respuesta.

La multiplicación en red o por tamiz es algorítmicamente equivalente a la multiplicación larga. Requiere la preparación de una red (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 realizar los cálculos intermedios. Matrakçı Nasuh presentó 6 variantes diferentes de este método en este libro del siglo XVI, Umdet-ul Hisab. Fue ampliamente utilizado en las escuelas Enderun en todo el Imperio Otomano. ^[4] Los huesos de Napier , o las varas de Napier , también utilizaron este método, como lo 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 "Fibonacci's Liber Abaci", 2002. ^{[ cita requerida ]}

• Durante la fase de multiplicación, la red se llena con productos de dos dígitos de los dígitos correspondientes que etiquetan cada fila y columna: el dígito de las decenas va 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 tal como se muestra a lo largo de los lados izquierdo e inferior de la red se convierte a la forma normal al transportar los dígitos de las decenas como en una suma o multiplicación larga.

Ejemplo

Las imágenes de la derecha muestran cómo calcular 345 × 12 mediante la multiplicación reticular. Como ejemplo más complicado, considere la imagen a continuación que muestra el cálculo de 23,958,233 multiplicado por 5,830 (multiplicador); el resultado es 139,676,498,390. Observe que 23,958,233 está en la parte superior de la red y 5,830 en el lado derecho. Los productos llenan la red y la suma de esos productos (en la diagonal) está en los lados izquierdo e inferior. Luego, esas sumas se suman como se muestra.

Multiplicación campesina rusa

El método binario también se conoce como multiplicación campesina, porque ha sido ampliamente utilizado por personas que se clasifican como campesinos y, por lo tanto, no han memorizado las tablas de multiplicación necesarias para la multiplicación larga. ^{[5] [ verificación fallida ]} El algoritmo se usaba 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óquer , 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 difícil de manejar para números grandes.

Descripción

En una hoja de papel, escribe en una columna los números que obtienes al dividir repetidamente por la mitad el multiplicador, ignorando el resto; en una columna a su lado, duplica repetidamente el multiplicando. Tacha cada fila en la que el último dígito del primer número sea par y suma los números restantes en la segunda columna para obtener el producto.

Ejemplos

Este ejemplo utiliza la multiplicación campesina para multiplicar 11 por 3 y llegar a un resultado de 33.

Decimal: Binario:11 3 1011 115 6 101 1102 12 10 11001 24 1 11000 —— —————— 33 100001

Describiendo los pasos explícitamente:

• 11 y 3 están escritos en la parte superior
• 11 se reduce a la mitad (5,5) y 3 se duplica (6). La parte fraccionaria se descarta (5,5 se convierte en 5).
• Se reduce a la mitad el 5 (2,5) y se duplica el 6 (12). Se descarta la parte fraccionaria (2,5 se convierte en 2). La cifra de la columna de la izquierda (2) es par , por lo que se descarta la cifra de la columna de la derecha (12).
• 2 se reduce a la mitad (1) y 12 se duplica (24).
• Se suman todos los valores no tachados: 3 + 6 + 24 = 33.

El método funciona porque la multiplicación es distributiva , entonces:

${\displaystyle {\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^{3})\\&=3\times (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}}$

Un ejemplo más complicado, utilizando las cifras de los ejemplos anteriores (23.958.233 y 5.830):

Decimal: Binario:5830 23958233 1011011000110 10110110110010010110110012915 47916466 101101100011 101101101100100101101100101457 95832932 10110110001 101101101100100101101100100728 191665864 1011011000 1011011011001001011011001000
364 383331728 101101100 10110110110010010110110010000
182 766663456 10110110 10110110110010010110110010000091 1533326912 1011011 101101101100100101101100100000045 3066653824 101101 1011011011001001011011001000000022 6133307648 10110 10110110110010010110110010000000011 12266615296 1011 10110110110010010110110010000000005 24533230592 101 101101101100100101101100100000000002 49066461184 10 101101101100100101101100100000000000
1 98132922368 1 10110110110010010110110010000000000000 ———————————— 1022143253354344244353353243222210110 (antes de llevar) 139676498390 10000010000101010111100011100111010110

Multiplicación de un cuarto de cuadrado

Esta fórmula se puede utilizar en algunos casos para facilitar la realización de tareas de multiplicación:

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

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

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

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

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

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

Ejemplos

A continuación se muestra una tabla de búsqueda de cuartos cuadrados con el resto descartado para los dígitos del 0 al 18; esto permite la multiplicación de números hasta 9×9 .

Si, por ejemplo, quisieras multiplicar 9 por 3, observarías que la suma y la diferencia son 12 y 6 respectivamente. Al buscar ambos valores en la tabla, obtendrías 36 y 9, cuya diferencia es 27, que es el producto de 9 y 3.

Historia de la multiplicación de un cuarto de cuadrado

En tiempos prehistóricos, la multiplicación de un cuarto de cuadrado implicaba la función base , que algunas fuentes ^{[7] [8]} atribuyen a las matemáticas babilónicas (2000-1600 a. C.).

Antoine Voisin publicó una tabla de cuartos de cuadrado del 1 al 1000 en 1817 como ayuda para la multiplicación. Samuel Laundy publicó una tabla más grande de cuartos de cuadrado del 1 al 100000 en 1856 ^[9] y Joseph Blater publicó una tabla del 1 al 200000 en 1888 ^[10].

Los multiplicadores de cuarto de cuadrado se utilizaban en ordenadores analógicos para formar una señal analógica que era el producto de dos señales de entrada analógicas. En esta aplicación, la suma y la diferencia de dos voltajes de entrada se forman utilizando amplificadores operacionales . El cuadrado de cada uno de ellos se aproxima utilizando circuitos lineales por partes . Finalmente, la diferencia de los dos cuadrados se forma y se escala por un factor de un cuarto utilizando otro amplificador operacional.

En 1980, Everett L. Johnson propuso utilizar el método del cuarto de cuadrado en un multiplicador digital . ^[11] Para formar el producto de dos enteros de 8 bits, por ejemplo, el dispositivo digital forma la suma y la diferencia, busca ambas cantidades en una tabla de cuadrados, toma la diferencia de los resultados y divide por cuatro desplazando dos bits a la derecha. Para los enteros de 8 bits, la tabla de cuartos de cuadrado tendrá 2 ⁹ −1=511 entradas (una entrada para el rango completo 0..510 de sumas posibles, las diferencias utilizan solo las primeras 256 entradas en el rango 0..255) o 2 ⁹ −1=511 entradas (utilizando para las diferencias negativas la técnica de complementos a 2 y enmascaramiento de 9 bits, que evita probar el signo de las diferencias), cada entrada tiene 16 bits de ancho (los valores de entrada son de (0²/4)=0 a (510²/4)=65025).

La técnica del multiplicador de un cuarto de cuadrado ha beneficiado a los sistemas de 8 bits que no tienen soporte para un multiplicador de hardware. Charles Putney implementó esto para el 6502. [ ^12]

Complejidad computacional de la multiplicación

Problema sin resolver en informática :

¿Cuál es el algoritmo más rápido para la multiplicación de números de dos dígitos? ${\displaystyle n}$

(más problemas sin resolver en informática)

Una línea de investigación en informática teórica trata sobre el número de operaciones aritméticas de un solo bit necesarias para multiplicar números enteros de dos bits. Esto se conoce como la complejidad computacional de la multiplicación. Los algoritmos habituales realizados a mano tienen una complejidad asintótica de , pero en 1960 Anatoly Karatsuba descubrió que era posible lograr una mayor complejidad (con el algoritmo de Karatsuba ). ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

Actualmente, el algoritmo con la mejor complejidad computacional es un algoritmo de 2019 de David Harvey y Joris van der Hoeven , que utiliza las estrategias de uso de transformadas de teoría de números introducidas con el algoritmo de Schönhage-Strassen para multiplicar números enteros utilizando solo operaciones. ^[13] Se conjetura que este es el mejor algoritmo posible, pero no se conocen los límites inferiores. ${\displaystyle O(n\log n)}$ ${\displaystyle \Omega (n\log n)}$

Multiplicación de Karatsuba

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

Al reescribir la fórmula, es posible realizar cálculos secundarios o recursividad. Al realizar la recursión, se puede resolver este problema de manera rápida.

Sean y representados como cadenas de dígitos en alguna base . Para cualquier entero positivo menor que , se pueden escribir los dos números dados como ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle n}$

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

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

donde y son menores que . El producto es entonces ${\displaystyle x_{0}}$ ${\displaystyle y_{0}}$ ${\displaystyle B^{m}}$

${\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 . ^[14] Karatsuba observó que se puede calcular en sólo tres multiplicaciones, al costo de unas pocas adiciones adicionales. Con y como antes se puede observar que ${\displaystyle xy}$ ${\displaystyle z_{0}}$ ${\displaystyle z_{2}}$

${\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 .

Caso general con multiplicación de N números

Al explorar patrones después de la expansión, se observa lo siguiente:

${\displaystyle (x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})(z_{1}B^{m}+z_{0})(a_{1}B^{m}+a_{0})=}$
${\displaystyle a_{1}x_{1}y_{1}z_{1}B^{4m}+a_{1}x_{1}y_{1}z_{0}B^{3m}+a_{1}x_{1}y_{0}z_{1}B^{3m}+a_{1}x_{0}y_{1}z_{1}B^{3m}}$
${\displaystyle +a_{0}x_{1}y_{1}z_{1}B^{3m}+a_{1}x_{1}y_{0}z_{0}B^{2m}+a_{1}x_{0}y_{1}z_{0}B^{2m}+a_{0}x_{1}y_{1}z_{0}B^{2m}}$
${\displaystyle +a_{1}x_{0}y_{0}z_{1}B^{2m}+a_{0}x_{1}y_{0}z_{1}B^{2m}+a_{0}x_{0}y_{1}z_{1}B^{2m}+a_{1}x_{0}y_{0}z_{0}B^{m}}$
${\displaystyle +a_{0}x_{1}y_{0}z_{0}B^{m}+a_{0}x_{0}y_{1}z_{0}B^{m}+a_{0}x_{0}y_{0}z_{1}B^{m}+a_{0}x_{0}y_{0}z_{0}}$

Cada sumando está asociado a un número binario único de 0 a , por ejemplo , etc. Además; B se potencia al número 1, en esta cadena binaria, multiplicado por m. ${\displaystyle 2^{N+1}-1}$ ${\displaystyle a_{1}x_{1}y_{1}z_{1}\longleftrightarrow 1111,\ a_{1}x_{0}y_{1}z_{0}\longleftrightarrow 1010}$

Si expresamos esto en menos términos, obtenemos:

${\displaystyle \prod _{j=1}^{N}(x_{j,1}B^{m}+x_{j,0})=\sum _{i=1}^{2^{N+1}-1}\prod _{j=1}^{N}x_{j,c(i,j)}B^{m\sum _{j=1}^{N}c(i,j)}=\sum _{j=0}^{N}z_{j}B^{jm}}$, donde significa dígito en el número i en la posición j. Nótese que ${\displaystyle c(i,j)}$ ${\displaystyle c(i,j)\in \{0,1\}}$

${\displaystyle z_{0}=\prod _{j=1}^{N}x_{j,0}}$
${\displaystyle z_{N}=\prod _{j=1}^{N}x_{j,1}}$
${\displaystyle z_{N-1}=\prod _{j=1}^{N}(x_{j,0}+x_{j,1})-\sum _{i\neq N-1}^{N}z_{i}}$

Historia

El algoritmo de Karatsuba fue el primer algoritmo conocido para la multiplicación que es asintóticamente más rápido que la multiplicación larga, ^[15] y por lo tanto puede considerarse como el punto de partida de la teoría de las multiplicaciones rápidas.

Toom-cocinero

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

Aunque el uso de más y más partes puede reducir aún más el tiempo empleado en multiplicaciones recursivas, también aumenta la sobrecarga de las sumas y la gestión de dígitos. Por este motivo, 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.

Calle Schönhage

Demostración de la multiplicación de 1234 × 5678 = 7006652 mediante transformadas rápidas de Fourier (FFT). Se utilizan transformadas de teoría de números en los números enteros módulo 337, seleccionando 85 como octava raíz de la unidad. Se utiliza la base 10 en lugar de la base 2 ^w con fines ilustrativos.

Todo número en base B, puede escribirse como polinomio:

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

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

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

Porque, para : , tenemos una convolución. ${\displaystyle B^{k}}$ ${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}}$

Al utilizar fft (transformación rápida de Fourier) con la regla de convolución, podemos obtener

${\displaystyle {\hat {f}}(a*b)={\hat {f}}(\sum _{i=0}^{k}{a_{i}b_{k-i}})={\hat {f}}(a)}$● . Es decir; ● , donde es el coeficiente correspondiente en el espacio de Fourier. Esto también se puede escribir como: fft(a * b) = fft(a) ● fft(b). ${\displaystyle {\hat {f}}(b)}$ ${\displaystyle C_{k}=a_{k}}$ ${\displaystyle b_{k}}$ ${\displaystyle C_{k}}$

Tenemos el mismo coeficiente debido a la linealidad bajo la transformación de Fourier, y porque estos polinomios solo constan de un término único por coeficiente:

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ y ${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

Regla de convolución: ● ${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)}$ ${\displaystyle {\hat {f}}(Y)}$

Hemos reducido nuestro problema de convolución a un problema de producto, a través de fft.

Al encontrar ifft (interpolación polinomial), para cada , se obtienen los coeficientes deseados. ${\displaystyle c_{k}}$

El algoritmo utiliza la estrategia de dividir y vencer para dividir el problema en subproblemas.

Tiene una complejidad temporal de O( n  log( n ) log(log( n ))).

Historia

El algoritmo fue inventado por Strassen (1968). En 1971, Schönhage y Strassen lo pusieron en práctica y aportaron garantías teóricas, dando como resultado el algoritmo de Schönhage-Strassen . ^[16]

Otras mejoras

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 números enteros a n  log( n ) 2 ^{Θ( log * ( n ))} utilizando transformadas de Fourier sobre números complejos , ^[17] donde log ^* denota el logaritmo iterado . Anindya De, Chandan Saha, Piyush Kurur y Ramprasad Saptharishi dieron un algoritmo similar utilizando aritmética modular en 2008 logrando el mismo tiempo de ejecución. ^[18] 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 tiene 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 imprácticamente grandes.

En 2014, Harvey, Joris van der Hoeven y Lecerf ^[19] dieron un nuevo algoritmo que logra un tiempo de ejecución de , haciendo explícita la constante implícita en el exponente. También propusieron una variante de su algoritmo que logra pero cuya validez se basa en conjeturas estándar sobre la distribución de primos de Mersenne . En 2016, Covanov y Thomé propusieron un algoritmo de multiplicación de enteros basado en una generalización de primos de Fermat que conjeturalmente logra un límite de complejidad de . 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. ^[20] En 2018, Harvey y van der Hoeven utilizaron un enfoque basado en la existencia de vectores de red cortos garantizados por el teorema de Minkowski para demostrar un límite de complejidad incondicional de . ^[21] ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$ ${\displaystyle O(\log ^{*}n)}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

En marzo de 2019, David Harvey y Joris van der Hoeven anunciaron su descubrimiento de un algoritmo de multiplicación de O ( n log n ) . ^[22] Se publicó en Annals of Mathematics en 2021. ^[23] 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 probar esto rigurosamente". ^[24]

Límites inferiores

Existe un límite inferior trivial de Ω ( n ) para multiplicar dos números de n bits en un solo procesador; no se conoce ningún algoritmo de coincidencia (en máquinas convencionales, es decir, en máquinas equivalentes de Turing) ni ningún límite inferior más preciso. La multiplicación se encuentra fuera de AC ⁰ [ p ] para cualquier primo p , lo que significa que no existe una familia de circuitos de tamaño polinomial (o incluso subexponencial) de profundidad constante que utilicen puertas AND, OR, NOT y MOD _p que puedan calcular un producto. Esto se desprende de una reducción de profundidad constante de MOD _q a multiplicación. ^[25] También se conocen límites inferiores para la multiplicación para algunas clases de programas de ramificación . ^[26]

Multiplicación de números complejos

La multiplicación compleja normalmente implica cuatro multiplicaciones y dos sumas.

${\displaystyle (a+bi)(c+di)=(ac-bd)+(bc+ad)i.}$

O

${\displaystyle {\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}}$

Como observó Peter Ungar en 1963, uno puede reducir el número de multiplicaciones a tres, utilizando esencialmente el mismo cálculo que el algoritmo de Karatsuba . ^[27] El producto ( a  +  bi ) · ( c  +  di ) se puede calcular de la siguiente manera.

k ₁ = c · ( a + b )

k ₂ = a · ( d − c )

k3 = b · ( c + d ₎

Parte real = k ₁ − k ₃

Parte imaginaria = k ₁ + k ₂ .

Este algoritmo utiliza sólo tres multiplicaciones, en lugar de cuatro, y cinco sumas o restas, en lugar de dos. Si una multiplicación es más costosa que tres sumas o restas, como cuando se calcula a mano, entonces hay una ganancia en velocidad. En las computadoras modernas, una multiplicación y una suma pueden tomar aproximadamente el mismo tiempo, por lo que es posible que no haya ganancia en velocidad. Existe una desventaja, ya que puede haber cierta pérdida de precisión al usar punto flotante.

Para las transformadas rápidas de Fourier (FFT) (o cualquier transformación lineal ), las multiplicaciones complejas se realizan mediante coeficientes constantes c  +  di (llamados factores de torsión en las FFT), en cuyo caso se pueden calcular previamente dos de las adiciones ( d − c y c + d ). Por lo tanto, solo se requieren tres multiplicaciones y tres sumas. ^[28] Sin embargo, intercambiar una multiplicación por una suma de esta manera puede que ya no sea beneficioso con las unidades de punto flotante modernas . ^[29]

Multiplicación de polinomios

Todos los algoritmos de multiplicación anteriores también se pueden ampliar para multiplicar polinomios . Alternativamente, se puede utilizar la técnica de sustitución de Kronecker para convertir el problema de multiplicar polinomios en una única multiplicación binaria. ^[30]

Los métodos de multiplicación largos se pueden generalizar para permitir la multiplicación de fórmulas algebraicas:

14ac - 3ab + 2 multiplicado por ac - ab + 1

14ac-3ab2 ac-ab 1 ————————————————————— 14a 2c 2-3a 2bc 2ac​ ​ -14a 2bc 3a 2b 2-2ab​ ​ 14ac-3ab2 ————————————————————————————————————————14a2c2-17a2bc16ac3a2b2-5ab + 2​​​​​​​ ​ ========================================= [31]

Como otro ejemplo de multiplicación basada en columnas, considere multiplicar 23 toneladas largas (t), 12 quintales (cwt) y 2 cuartos (qtr) por 47. Este ejemplo utiliza medidas avoirdupois : 1 t = 20 cwt, 1 cwt = 4 qtr.

 t cwt trimestre 23 12 2 47x ———————————————— 141 94 94 940 470 29 23 ———————————————— 1110 587 94 ———————————————— 1110 7 2 ================= Respuesta: 1110 toneladas 7 cwt 2 qtr

Primero, multiplica los cuartos por 47, el resultado 94 se escribe en el primer espacio de trabajo. Luego, multiplica cwt 12*47 = (2 + 10)*47 pero no sumes todavía los resultados parciales (94, 470). Del mismo modo, multiplica 23 por 47, lo que da (141, 940). Se suma la columna de los cuartos y el resultado se coloca en el segundo espacio de trabajo (un movimiento trivial en este caso). 94 cuartos son 23 cwt y 2 qtr, así que coloca el 2 en la respuesta y pon el 23 en la siguiente columna a la izquierda. Ahora suma las tres entradas en la columna cwt, lo que da 587. Esto es 29 t 7 cwt, así que escribe el 7 en la respuesta y el 29 en la columna de la izquierda. Ahora suma la columna de toneladas. No hay que hacer ningún ajuste, así que el resultado simplemente se copia.

El mismo diseño y los mismos métodos se pueden utilizar para cualquier medida tradicional y moneda no decimal, como el antiguo sistema británico £sd .

Véase también

• Multiplicador binario
• Multiplicador de Dadda
• Algoritmo de división
• Esquema de Horner para evaluar un polinomio
• Logaritmo
• Cálculo mental
• Transformación de la teoría de números
• Prosteatoféresis
• Regla de cálculo
• Sistema de Trachtenberg
• Sistema de numeración de residuos § Multiplicación para otro algoritmo de multiplicación rápido, especialmente eficiente cuando se realizan muchas operaciones en secuencia, como en el álgebra lineal.
• Árbol de Wallace

Referencias

1. "Multiplicación". www.mathematische-basteleien.de . Consultado el 15 de marzo de 2022 .
2. Brent, Richard P (marzo de 1978). "Un paquete aritmético de precisión múltiple en Fortran". ACM Transactions on Mathematical Software . 4 : 57–70. CiteSeerX 10.1.1.117.8425 . doi :10.1145/355769.355775. S2CID  8875817. 
3. Eason, Gary (13 de febrero de 2000). "De vuelta a la escuela para los padres". BBC News .
   Eastaway, Rob (10 de septiembre de 2010). "Por qué los padres no pueden hacer matemáticas hoy en día". BBC News.
4. Corlu, MS; Burlbaw, LM; Capraro, RM; Corlu, MA; Han, S. (2010). "La escuela del palacio otomano Enderun y el hombre con múltiples talentos, Matrakçı Nasuh". Revista de la Sociedad Coreana de Educación Matemática Serie D: Investigación en Educación Matemática . 14 (1): 19–31.
5. Bogomolny, Alexander . "Multiplicación campesina". www.cut-the-knot.org . Consultado el 4 de noviembre de 2017 .
6. Wells, D. (1987). Diccionario Penguin de números curiosos e interesantes . Penguin Books. pág. 44. ISBN 978-0-14-008029-2.
7. McFarland, David (2007), Quarter Tables Revisited: Early Tables, Division of Labor in Table Construction, and Later Implementations in Analog Computers (Tablas de cuartos revisadas: tablas anteriores, división del trabajo en la construcción de tablas e implementaciones posteriores en computadoras analógicas), pág. 1
8. Robson, Eleanor (2008). Matemáticas en el antiguo Irak: una historia social . Princeton University Press. pág. 227. ISBN 978-0691201405.
9. "Reseñas", Revista del ingeniero civil y arquitecto : 54–55, 1857.
10. Holmes, Neville (2003), "Multiplicar con cuadrados de cuartos", The Mathematical Gazette , 87 (509): 296–299, doi :10.1017/S0025557200172778, JSTOR  3621048, S2CID  125040256.
11. Everett L., Johnson (marzo de 1980), "Un multiplicador digital de un cuarto de cuadrado", IEEE Transactions on Computers , vol. C-29, núm. 3, Washington, DC, EE. UU.: IEEE Computer Society, págs. 258-261, doi :10.1109/TC.1980.1675558, ISSN  0018-9340, S2CID  24813486
12. Putney, Charles (marzo de 1986). "La multiplicación 6502 más rápida hasta la fecha". Línea de montaje de Apple . 6 (6).
13. Harvey, David; van der Hoeven, Joris (2021). "Multiplicación de enteros en tiempo O ( n log ⁡ n ) {\displaystyle O(n\log n)}" (PDF) . Anales de Matemáticas . Segunda serie. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
14. Charles Babbage, Capítulo VIII – De la máquina analítica, tratados sobre números mayores, pasajes de la vida de un filósofo, Longman Green, Londres, 1864; página 125.
15. D. Knuth, El arte de la programación informática , vol. 2, sección 4.3.3 (1998)
16. Schönhage, A.; Strassen, V. (1971). "Schnelle Multiplication großer Zahlen". Computación . 7 (3–4): 281–292. doi :10.1007/BF02242355. S2CID  9738629.
17. Fürer, M. (2007). "Multiplicación de enteros más rápida" (PDF) . Actas del trigésimo noveno simposio anual de la ACM sobre teoría de la computación, 11-13 de junio de 2007, San Diego, California, EE. UU . . págs. 57-66. doi :10.1145/1250790.1250800. ISBN . 978-1-59593-631-8. Número de identificación del sujeto  8437794.
18. De, A.; Saha, C.; Kurur, P.; Saptharishi, R. (2008). "Multiplicación rápida de números enteros mediante aritmética modular". Actas del 40.º Simposio anual de la ACM sobre teoría de la computación (STOC) . pp. 499–506. arXiv : 0801.1416 . doi :10.1145/1374376.1374447. ISBN 978-1-60558-047-0. Número de identificación del sujeto  3264828.
19. Harvey, David; van der Hoeven, Joris; Lecerf, Grégoire (2016). "Multiplicación de enteros aún más rápida". Revista de Complejidad . 36 : 1–30. arXiv : 1407.3360 . doi :10.1016/j.jco.2016.03.001. SEÑOR  3530637.
20. Covanov, Svyatoslav; Thomé, Emmanuel (2019). "Multiplicación rápida de enteros usando primos de Fermat generalizados". Matemáticas. Comp. 88 (317): 1449–1477. arXiv : 1502.02800 . doi :10.1090/mcom/3367. S2CID  : 67790860.
21. Harvey, D.; van der Hoeven, J. (2019). "Multiplicación de números enteros más rápida usando vectores reticulares cortos". The Open Book Series . 2 : 293–310. arXiv : 1802.07932 . doi :10.2140/obs.2019.2.293. S2CID  3464567.
22. Hartnett, Kevin (11 de abril de 2019). "Los matemáticos descubren la forma perfecta de multiplicar". Revista Quanta . Consultado el 3 de mayo de 2019 .
23. Harvey, David; van der Hoeven, Joris (2021). "Multiplicación de enteros en tiempo O ( n log ⁡ n ) {\displaystyle O(n\log n)}" (PDF) . Anales de Matemáticas . Segunda serie. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
24. Gilbert, Lachlan (4 de abril de 2019). "Un genio de las matemáticas resuelve un problema de multiplicación de hace 48 años". UNSW . Consultado el 18 de abril de 2019 .
25. Arora, Sanjeev; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno. Cambridge University Press. ISBN 978-0-521-42426-4.
26. Ablayev, F.; Karpinski, M. (2003). "Un límite inferior para la multiplicación de números enteros en programas aleatorios ordenados de una sola lectura" (PDF) . Información y Computación . 186 (1): 78–89. doi :10.1016/S0890-5401(03)00118-4.
27. Knuth, Donald E. (1988), El arte de la programación informática, volumen 2: Algoritmos seminuméricos , Addison-Wesley , págs. 519, 706
28. Duhamel, P.; Vetterli, M. (1990). "Transformadas rápidas de Fourier: una revisión tutorial y un estado del arte" (PDF) . Procesamiento de señales . 19 (4): 259–299 Véase la sección 4.1. doi :10.1016/0165-1684(90)90158-U.
29. Johnson, SG; Frigo, M. (2007). "Una FFT de base dividida modificada con menos operaciones aritméticas" (PDF) . IEEE Trans. Signal Process . 55 (1): 111–9 Véase la Sección IV. Bibcode :2007ITSP...55..111J. doi :10.1109/TSP.2006.882087. S2CID  14772428.
30. von zur Gathen, Joaquín ; Gerhard, Jürgen (1999), Álgebra informática moderna, Cambridge University Press, págs. 243–244, ISBN 978-0-521-64176-0.
31. Castle, Frank (1900). Taller de matemáticas. Londres: MacMillan and Co., pág. 74.

Lectura adicional

• Warren Jr., Henry S. (2013). Hacker's Delight (2.ª edición). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John JG (2018) [2006]. «Técnicas aritméticas avanzadas». quadibloc . Archivado desde el original el 2018-07-03 . Consultado el 2018-07-16 .
• Johansson, Kenny (2008). Cálculos basados ​​en desplazamiento y adición de baja potencia y baja complejidad (PDF) (Tesis de disertación). Linköping Studies in Science and Technology (1.ª ed.). Linköping, Suecia: Departamento de Ingeniería Eléctrica, Universidad de Linköping . ISBN 978-91-7393-836-5. ISSN  0345-7524. Núm. 1201. Archivado (PDF) desde el original el 13 de agosto de 2017. Consultado el 23 de agosto de 2021 .(x+268 páginas)

Enlaces externos

Aritmética básica

• Las múltiples formas de realizar aritmética en las matemáticas cotidianas de la UCSMP
• Una presentación en Powerpoint sobre las matemáticas antiguas
• Vídeo flash sobre multiplicación en red

Algoritmos avanzados

• Algoritmos de multiplicación utilizados por GMP