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, se utilizan diferentes algoritmos. Han existido algoritmos de multiplicación eficientes desde la llegada del sistema decimal.

Método de cuadrícula

Artículo principal: Multiplicación del 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 en la escuela primaria o la escuela primaria . Ha sido una parte estándar del plan de estudios de matemáticas de la escuela primaria en Inglaterra y Gales desde finales de la década de 1990. ^[1]

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

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

 300 40 90 + 12 ———— 442

×	30	4
10	300	40
3	90	12

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 método de cálculo (aunque no necesariamente con la disposición de cuadrícula explícita) también se conoce como el algoritmo de productos parciales . Su esencia es el cálculo de las multiplicaciones simples por separado, dejando todas las adiciones para la etapa final de recolecció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 considera un método útilmente explícito para introducir la idea de 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 necesitarán.

Multiplicación larga

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

Este es el algoritmo habitual para multiplicar números más grandes a mano en base 10. Las computadoras inicialmente usaban un cambio muy similar y agregan algoritmo en base 2, pero los procesadores modernos tienen circuitos optimizados para multiplicaciones rápidas usando algoritmos más eficientes, al precio de un algoritmo más complejo. realización de hardware. Una persona que haga una multiplicación larga 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 una 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,233 × 0) 71874699 (= 23,958,233 × 30) 191665864 (= 23,958,233 × 800) + 119791165 (= 23,958,233 × 5,000) ——————————————— 139676498390 (= 139,676,498,390)

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

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

