Algoritmo de multiplicación - Multiplication algorithm

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

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.

Ambos factores se dividen ("divididos") en sus partes de centenas, decenas y unidades, y los productos de las partes se calculan luego 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:

×	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 enfoque 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.

multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product

Optimización de la complejidad del espacio

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 su lugar, 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 doble logaritmo 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 {alineado} 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 {alineado}}}

o

{\ Displaystyle c_ {i} = \ left (\ sum _ {m = 0} ^ {i-2} \ sum _ {j + k = im} 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:

multiply(a[1..p], b[1..q], base)                  // Operands containing rightmost digits at index 1
    tot = 0
    for ri = 1 to p + q - 1                       // For each digit of result
        for bi = MAX(1, ri - p + 1) to MIN(ri, q) // Digits from b that need to be considered
            ai = ri − bi + 1                      // Digits from a follow "symmetry"
            tot = tot + (a[ai] * b[bi])
        product[ri] = tot mod base
        tot = floor(tot / base)
    product[p+q] = tot mod base                   // Last digit of the result comes from last carry
    return product

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. A continuación, 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.

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. Los huesos de Napier , o las varillas de Napier, también utilizaron este método, según lo publicado por Napier en 1617, el 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.

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 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á 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

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

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

Decimal:     Binary:
11   3       1011  11
5    6       101  110
2   12       10  1100
1   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 {alineado} 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 {alineado}}}

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

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

Multiplicación binaria en computadoras

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 # Here 10*x is computed as (x*2^2 + x)*2
(x << 3) + (x << 1) # Here 10*x is computed as 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 "multiplicar", y también pueden usarse por extensión a números de punto flotante si se reemplazan los cambios con el cálculo de 2 * x como x + x , ya que estos son lógicamente equivalentes.

Multiplicación de cuartos cuadrados

Se pueden multiplicar dos cantidades usando cuartos de cuadrado empleando la siguiente identidad que involucra la función de piso que algunas fuentes 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 (xy \ 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, por lo que sus cuadrados son 1 mod 4, entonces tomar la palabra reduce ambos en un cuarto; la resta luego anula los trimestres y descartar los remanentes no introduce ninguna diferencia comparando con la misma expresión sin las funciones de piso. 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 \times 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ó una tabla más grande de cuartos cuadrados del 1 al 100000 en 1856, y una tabla del 1 al 200000 por Joseph Blater en 1888.

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 . 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 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, por diferencias negativas de la técnica de 2-complementos y enmascaramiento de 9 bits, lo que evita probar el signo de las diferencias), siendo cada entrada de 16 bits de ancho (los valores de entrada son a partir 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 .

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) (do + 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.

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. Sin embargo, cambiar una multiplicación por una suma de esta manera puede que ya no sea beneficioso con las unidades modernas de punto flotante .

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 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 base- m de 2 dígitos : x ₁m + x ₂ y y ₁m + y ₂ :

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

Para calcular estos tres productos de números de base m , podemos emplear el mismo truco nuevamente, usando 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 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. Para multiplicar ( a + bi ) · ( c + di ), siga estos pasos:

calcular b · d , llamar al resultado F
calcular a · c , llamar al resultado G
calcular ( a + b ) · ( c + d ), llamar al resultado H
la parte imaginaria del resultado es K = H - F - G = a · d + b · c
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

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 . 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 {y}} 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 {y}} 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.}

El anillo Z / NZ tendría, por tanto, 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 ) 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 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 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 publicaron un artículo que describe un algoritmo de multiplicación O ( n log n ) .

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 ³¹ - 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 se conoce ningún límite inferior más nítido. La multiplicación se encuentra fuera de AC ⁰ [ 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. Los límites inferiores para la multiplicación también se conocen para algunas clases de programas de ramificación .

Multiplicación de polinomios

Todos los algoritmos de multiplicación anteriores también se pueden expandir para multiplicar polinomios . Por ejemplo, se puede utilizar el algoritmo de Strassen para la multiplicación de 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.

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

 14ac - 3ab + 2 multiplied by ac - ab + 1

 14ac  -3ab   2
   ac   -ab   1
 ————————————————————
 14a²c²  -3a²bc   2ac
        -14a²bc         3 a²b²  -2ab
                 14ac           -3ab   2
 ———————————————————————————————————————
 14a²c² -17a²bc   16ac  3a²b²    -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 qtr.

    t    cwt  qtr
   23     12    2
               47 x
 ————————————————
  141     94   94
  940    470
   29     23
 ————————————————
 1110    587   94
 ————————————————
 1110      7    2
 =================  Answer: 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

Otras lecturas

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 .
Johansson, Kenny. Cálculos basados en Shift-and-Add de baja potencia y baja complejidad (PDF) (Tesis de disertación). Estudios de Linköping en ciencia y tecnología (1 ed.). Linköping, Suecia: Departamento de Ingeniería Eléctrica, Universidad de Linköping . ISBN 978-91-7393-836-5. ISSN 0345-7524 . No. 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

Algoritmos avanzados

Algoritmos de multiplicación utilizados por GMP

Languages

In other projects

Algoritmo de multiplicación - Multiplication algorithm

Contenido

Método de cuadrícula

Multiplicación larga

Ejemplo

Optimización de la complejidad del espacio

Uso en computadoras

Multiplicación de celosía

Ejemplo

Multiplicación binaria o campesina

Descripción

Ejemplos de

Multiplicación binaria en computadoras

Cambiar y agregar

Multiplicación de cuartos cuadrados

Algoritmos de multiplicación rápida para entradas grandes

Algoritmo de multiplicación complejo

Multiplicación de Karatsuba

Toom – Cook

Métodos de transformada de Fourier

Límites inferiores

Multiplicación de polinomios

Ver también

Referencias

Otras lecturas

enlaces externos

Aritmética básica

Algoritmos avanzados