Algoritmo de multiplicación

Un algoritmo de multiplicación es un algoritmo (o método) para multiplicar dos números. Dependiendo del tamaño de los números, diferentes algoritmos son más eficientes que otros. Los algoritmos de multiplicación eficientes han existido desde la llegada del sistema decimal.

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 como multiplicación larga, a veces llamada multiplicación de escuela primaria, a veces llamada algoritmo estándar: multiplica el multiplicando por cada dígito del multiplicador y luego suma todos los resultados correctamente desplazados. Requiere la memorización de la tabla de multiplicar para un solo dígito.

Este es el algoritmo habitual para multiplicar números grandes a mano en base 10. Una persona que hace multiplicaciones largas en 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 usa multiplicación larga para multiplicar 23,958,233 (multiplicando) por 5,830 (multiplicador) y llega a 139,676,498,390 para el resultado (producto).

 23958233
× 5830
—————————————
00000000 (= 23.958.2233 × 0)
71874699 (= 23.958.2233 × 30)
191665864 (= 23.958.2233 × 800)
+ 119791165 (= 23.958.2233 × 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 en posición horizontal y el cálculo comienza con el primer dígito del multiplicador:

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

El siguiente pseudocódigo describe el proceso de la multiplicación anterior. Mantiene solo una fila para mantener la suma que finalmente se convierte en el resultado. Tenga en cuenta que el '+=' El operador se usa para denotar la suma del valor existente y la operación de almacenamiento (similar a lenguajes como Java y C) para compacidad.

multiplica multiplica multiplica multiplica multiplica multiplica()a[1..p], b[1..q], base) // Óperas que contienen dígitos más correctos 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 transporte = 0 para a_i = 1 a p // para todos los dígitos en un producto[a_i + b_i - 1] += transporte + a[a_i] * b[b_i] transporte = producto[a_i + b_i - 1] / base producto[a_i + b_i - 1] = producto[a_i + b_i - 1] mod base producto[b_i + p] = transporte // último dígito viene de la carga final retorno producto

Uso en ordenadores

Algunos chips implementan la multiplicación larga, en hardware o en microcódigo, para varios tamaños de palabra enteros y de punto flotante. En aritmética de precisión arbitraria, es común usar multiplicaciones largas 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 usando este método, se necesitan alrededor de n² operaciones. De manera más formal, multiplicar números de dos n dígitos mediante una 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 adiciones, 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, 8b sea un entero de máquina representable. Luego se pueden realizar varias adiciones antes de que ocurra un desbordamiento. Cuando el número se vuelve demasiado grande, sumamos parte de él al resultado, o trasladamos y asignamos la parte restante a un número que es menor que b. Este proceso se llama normalización. Richard Brent usó este enfoque en su paquete Fortran, MP.

Las computadoras inicialmente usaban un algoritmo muy similar a la multiplicación larga en base 2, pero los procesadores modernos tienen circuitos optimizados para multiplicaciones rápidas usando algoritmos más eficientes, al precio de una realización de hardware más compleja. En base dos, la multiplicación larga a veces se denomina "cambiar y sumar", porque el algoritmo 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.

En los procesadores disponibles actualmente, una instrucción de desplazamiento bit a bit es más rápida que una instrucción de multiplicación y se puede usar 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 usando una secuencia de cambios y sumas o restas. Por ejemplo, hay varias formas de multiplicar por 10 utilizando solo el desplazamiento de bits y la suma.

(x se hizo realidad 2) + x)
(x  se realizó 3) + (x  se realizó 1) # Aquí 10*x se computó como x*2^3 + x*2