Optimización de la complejidad del espacio

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado . ( Septiembre de 2012 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Deje que n es el número total de dígitos en los dos números de entrada en la base D . Si el resultado debe mantenerse en la memoria, entonces la complejidad del espacio es trivialmente Θ ( n ). Sin embargo, en ciertas aplicaciones, no es necesario guardar el resultado completo en la memoria y, en cambio, los dígitos del resultado se pueden transmitir a medida que se calculan (por ejemplo, a la consola del sistema o al archivo). En estos escenarios, la multiplicación larga tiene la ventaja de que se puede formular fácilmente como un algoritmo de espacio logarítmico ; es decir, un algoritmo que solo necesita espacio de trabajo proporcional al logaritmo del número de dígitos en la entrada ( Θ (log  n )). Este es el doblelogaritmo de los números que se multiplican (log log  N ). Tenga en cuenta que los propios operandos aún deben mantenerse en la memoria y su espacio Θ ( n ) no se considera en este análisis.

El método se basa en la observación de que cada dígito del resultado se puede calcular de derecha a izquierda con solo conocer el acarreo del paso anterior. Deja un _i y b _i ser el i dígitos -ésima del operando, con una y b rellena por la izquierda por ceros para ser de longitud n , r _i ser el i dígitos -ésima del resultado y c _i ser el acarreo generado para r _i (i = 1 es el dígito más a la derecha) entonces

${\displaystyle {\begin{aligned}r_{i}&=\left(c_{i-1}+\sum _{j+k=i+1}a_{j}b_{k}\right)\mod D\\c_{i}&=\left\lfloor (c_{i-1}+\sum _{j+k=i}a_{j}b_{k})/D\right\rfloor \\c_{0}&=0\end{aligned}}}$

o

${\displaystyle c_{i}=\left(\sum _{m=0}^{i-2}\sum _{j+k=i-m}a_{j}b_{k}\right)/D.}$

Un simple argumento inductivo muestra que el acarreo nunca puede exceder n y la suma total de r _i nunca puede exceder D * n : el acarreo en la primera columna es cero, y para todas las demás columnas, hay como máximo n dígitos en la columna , y un acarreo de como máximo n de la columna anterior (por la hipótesis de inducción). La suma es como máximo D * n , y el acarreo a la siguiente columna es como máximo D * n / D , on . Por tanto, ambos valores se pueden almacenar en dígitos O (log n ).

En pseudocódigo, el algoritmo de espacio de registro es:

multiplicar ( una [ 1 .. P ] ,  b [ 1 .. Q ] ,  de base )  // Operandos contienen dígitos de la derecha en el índice 1  tot  =  0  para  ri  =  1  a  p  +  q  -  1  // para cada dígito del resultado  para  bi  =  MAX ( 1 ,  ri  -  p  +  1 )  a  MIN ( ri ,  q ) // Dígitos de b que deben considerarse  ai  =  ri  -  bi  +  1  // Dígitos de una "simetría" de seguimiento  tot  =  tot  +  ( a [ ai ]  *  b [ bi ])  producto [ ri ]  =  tot  mod  base  tot  =  piso ( tot  /  base de )  producto [ p + q ]  =  tot  mod  base de // El último dígito del resultado proviene del último  producto de devolución de  acarreo

Uso en computadoras

Algunos chips implementan multiplicaciones largas, en hardware o en microcódigo , para varios tamaños de palabras enteras y de coma 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 usando este método, se necesitan aproximadamente n ² operaciones. Más formalmente: usando una métrica de tamaño natural de número de dígitos, la complejidad temporal de multiplicar dos números de n dígitos usando la multiplicación larga es Θ ( n ² ).

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, 8 b es un número entero de máquina representable. Luego se pueden realizar varias adiciones 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 a un número menor que b . Este proceso se llama normalización . Richard Brent utilizó este enfoque en su paquete Fortran, MP. ^[2]

Multiplicación de celosía

Artículo principal: multiplicación de celosía

Primero, configure la cuadrícula marcando sus filas y columnas con los números que se van a multiplicar. Luego, complete las casillas con dígitos de decenas en los triángulos superiores y dígitos de unidades en la parte inferior.

Finalmente, sume a lo largo de los tractos diagonales y lleve según sea necesario para obtener la respuesta

La multiplicación en celosía o tamiz es algorítmicamente equivalente a la multiplicación larga. Requiere la preparación de una celosía (una 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 Fibonacci 's Liber Abaci . 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. ^[3] Huesos de Napier o varas de Napier También utilizó 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 y a la derecha de una celosía o un tamiz. Se encuentra en "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, el enrejado 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 que se muestra a lo largo de los lados izquierdo e inferior del enrejado se convierte a la forma normal llevando los dígitos de diez como una suma larga o una multiplicación.

Ejemplo

Las imágenes de la derecha muestran cómo calcular 345 × 12 usando la multiplicación de celosía. Como 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á a lo largo de la parte superior de la celosía y 5,830 está a lo largo del lado derecho. Los productos llenan la celosía y la suma de esos productos (en la diagonal) está a lo largo de los lados izquierdo e inferior. Entonces esas sumas se suman como se muestra.

2 3 9 5 8 2 3 3 + --- + --- + --- + --- + --- + --- + --- + --- + - | 1 / | 1 / | 4 / | 2 / | 4 / | 1 / | 1 / | 1 / | | / | / | / | / | / | / | / | / | 5 01 | / 0 | / 5 | / 5 | / 5 | / 0 | / 0 | / 5 | / 5 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 1 / | 2 / | 7 / | 4 / | 6 / | 1 / | 2 / | 2 / | | / | / | / | / | / | / | / | / | 8 02 | / 6 | / 4 | / 2 | / 0 | / 4 | / 6 | / 4 | / 4 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 0 / | 0 / | 2 / | 1 / | 2 / | 0 / | 0 / | 0 / | | / | / | / | / | / | / | / | / | 3 17 | / 6 | / 9 | / 7 | / 5 | / 4 | / 6 | / 9 | / 9 | + --- + --- + --- + --- + --- + --- + --- + --- + - | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | 0 / | | / | / | / | / | / | / | / | / | 0 24 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | / 0 | + --- + --- + --- + --- + --- + --- + --- + --- + - 26 15 13 18 17 13 09 00

01 002 0017 00024 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390

= 139,676,498,390

Multiplicación binaria o campesina

Artículo principal: multiplicación campesina

El método binario también se conoce como multiplicación campesina, porque ha sido ampliamente utilizado por personas que están clasificadas como campesinas y, por lo tanto, no han memorizado las tablas de multiplicar necesarias para una multiplicación larga. ^{[4] [ verificación fallida ]} El algoritmo estaba en uso en el antiguo Egipto. ^{[5] [6]} 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 papel y lápiz. La desventaja es que requiere más pasos que una multiplicación larga, por lo que puede resultar difícil de manejar para números grandes.

Descripción

En papel, escriba en una columna los números que obtiene cuando reduce a la mitad repetidamente 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 usa la multiplicación campesina para multiplicar 11 por 3 para 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 fracción fraccionada se descarta (5,5 se convierte en 5).
• 5 se reduce a la mitad (2,5) y 6 se duplica (12). La porción fraccionaria se descarta (2,5 se convierte en 2). La cifra de la columna de la izquierda (2) es par , por lo que la cifra de la columna de la derecha (12) se descarta.
• 2 se reduce a la mitad (1) y 12 se duplica (24).
• Todos los valores no tachados se suman: 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, usando las cifras de los ejemplos anteriores (23,958,233 y 5,830):

Decimal: Binario:5830 23958233 1011011000110 10110110110010010110110012915 47916466 101101100011 101101101100100101101100101457 95832932 10110110001 101101101100100101101100100728 191665,864 mil 1011011000 1011011011001001011011001000
364 383 331 728 101 101 100 10110110110010010110110010000
182 766 663 456 10110110 10110110110010010110110010000091 1533326912 1011011 101101101100100101101100100000045 3066653824 101101 1011011011001001011011001000000022 6133307648 10110 10110110110010010110110010000000011 12266615296 1011 10110110110010010110110010000000005 24533230592 101 101101101100100101101100100000000002 49066461184 10 101101101100100101101100100000000000
1 98132922368 1 1011011011001001011011001000000000000 ———————————— 1022143253354344244353353243222210110 (antes del transporte) 139676498390 10000010000101010111100011100111010110

Multiplicación binaria en computadoras

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado . ( Enero de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Esta es una variación de la multiplicación campesina.

En base 2, la multiplicación larga se reduce a una operación casi trivial. Para cada bit '1' en el multiplicador , cambie el multiplicando por una cantidad adecuada y luego sume los valores desplazados. En algunos procesadores , es más rápido usar cambios de bits y adiciones en lugar de instrucciones de multiplicación, especialmente si el multiplicador es pequeño o siempre es el mismo.

Cambiar y agregar

Históricamente, las computadoras usaban un algoritmo de "cambiar y agregar" para multiplicar números enteros pequeños. Tanto la multiplicación larga en base 2 como la multiplicación campesina en base 2 se reducen a este mismo algoritmo. En base 2, multiplicar por un solo dígito del multiplicador se reduce a una serie simple de operaciones lógicas AND . Cada producto parcial se agrega a una suma acumulada tan pronto como se calcula cada producto parcial. La mayoría de los microprocesadores actualmente disponibles implementan este u otros algoritmos similares (como la codificación de Booth ) para varios tamaños 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 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 usando una secuencia de cambios 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 cambios 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 o, a menudo, se puede convertir en una secuencia tan corta.${\displaystyle 2^{n}}$${\displaystyle 2^{n}\pm 1}$

Estos tipos de secuencias deben usarse siempre para computadoras que no tienen una instrucción de "multiplicar", ^[7] y también pueden usarse por extensión a números de coma flotante si se reemplazan los cambios con el cálculo de 2 * x como x + x , ya que son lógicamente equivalentes.

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 piso que algunas fuentes ^{[8] [9]} atribuyen a las matemáticas babilónicas (2000-1600 aC).

${\displaystyle \left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(x-y\right)^{2}}{4}}\right\rfloor ={\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.}$

Si uno de x + y y x - y es impar, el otro también es impar; esto significa que las fracciones, si las hay, se cancelarán y descartar los restos no introduce ningún error. 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 .

norte	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	dieciséis	17	18
⌊ n 2 / 4⌋	0	0	1	2	4	6	9	12	dieciséis	20	25	30	36	42	49	56	64	72	81

Si, por ejemplo, quisiera multiplicar 9 por 3, observa que la suma y la diferencia son 12 y 6 respectivamente. Al buscar 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 para la multiplicación. Samuel Laundy publicó en 1856 una tabla más grande de cuartos cuadrados de 1 a 100000, ^[10] y una tabla de 1 a 200000 por Joseph Blater en 1888. ^[11]

Los multiplicadores de un cuarto de cuadrado se utilizaron 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 utilizando amplificadores operacionales . El cuadrado de cada uno de estos se aproxima utilizando 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 . ^[12] 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 a la derecha. Para enteros de 8 bits, la tabla de cuartos cuadrados tendrá 2 ⁹ -1 = 511 entradas (una entrada para el rango completo 0..510 de posibles sumas, las diferencias usando solo las primeras 256 entradas en el rango 0..255) o 2 ⁹-1 = 511 entradas (utilizando 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 de 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 también ha beneficiado a los sistemas de 8 bits que no tienen soporte para un multiplicador de hardware. Charles Putney implementó esto para el 6502 . ^[13]

Algoritmos de multiplicación rápida para entradas grandes

Problema no resuelto 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)

Algoritmo de multiplicación complejo

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}}}$

Pero hay una forma de reducir el número de multiplicaciones a tres. ^[14]

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 hay una ganancia de velocidad. En las computadoras modernas, una multiplicación y una adición pueden tardar 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 cuando se usa el punto flotante.

Para transformadas rápidas de Fourier (FFT) (o cualquier transformación lineal ) las multiplicaciones complejas son por coeficientes constantes c  +  di (llamado factores de rotación en FFT), en cuyo caso dos de las adiciones ( d - c y c + d ) pueden ser precalculadas . Por lo tanto, solo se requieren tres multiplicaciones y tres sumas. ^[15] Sin embargo, cambiar una multiplicación por una adición de esta manera puede que ya no sea beneficioso con las unidades modernas de punto flotante . ^[dieciséis]

Multiplicación de Karatsuba

Artículo principal: algoritmo de Karatsuba

Para los sistemas que necesitan multiplicar números en el rango de varios miles de dígitos, como los sistemas de álgebra computarizada y las bibliotecas de 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 sólo tres en lugar de las cuatro multiplicaciones clásicamente requeridas. Este es un ejemplo de lo que ahora se llama algoritmo de divide y vencerás . Supongamos que queremos multiplicar dos números de base m de 2 dígitos : x ₁ m + x ₂ y y ₁m + y ₂ :