En algunos casos tales secuencias de cambios y adiciones o subtractos superarán los multiplicadores de hardware y especialmente los separadores. Una división por un número de la forma ${displaystyle 2^{n}$ o ${displaystyle 2^{n}pm 1}$ a menudo se puede convertir a una secuencia tan corta.

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. Dichos algoritmos pueden diseñarse para la velocidad, la facilidad de cálculo o el valor educativo, particularmente 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 a menudo se enseña a los alumnos de la escuela primaria o primaria. Ha sido una parte estándar del plan de estudios de matemáticas de la escuela primaria nacional en Inglaterra y Gales desde finales de los años noventa.

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

El cálculo 34 × 13, por ejemplo, podría calcularse usando 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 formando los totales fila por fila (300 + 40) + (90 + 12) = 340 + 102 = 442.

Este enfoque de cálculo (aunque no necesariamente con la disposición de cuadrícula explícita) 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 la cantidad de subproductos se vuelve engorrosa a medida que aumenta la cantidad de dígitos. Sin embargo, se considera un método útil y explícito para introducir la idea de multiplicaciones de varios dígitos; y, en una era 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 necesitarán.

Multiplicación de celosía

En primer lugar, configurar la cuadrícula marcando sus filas y columnas con los números que se multiplican. Luego, rellena las cajas con diez dígitos en los triángulos superiores y dígitos de unidades en la parte inferior.

Finalmente, resumir las vías diagonales y llevar según sea necesario para obtener la respuesta

La multiplicación en celosía, o criba, es algorítmicamente equivalente a la multiplicación larga. Requiere la preparación de una retícula (cuadrícula dibujada en papel) que guía el cálculo y separa todas las multiplicaciones de las sumas. Fue introducido 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 de Enderun en todo el Imperio Otomano. Los huesos de Napier, o varillas de Napier, también utilizaron este método, según lo publicado por Napier en 1617, año de su muerte.

Como se muestra en el ejemplo, el multiplicando y el multiplicador se escriben arriba ya la derecha de un enrejado 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.

• Durante la fase de multiplicación, la rejilla se llena con dos dígitos de los dígitos correspondientes etiquetando cada fila y columna: el dígito de diez va en la esquina superior izquierda.
• Durante la fase de adición, la celosía se resume en las diagonales.
• Por último, si es necesaria una fase de carga, la respuesta que se muestra a lo largo de los lados izquierdo y inferior de la rejilla se convierte en forma normal mediante la carga de diez dígitos como adición o multiplicación larga.

Ejemplo

Las imágenes de la derecha muestran cómo calcular 345 × 12 usando la multiplicación reticular. Como un ejemplo más complicado, considere la siguiente imagen 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 está en el lado derecho. Los productos llenan el enrejado y la suma de esos productos (en la diagonal) está a lo largo de los lados izquierdo e inferior. Luego, esas sumas se suman como se muestra.

 2 3 9 5 8 2 3 3
+---+---+---+---+---+---+---+---+-+-+-
Silencio1 / vidas1 / vidas4 / vidas2 / vidas4 / vidas1 / sufrimiento1 / sufrimiento1 / sufrimiento1
Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / 
01 vidas/ 0 vidas/ 5 vidas/ 5 vidas/ 5 vidas/ 0 sufrimiento/ 0 sufrimiento/ 5 vidas/ 5 vidas
+---+---+---+---+---+---+---+---+-+-+-
Silencio1 / vidas2 / sufrimiento7 / vidas4 / vidas6 / vidas1 / sufrimiento2 / sufrimiento2 / permanecer
Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio 8
02 vidas/ 6 vidas/ 4 vidas/ 2 vidas/ 0 horas/ 4 vidas/ 6 sufrimiento/ 4 vidas/ 4 vidas/ 4 sufrimiento
+---+---+---+---+---+---+---+---+-+-+-
Silencio0 / sufrimiento0 / permanecer2 / permanecer1 / permanecer2 / permanecer0 / permanecer0 / permanecer0 / permanecer0 / permanecer
Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / 
17 vidas/ 6 vidas/ 9 vidas/ 7 vidas/ 5 vidas/ 4 vidas/ 6 sufrimiento/ 9 vidas/ 9 vidas
+---+---+---+---+---+---+---+---+-+-+-
Silencio0 / vidas0 / vidas0 / vidas0 / vidas0 / vidas0 / sufrimiento0 / sufrimiento0 / sufrimiento0 /
Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / Silencio / 
24 horas/ 0 sometida/ 0 sometida/ 0 sometida// 0 sometida// 0 sometida// 0 sometida// 0 sometida/
+---+---+---+---+---+---+---+---+-+-+-
26 15 13 18 17 13 09 00

 01
002
0017
00024
000026
0000015
00013
000000018
0000000017
00000013
000000009
0000000000000
———————————
139676498390

139.676.498.390

Multiplicación campesina rusa

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 requeridas para multiplicaciones largas. El algoritmo estaba en uso en el antiguo Egipto. Sus principales ventajas son que se puede enseñar rápidamente, no requiere memorización y se puede realizar con fichas, como fichas de póquer, si no se dispone de lápiz y papel. La desventaja es que requiere más pasos que una multiplicación larga, por lo que puede ser difícil de manejar para números grandes.

Descripción

En un papel, escriba en una columna los números que obtiene cuando reduce repetidamente a la mitad el multiplicador, ignorando el resto; en una columna a su lado duplicar 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 usa la multiplicación campesina para multiplicar 11 por 3 para llegar a un resultado de 33.

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

Describiendo los pasos explícitamente:

• 11 y 3 están escritos en la parte superior
• 11 es a la mitad (5.5) y 3 se duplica (6). La porción fraccional se descarta (5.5 se convierte en 5).
• 5 es a la mitad (2.5) y 6 se duplica (12). La porción fraccionada se descarta (2.5 se convierte en 2). La figura de la columna izquierda (2) incluso, por lo que la figura en la columna derecha (12) es descartada.
• 2 es a la mitad (1) y 12 se duplica (24).
• Todos los valores no eliminados se resumen: 3 + 6 + 24 = 33.

El método funciona porque la multiplicación es distributiva, así que:

${displaystyle {begin{aligned}3times 11 limit=3times (1times 2^{0}+1times 2^{1}+0times 2^{2}+1times 2^{3})\q=3times (1+2+8)\fn0+3+24\}end{aligned$

Un ejemplo más complicado, usando las cifras de los ejemplos anteriores (23,958,233 y 5,830):

Decimal: binario:
5830 23958233 1011011000110 10110110010110110012915 47916466 101101100011 10110110010110010
1457 95832932 10110001 101101100101100100100
728 191665864 1011011000 1011011001001011011001000364 383331728 101101100 10110110010010110010000182 766663456 10110110 10110110010010110010000091 1533326912 1011011 1011011001011001000000
45 3066653824 101101 10110110010110010000
22 6133307648 10110 10110110010010110010000000011 12266615296 1011 1011011001011001000000
5 24533230592 10110110110010110010000000
2 49066461184 10 1011011001001011001000000000001 98132922368 1 1011011001001011001000000000000————————————— 1022143253354344244353353243222210110 (antes de llevar)
139676498390 100000101010101111000111001110110

Multiplicación de un cuarto de cuadrado

Se pueden multiplicar dos cantidades usando cuartos de cuadrado empleando la siguiente identidad que involucra la función de suelo que algunas fuentes atribuyen a las matemáticas babilónicas (2000–1600 a. C.).

${displaystyle leftlfloor {frac {left(x+yright)}{4}}rightrfloor Está bien.$

Si uno de x+y o x−y es impar, el otro también es impar, por lo que sus cuadrados son 1 mod 4, luego tomar piso reduce ambos en un cuarto; la resta entonces cancela los cuartos, y descartar los restos no introduce ninguna diferencia comparando con la misma expresión sin las funciones suelo. A continuación se muestra una tabla de búsqueda de cuadrados de un cuarto 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, observas que la suma y la diferencia son 12 y 6 respectivamente. Al mirar ambos valores en la tabla, se obtienen 36 y 9, cuya diferencia es 27, que es el producto de 9 y 3.

Antoine Voisin publicó una tabla de cuartos de cuadrado del 1 al 1000 en 1817 como ayuda en la multiplicación. Samuel Laundy publicó una tabla más grande de cuadrados de cuartos de 1 a 100000 en 1856, y una tabla de 1 a 200000 de Joseph Blater en 1888.

Los multiplicadores de un cuarto de cuadrado se usaban en computadoras analógicas 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 usando amplificadores operacionales. El cuadrado de cada uno de estos se aproxima usando circuitos lineales por partes. Finalmente, la diferencia de los dos cuadrados se forma y escala por un factor de un cuarto utilizando otro amplificador operacional.

En 1980, Everett L. Johnson propuso utilizar el método de un cuarto de cuadrado en un multiplicador digital. Para formar el producto de dos números 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 al bien. Para enteros de 8 bits, la tabla de cuartos cuadrados tendrá 2⁹−1=511 entradas (una entrada para el rango completo de 0 a 510 de sumas posibles, las diferencias usando solo las primeras 256 entradas en rango 0..255) o 2⁹−1=511 entradas (usando para diferencias negativas la técnica de 2-complementos y enmascaramiento de 9 bits, que evita probar el signo de las diferencias), siendo cada entrada Ancho de 16 bits (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 son compatibles con un multiplicador de hardware. Charles Putney implementó esto para el 6502.

Complejidad computacional de la multiplicación

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

Actualmente, el algoritmo con la mejor complejidad computacional es un algoritmo 2019 de David Harvey y Joris van der Hoeven, que utiliza las estrategias de uso de transformaciones número-teoréticas introducidas con el algoritmo Schönhage-Strassen para multiplicar números enteros utilizando sólo ${displaystyle O(nlog n)}$ operaciones. Esto se conjetura para ser el mejor algoritmo posible, pero los límites inferiores de ${displaystyle Omega (nlog n)}$ no se conocen.

Multiplicación de Karatsuba

Para los sistemas que necesitan multiplicar números en el rango de varios miles de dígitos, como los sistemas de álgebra computacional y las bibliotecas bignum, la multiplicación larga es demasiado lenta. Estos sistemas pueden emplear la multiplicación de Karatsuba, que fue descubierta en 1960 (publicada en 1962). El corazón del método de Karatsuba radica en la observación de que la multiplicación de dos dígitos se puede hacer con solo tres en lugar de las cuatro multiplicaciones clásicamente requeridas. Este es un ejemplo de lo que ahora se llama un algoritmo divide y vencerás. Supongamos que queremos multiplicar dos números base m de 2 dígitos: x₁ m + x ₂ y y₁ m + y₂:

1. computador x₁ · Sí.₁, llame al resultado F
2. computador x₂ · Sí.₂, llame al resultado G
3. computaciónx₁ + x₂)Sí.₁ + Sí.₂), llame al resultado H
4. computador H − F − G, llame al resultado K; este número es igual a x₁ · Sí.₂ + x₂ · Sí.₁
5. computador F · m² + K · m + G.

Para calcular estos tres productos de números base m, podemos emplear el mismo truco de nuevo, usando efectivamente la recursividad. Una vez que se calculan los números, debemos sumarlos (pasos 4 y 5), lo que requiere alrededor de n operaciones.

La multiplicación de Karatsuba tiene una complejidad temporal de O(n^log₂3) ≈ O(n< sup>1,585), lo que hace que este método sea significativamente más rápido que la multiplicación larga. Debido a la sobrecarga de la recursividad, 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 multiplicaciones largas para valores pequeños de n.

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 y, por lo tanto, puede verse como el punto de partida para la teoría de las multiplicaciones rápidas.

Toom–Cocinar

Otro método de multiplicación se llama Toom-Cook o Toom-3. El método Toom-Cook divide cada número para multiplicarlo 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 hacer una multiplicación de tamaño 3N por el costo de cinco multiplicaciones de tamaño N. Esto acelera la operación por un factor de 9/5, mientras que el método Karatsuba lo acelera por 4/3.

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

Schönhage–Strassen

Demostración de multiplicación 1234 × 5678 = 7006652 utilizando rápidas transformaciones Fourier (FFTs). Se utilizan transformados en número-teoréticos en el modulo 337 de los enteros, seleccionando 85 como 8a raíz de la unidad. Base 10 se utiliza en lugar de base 2^w para fines ilustrativos.

La idea básica de Strassen (1968) es utilizar la multiplicación rápida de polinomios para realizar la multiplicación rápida de enteros. El algoritmo se hizo práctico y las garantías teóricas fueron proporcionadas en 1971 por Schönhage y Strassen, lo que resultó en el algoritmo de Schönhage-Strassen. Los detalles son los siguientes: Elegimos el número entero más grande w que no causará desbordamiento durante el proceso descrito a continuación. Luego dividimos los dos números en grupos m de w bits de la siguiente manera

${displaystyle a=sum _{i=0}{m-1}{a_{i}{wi}{text{ and }b=sum _{j=0}{m-1}{b_{j}2^{wj}}}}}$

Vemos estos números como polinomios en x, donde x = 2^w, para obtener,

${displaystyle a=sum _{i=0}{m-1}{a_{i}{i}{text{ and }b=sum _{j=0}{m-1}{b_{j}x^{j}}}}$

Entonces podemos decir que,

${displaystyle ab=sum - ¿Por qué? ¿Por qué? ¿Qué?$

Claramente, la configuración anterior se realiza mediante la multiplicación de polinomios, de dos polinomios a y b. El paso crucial ahora es usar la multiplicación rápida de polinomios de Fourier para realizar las multiplicaciones anteriores más rápido que en el tiempo ingenuo O(m²).

Para permanecer en el entorno modular de las transformadas de Fourier, buscamos un anillo con una (2m) raíz de unidad. Por lo tanto, hacemos la multiplicación módulo N (y por lo tanto en el anillo Z/NZ). Además, se debe elegir N para que no haya un 'retorno', esencialmente, no se produzcan reducciones del módulo N. Por lo tanto, la elección de N es crucial. Por ejemplo, podría hacerse como,

${displaystyle N=2^{3m}+1.}$

El anillo Z/NZ tendría entonces una raíz (2m)ésima de la unidad, es decir, 8. Además, puede ser comprobado que c_k < N y, por lo tanto, no se producirá ningún ajuste.

El algoritmo tiene una complejidad temporal de Θ(n log(n) log(log(n))) y se utiliza en práctica para números con más de 10.000 a 40.000 dígitos decimales.

Más 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 enteros a n log(n) 2^{Θ(log *(n))} utilizando transformadas de Fourier sobre números complejos. 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. En el contexto del material anterior, lo que estos últimos autores han logrado es encontrar N mucho menor que 2^3k + 1, de modo que < i>Z/NZ tiene una (2m)-ésima raíz de la unidad. Esto acelera el cálculo y reduce la complejidad del tiempo. Sin embargo, estos últimos algoritmos solo son más rápidos que Schönhage-Strassen para entradas imprácticamente grandes.

En 2015, Harvey, Joris van der Hoeven y Lecerf dieron un nuevo algoritmo que logra un tiempo de funcionamiento ${displaystyle O(nlog ncdot 2^{3log ^{*}n}$, haciendo explícita la constante implícita en ${displaystyle O(log ^{*}n)}$ exponente. También propusieron una variante de su algoritmo que logra ${displaystyle O(nlog ncdot 2^{2log ^{*}n}$ pero cuya validez se basa en conjeturas estándar sobre la distribución de los primos Mersenne. En 2016, Covanov y Thomé propusieron un algoritmo de multiplicación entero basado en una generalización de los primos de Fermat que conjetura consigue un límite de complejidad ${displaystyle O(nlog ncdot 2^{2log ^{*}n}$. Esto coincide con el resultado condicional 2015 de Harvey, van der Hoeven y Lecerf pero utiliza un algoritmo diferente y se basa en una conjetura diferente. En 2018, Harvey y van der Hoeven utilizaron un enfoque basado en la existencia de cortos vectores de celo garantizados por el teorema de Minkowski para demostrar una complejidad incondicional ligada a ${displaystyle O(nlog ncdot 2^{2log ^{*}n}$.

En marzo de 2019, David Harvey y Joris van der Hoeven anunciaron el descubrimiento de un O(n log n< /i>) algoritmo de multiplicación. Se publicó en Annals of Mathematics en 2021. Porque Schönhage y Strassen predijeron que n log(n) es el 'mejor resultado posible' Harvey dijo: "... se espera que nuestro trabajo sea el final del camino para este problema, aunque todavía no sabemos cómo demostrarlo con rigor".

El uso de transformadas teóricas de números en lugar de transformadas discretas de Fourier evita problemas de error de redondeo mediante el uso de aritmética modular en lugar de aritmética de punto flotante. Para poder aplicar la factorización que permite que funcione la FFT, la longitud de la transformada debe ser factorizable a números primos pequeños y debe ser un factor de N − 1, donde N es el tamaño del campo. En particular, el cálculo usando un campo de Galois GF(k²), donde k es un primo de Mersenne, permite el uso de una transformada dimensionada para una potencia de 2; p.ej. k = 2³¹ − 1 admite tamaños de transformación de hasta 2³².

Límites inferiores

Hay 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 definido. La multiplicación se encuentra fuera de AC0[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 use AND, OR, NOT y MOD _{Puertas p} que pueden calcular un producto. Esto se sigue de una reducción de profundidad constante de MOD_q a la multiplicación. Los límites inferiores para la multiplicación también se conocen para algunas clases de programas de ramificación.

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

${fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}$

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

k₁ = c · (a + b)

k₂ = a · (d − c)

k₃ = b · (c + d)

Parte real = k₁ − k₃

Parte imaginaria = k₁ + k₂.

Este algoritmo utiliza solo tres multiplicaciones, en lugar de cuatro, y cinco sumas o restas en lugar de dos. Si una multiplicación es más cara que tres sumas o restas, como cuando se calcula a mano, entonces se gana 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 de velocidad. Existe una compensación en el sentido de que puede haber cierta pérdida de precisión al usar el punto flotante.

Para las transformadas rápidas de Fourier (FFT) (o cualquier transformación lineal), las multiplicaciones complejas son por coeficientes constantes c + di (llamados factores de twiddle en FFT), en los que dos de las sumas (d−c y c+d) pueden precalcularse. Por lo tanto, solo se requieren tres multiplicaciones y tres sumas. Sin embargo, intercambiar una multiplicación por una suma de esta manera puede no ser beneficioso con las unidades modernas de punto flotante.

Multiplicación de polinomios

Todos los algoritmos de multiplicación anteriores también se pueden expandir para multiplicar polinomios. Alternativamente, se puede usar la técnica de sustitución de Kronecker para convertir el problema de multiplicar polinomios en una sola multiplicación binaria.

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 -3ab 2
ac -ab 1
———————————————————————
14a2c2 -3a2bc 2ac
-14a2bc 3 a2b2 -2ab
14ac -3ab 2
———————————————————————————————————————————
14a2c2 -17a2bc 16ac 3a2b2 -5ab +2
================================================================================================================================================================================================================================================================

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 usa medidas avoirdupois: 1 t = 20 cwt, 1 cwt = 4 cuartos

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

Primero multiplique los cuartos por 47, el resultado 94 se escribe en el primer espacio de trabajo. Luego, multiplique cwt 12*47 = (2 + 10)*47 pero no sume los resultados parciales (94, 470) todavía. Del mismo modo, multiplique 23 por 47 dando (141, 940). La columna de los cuartos se totaliza 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 coloque el 2 en la respuesta y coloque el 23 en la siguiente columna a la izquierda. Ahora sume las tres entradas en la columna cwt dando 587. Esto es 29 t 7 cwt, así que escriba el 7 en la respuesta y el 29 en la columna de la izquierda. Ahora sume la columna de toneladas. No es necesario realizar ningún ajuste, por lo que el resultado simplemente se copia.

Se puede usar el mismo diseño y métodos para cualquier medida tradicional y monedas no decimales, como el antiguo sistema británico £sd.