1. calcular x ₁ · y ₁ , llamar al resultado F
2. calcular x ₂ · y ₂ , llamar al resultado G
3. calcular ( x ₁ + x ₂ ) · ( y ₁ + y ₂ ), llamar al resultado H
4. calcular H - F - G , llamar al resultado K ; este número es igual ax ₁ · y ₂ + x ₂ · y ₁
5. Calcular F · m ² + K · m + G .

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

La multiplicación de Karatsuba tiene una complejidad temporal de O ( n ^{log ₂ 3} ) ≈ O ( n ^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 la multiplicación larga 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, ^[17] y por lo tanto puede verse como el punto de partida para la teoría de multiplicaciones rápidas.

En 1963, Peter Ungar sugirió establecer m en i para obtener una reducción similar en el algoritmo de multiplicación compleja. ^[14] Para multiplicar ( a  +  bi ) · ( c  +  di ), sigue estos pasos:

1. calcular b · d , llamar al resultado F
2. calcular a · c , llamar al resultado G
3. calcular ( a + b ) · ( c + d ), llamar al resultado H
4. la parte imaginaria del resultado es K = H - F - G = a · d + b · c
5. la parte real del resultado es G - F = a · c - b · d

Al igual que el algoritmo de la sección anterior, esto requiere tres multiplicaciones y cinco sumas o restas.

Toom – Cook

Artículo principal: Multiplicación de Toom-Cook

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 en un factor de 9/5, mientras que el método Karatsuba la acelera en 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 adiciones y la gestión de dígitos también aumenta. Por esta razón, el método de las transformadas de Fourier es típicamente 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.

Métodos de transformada de Fourier

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

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

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

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

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

Entonces podemos decir que,

${\displaystyle ab=\sum _{i=0}^{m-1}\sum _{j=0}^{m-1}a_{i}b_{j}x^{(i+j)}=\sum _{k=0}^{2m-2}c_{k}x^{k}.}$

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

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

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

Por tanto, el anillo Z / NZ tendría una raíz de la unidad (2 m ), es decir, 8. Además, se puede comprobar que c _k < N y, por tanto, no se producirá ningún rodeo.

El algoritmo tiene una complejidad de tiempo de Θ ( n  log ( n ) log (log ( n ))) y se usa en la práctica para números con más de 10,000 a 40,000 dígitos decimales. En 2007 esto fue mejorado por Martin Fürer ( algoritmo de Fürer ) ^[19] para dar una complejidad de tiempo de n  log ( n ) 2 ^{Θ ( log * ( n ))} usando transformadas de Fourier sobre números complejos. Anindya De, Chandan Saha, Piyush Kurur y Ramprasad Saptharishi ^[20] dieron un algoritmo similar usando aritmética modularen 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 menos que 2 ^{3 k} + 1, de modo que Z / NZ tiene una raíz de unidad (2 m ). 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 de gran tamaño que no son prácticas.

En marzo de 2019, David Harvey y Joris van der Hoeven ( de ) publicaron un artículo que describe un algoritmo de multiplicación O ( n log n ) . ^{[21] [22] [23] [24]}

El uso de transformadas teóricas de números en lugar de transformadas discretas de Fourier evita problemas de error de redondeo al usar aritmética modular en lugar de aritmética de punto flotante. Para aplicar la factorización que permite que funcione la FFT, la longitud de la transformada debe ser factorizable en pequeños números primos 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 número primo de Mersenne , permite el uso de una transformada dimensionada a una potencia de 2; por ejemplo, k = 2 ³¹ - 1admite 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 las máquinas convencionales, es decir, en las máquinas equivalentes de Turing) ni se conoce ningún límite inferior más nítido. La multiplicación se encuentra fuera de AC 0 [ p ] para cualquier primo p , lo que significa que no hay una familia de circuitos de tamaño polinomial (o incluso subexponencial) de profundidad constante que utilicen compuertas AND, OR, NOT y MOD _p que puedan calcular un producto. Esto se sigue de una reducción de profundidad constante de MOD _q a una multiplicación. ^[25] Los límites inferiores para la multiplicación también se conocen para algunas clases deprogramas de ramificación . ^[26]

Multiplicación de polinomios

Todos los algoritmos de multiplicación anteriores también se pueden expandir para multiplicar polinomios . Por ejemplo, el algoritmo de Strassen puede usarse para la multiplicación de polinomios ^[27] Alternativamente, la técnica de sustitución de Kronecker puede usarse para convertir el problema de multiplicar polinomios en una sola multiplicación binaria. ^[28]

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 ———————————————————— 14a 2 c 2 -3a 2 bc 2ac -14a 2 bc 3 a 2 b 2 -2ab 14ac -3ab 2 —————————————————————————————————————— 14a 2 c 2 -17a 2 bc 16ac 3a 2 b 2 -5ab +2 ======================================= [29]

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 qtr.

 t cwt qtr 23 12 2 47 veces ———————————————— 141 94 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. Asimismo, multiplique 23 por 47 dando (141, 940). La columna de cuartos se suma 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 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 hay que hacer ningún ajuste, por lo que el resultado simplemente se copia.

El mismo diseño y métodos se pueden utilizar para cualquier medida tradicional y monedas no decimales, como el antiguo sistema de libras esterlinas británicas .

Ver también

• Multiplicador binario
• Algoritmo de división
• Logaritmo
• Cálculo mental
• Prostaphaeresis
• Regla de cálculo
• Sistema de Trachtenberg
• Esquema de Horner para evaluar un polinomio
• Sistema de números de residuos § Multiplicación para otro algoritmo de multiplicación rápida, especialmente eficiente cuando muchas operaciones se realizan en secuencia, como en álgebra lineal
• Multiplicador de papá
• Árbol de Wallace

Referencias

1. Gary Eason, Regreso a la escuela para padres , BBC News , 13 de febrero de 2000
   Rob Eastaway , Por qué los padres no pueden hacer matemáticas hoy , BBC News , 10 de septiembre de 2010
2. Brent, Richard P (marzo de 1978). "Un paquete aritmético de precisión múltiple de Fortran". Transacciones ACM en software matemático . 4 : 57–70. CiteSeerX  10.1.1.117.8425 . doi : 10.1145 / 355769.355775 . S2CID  8875817 .
3. Corlu, MS, Burlbaw, LM, Capraro, RM, Corlu, MA y 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), págs. 19–31.
4. Bogomolny, Alexander . "Multiplicación campesina" . www.cut-the-knot.org . Consultado el 4 de noviembre de 2017 .
5. D. Wells (1987). El diccionario de pingüinos de números curiosos e interesantes . Libros de pingüinos. pag. 44.
6. Cool Multiplication Math Trick , consultado el 14 de marzo de 2020
7. "Nuevos métodos de multiplicación y división de enteros" por G. Reichborn-Kjennerud
8. McFarland, David (2007), tablas de cuartos revisadas: tablas anteriores, división del trabajo en la construcción de tablas e implementaciones posteriores en computadoras analógicas , p. 1
9. Robson, Eleanor (2008). Matemáticas en el antiguo Iraq: una historia social . pag. 227. ISBN 978-0691091822.
10. "Reseñas" , El ingeniero civil y el diario del arquitecto : 54–55, 1857.
11. Holmes, Neville (2003), "Multiplicar con cuartos cuadrados", The Mathematical Gazette , 87 (509): 296-299, doi : 10.1017 / S0025557200172778 , JSTOR 3621048 . 
12. Everett L., Johnson (marzo de 1980), "A Digital Quarter Square Multiplier", IEEE Transactions on Computers , Washington, DC, EE. UU .: IEEE Computer Society, C-29 (3), págs. 258-261, doi : 10.1109 /TC.1980.1675558 , ISSN 0018-9340 , S2CID 24813486  
13. Putney, Charles (marzo de 1986), "Multiplicación 6502 más rápida hasta ahora" , Línea de montaje de Apple , 6 (6)
14. Knuth, Donald E. (1988), El arte de la programación informática, volumen 2: Algoritmos seminuméricos , Addison-Wesley , págs. 519, 706
15. P. Duhamel y M. Vetterli, Fast Fourier Transforms: A tutorial review and a state of the art " Archivado el 29 de mayo de 2014 en Wayback Machine , Signal Processing vol. 19, págs. 259-299 (1990), sección 4.1.
16. SG Johnson y M. Frigo, " Una FFT de base dividida modificada con menos operaciones aritméticas ", IEEE Trans. Proceso de señal. vol. 55, págs. 111-119 (2007), sección IV.
17. D. Knuth, El arte de la programación informática , vol. 2 segundos. 4.3.3 (1998)
18. A. Schönhage y V. Strassen, "Schnelle Multiplikation großer Zahlen", Computación 7 (1971), págs. 281-292.
19. Fürer, M. (2007). " Multiplicación de enteros más rápida " en las actas del trigésimo noveno simposio anual de ACM sobre teoría de la computación, del 11 al 13 de junio de 2007, San Diego, California, EE. UU.
20. Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Multiplicación rápida de enteros mediante aritmética modular. Simposio de Teoría de la Computación (STOC) 2008.
21. David Harvey, Joris Van Der Hoeven. Multiplicación de enteros en el tiempo O ( n log n ) . 2019. ffhal-02070778
22. KWRegan (29 de marzo de 2019). "Multiplicación de enteros en tiempo NlogN" . Letra perdida de Gödel y P = NP . Consultado el 3 de mayo de 2019 .
23. Hartnett, Kevin. "Los matemáticos descubren la manera perfecta de multiplicar" . Revista Quanta . Consultado el 3 de mayo de 2019 .
24. Harvey, David. "Multiplicación de enteros en el tiempo O ( n log n ) " .
25. Sanjeev Arora y Boaz Barak, Complejidad computacional: un enfoque moderno , Cambridge University Press, 2009.
26. Farid Ablayev y Marek Karpinski, Un límite inferior para la multiplicación de enteros en programas de ramificación ordenados aleatorios de lectura única , Información y Computación 186 (2003), 78-89.
27. "Algoritmo de Strassen para la multiplicación de polinomios" . Todo 2.
28. von zur Gathen, Joachim ; Gerhard, Jürgen (1999), Álgebra informática moderna , Cambridge University Press, págs. 243–244, ISBN 978-0-521-64176-0.
29. Castillo, Frank (1900). Taller de Matemáticas . Londres: MacMillan and Co. p. 74 .

Lectura adicional

• Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). 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 3 de julio de 2018 . Consultado el 16 de julio de 2018 .

Enlaces externos

Aritmética básica

• Las muchas formas de aritmética en UCSMP Everyday Mathematics
• Una presentación de Powerpoint sobre las matemáticas antiguas
• Video Flash de multiplicación de celosía

Algoritmos avanzados

• Algoritmos de multiplicación utilizados por GMP