Algoritmos de multiplicação

Este exemplo utiliza a multiplicação longa para multiplicar 23.958.233 (multiplicando) por 5.830 (multiplicador) e chega a 139.676.498.390 como resultado (produto).

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

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

multiply(a[1..p], b[1..q], base)                             // Operandos contendo os dígitos mais à direita no índice 1
  product = [1..p+q]                                         // Alocar espaço para o resultado
  for b_i = 1 to q                                           // para todos os dígitos em b
    carry = 0
    for a_i = 1 to p                                         // para todos os dígitos em 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                                 // o último dígito provém do transporte final (carry)
  return product

Alguns chips implementam a multiplicação longa, em hardware ou em microcódigo, para vários tamanhos de palavras inteiras e de vírgula flutuante. Na aritmética de precisão arbitrária, é comum utilizar a multiplicação longa com a base definida para 2^w, onde w é o número de bits numa palavra, para multiplicar números relativamente pequenos. Para multiplicar dois números com n dígitos utilizando este método, são necessárias cerca de n² operações. Mais formalmente, multiplicar dois números de n dígitos utilizando a multiplicação longa requer ${\displaystyle \Theta (n^{2})}$ operações de um único dígito (adições e multiplicações).

Quando implementados em software, os algoritmos de multiplicação longa têm de lidar com o overflow (transbordo) durante as adições, o que pode ser computacionalmente dispendioso. Uma solução típica é representar o número numa base pequena, b, de modo que, por exemplo, 8b seja um número inteiro de máquina representável. Desta forma, várias adições podem ser efetuadas antes de ocorrer um overflow. Quando o número se torna demasiado grande, adicionamos uma parte dele ao resultado, ou transportamos (carry) e mapeamos a parte restante de volta para um número inferior a b. Este processo é chamado de normalização. Richard Brent usou esta abordagem no seu pacote Fortran, MP.^[2]

Os computadores usaram inicialmente um algoritmo muito semelhante à multiplicação longa na base 2, mas os processadores modernos têm circuitos otimizados para multiplicações rápidas usando algoritmos mais eficientes, ao custo de uma implementação de hardware mais complexa.^{[carece de fontes?]} Na base dois, a multiplicação longa é por vezes chamada de "deslocar e adicionar" (shift and add), porque o algoritmo simplifica-se e consiste apenas em deslocar para a esquerda (multiplicar por potências de dois) e adicionar. A maioria dos microprocessadores atualmente disponíveis implementa este ou outros algoritmos semelhantes (como o algoritmo de Booth) para vários tamanhos de inteiros e de vírgula flutuante em multiplicadores de hardware ou em microcódigo.

Nos processadores atualmente disponíveis, uma instrução de deslocamento bit a bit (bit-wise shift) é geralmente (mas não sempre) mais rápida do que uma instrução de multiplicação e pode ser usada para multiplicar (deslocamento para a esquerda) e dividir (deslocamento para a direita) por potências de dois. A multiplicação por uma constante e a divisão por uma constante podem ser implementadas através de uma sequência de deslocamentos e adições ou subtrações. Por exemplo, existem várias maneiras de multiplicar por 10 usando apenas deslocamento de bits e adição.

 ((x << 2) + x) << 1 # Aqui 10*x é calculado como (x*2^2 + x)*2
 (x << 3) + (x << 1) # Aqui 10*x é calculado como x*2^3 + x*2

Nalguns casos, tais sequências de deslocamentos e adições ou subtrações terão um desempenho superior ao dos multiplicadores e, especialmente, aos dos divisores de hardware. Uma divisão por um número da forma ${\displaystyle 2^{n}}$ ou ${\displaystyle 2^{n}\pm 1}$ pode, muitas vezes, ser convertida para uma dessas sequências curtas.

O método da grelha (ou método da caixa) é um método introdutório para multiplicações de vários dígitos que é frequentemente ensinado a alunos no ensino primário ou na escola primária. Tem feito parte integrante do currículo nacional de matemática do ensino primário em Inglaterra e no País de Gales desde o final da década de 1990.^[3]

Ambos os fatores são divididos ("particionados") nas suas partes de centenas, dezenas e unidades, e os produtos das partes são então calculados explicitamente numa etapa relativamente simples apenas de multiplicação, antes de estas contribuições serem totalizadas para dar a resposta final numa etapa de adição separada.

O cálculo de 34 × 13, por exemplo, poderia ser efetuado utilizando a grelha:

  300
   40
   90
 + 12
 ————
  442

seguido da adição para obter 442, seja numa única soma (ver à direita), ou formando os totais linha a linha

${\displaystyle (300+40)+(90+12)=340+102=442.}$

Esta abordagem de cálculo (embora não necessariamente com a disposição explícita da grelha) também é conhecida como o algoritmo dos produtos parciais. A sua essência é o cálculo das multiplicações simples separadamente, com toda a adição a ser deixada para a etapa final de agrupamento.

Em princípio, o método da grelha pode ser aplicado a fatores de qualquer tamanho, embora o número de subprodutos se torne muito extenso à medida que o número de dígitos aumenta. Não obstante, é visto como um método explicitamente útil para introduzir a ideia das multiplicações de múltiplos dígitos; e, numa era em que a maioria dos cálculos de multiplicação é feita com recurso a uma calculadora ou a uma folha de cálculo, poderá na prática ser o único algoritmo de multiplicação de que alguns alunos precisarão alguma vez.

A multiplicação em treliça (lattice), ou em gelosia (sieve), é algoritmicamente equivalente à multiplicação longa. Requer a preparação de uma treliça (uma grelha desenhada em papel) que orienta o cálculo e separa todas as multiplicações das adições. Foi introduzida na Europa em 1202 no livro Liber Abaci de Fibonacci. Fibonacci descreveu a operação como sendo mental, usando as mãos direita e esquerda para carregar os cálculos intermédios. Matrakçı Nasuh apresentou 6 variantes diferentes deste método no seu livro do século XVI, Umdet-ul Hisab. Era amplamente utilizado nas escolas do Enderun por todo o Império Otomano.^[4] Os Ossos de Napier, ou Barras de Napier, também usavam este método, tal como publicado por Napier em 1617, ano da sua morte.

Como demonstrado no exemplo, o multiplicando e o multiplicador são escritos por cima e à direita de uma treliça, ou gelosia. Encontra-se na "Aritmética" de Muhammad ibn Musa al-Khwarizmi, uma das fontes de Leonardo mencionadas por Sigler, autor de "Fibonacci's Liber Abaci", 2002.^{[carece de fontes?]}

• Durante a fase de multiplicação, a treliça é preenchida com produtos de dois dígitos dos dígitos correspondentes que rotulam cada linha e coluna: o dígito das dezenas vai para o canto superior esquerdo.
• Durante a fase de adição, a treliça é somada nas diagonais.
• Por fim, se for necessária uma fase de transporte (carry), a resposta, tal como apresentada ao longo dos lados esquerdo e inferior da treliça, é convertida para a forma normal transportando os dígitos das dezenas como na adição ou na multiplicação longa.

     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

O método binário também é conhecido como multiplicação camponesa (ou russa), pois tem sido muito utilizado por pessoas classificadas como camponesas que, desse modo, não memorizaram as tabuadas de multiplicação necessárias para a multiplicação longa.^[5]Predefinição:Falhou a verificação O algoritmo já estava em uso no antigo Egipto.^[6] As suas principais vantagens são poder ser ensinado rapidamente, não exigir qualquer memorização e poder ser executado utilizando fichas, tais como fichas de póquer, caso papel e lápis não estejam disponíveis. A desvantagem é exigir mais passos do que a multiplicação longa, o que o pode tornar pesado para números grandes.

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

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

Esta fórmula pode, em alguns casos, ser usada para tornar as tarefas de multiplicação mais fáceis de completar:

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

No caso em que ${\displaystyle x}$ e ${\displaystyle y}$ são números inteiros, temos que $${\displaystyle (x+y)^{2}\equiv (x-y)^{2}{\bmod {4}}}$$ uma vez que ${\displaystyle x+y}$ e ${\displaystyle x-y}$ são ambos pares ou ambos ímpares. Isto significa que $${\displaystyle {\begin{aligned}xy&={\frac {1}{4}}(x+y)^{2}-{\frac {1}{4}}(x-y)^{2}\\&=\left((x+y)^{2}{\text{ div }}4\right)-\left((x-y)^{2}{\text{ div }}4\right)\end{aligned}}}$$ e é suficiente (pré-)calcular a parte inteira dos quadrados divididos por 4, como no exemplo que se segue.

Exemplos

Abaixo encontra-se uma tabela de pesquisa de um quarto de quadrados com o resto descartado para os dígitos 0 a 18; esta tabela permite a multiplicação de números até ${\displaystyle 9\times 9}$.

${\displaystyle n}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
${\displaystyle \lfloor n^{2}/4\rfloor }$	0	0	1	2	4	6	9	12	16	20	25	30	36	42	49	56	64	72	81

Se, por exemplo, quisesse multiplicar 9 por 3, observaria que a soma e a diferença são 12 e 6, respetivamente. A pesquisa de ambos esses valores na tabela produz 36 e 9, cuja diferença é 27, o qual é o produto de 9 e 3.

Ver artigo principal: Algoritmo de Karatsuba

A multiplicação de Karatsuba é um algoritmo de divisão e conquista de ${\displaystyle O(n^{\log _{2}3})\approx O(n^{1.585})}$, que utiliza a recursividade para unir subcálculos.

Ao reescrever a fórmula, torna-se possível efetuar subcálculos / recursão. Através da recursividade, é possível resolver isto de forma rápida.

Sejam ${\displaystyle x}$ e ${\displaystyle y}$ representados como cadeias de ${\displaystyle n}$ dígitos numa determinada base ${\displaystyle B}$. Para qualquer inteiro positivo ${\displaystyle m}$ menor que ${\displaystyle n}$, pode-se escrever os dois números dados como

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

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

onde ${\displaystyle x_{0}}$ e ${\displaystyle y_{0}}$ são menores que ${\displaystyle B^{m}}$. O produto é então

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

onde

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

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

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

Estas fórmulas requerem quatro multiplicações e eram conhecidas por Charles Babbage.^[15] Karatsuba observou que ${\displaystyle xy}$ pode ser calculado em apenas três multiplicações, à custa de algumas adições extra. Com ${\displaystyle z_{0}}$ e ${\displaystyle z_{2}}$ como anteriormente, pode-se observar que

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

Devido à sobrecarga (overhead) da recursividade, a multiplicação de Karatsuba é mais lenta do que a multiplicação longa para pequenos valores de ${\displaystyle n}$; as implementações típicas, por conseguinte, mudam para a multiplicação longa para pequenos valores de ${\displaystyle n}$.

Outro método de multiplicação é chamado de Toom-Cook ou Toom-3. O método de Toom-Cook divide cada número a ser multiplicado em múltiplas partes. O método de Toom-Cook é uma das generalizações do método de Karatsuba. Um Toom-Cook de três vias pode fazer uma multiplicação de tamanho 3N pelo custo de cinco multiplicações de tamanho N. Isto acelera a operação por um fator de 9/5, enquanto que o método de Karatsuba a acelera por 4/3.

Embora o uso de cada vez mais partes possa reduzir ainda mais o tempo gasto em multiplicações recursivas, a sobrecarga proveniente das adições e da gestão de dígitos também cresce. Por esta razão, o método das transformadas de Fourier é tipicamente mais rápido para números com vários milhares de dígitos, e assintoticamente mais rápido para números ainda maiores.

Todo o número na base B pode ser escrito como um polinómio:

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

Além disso, a multiplicação de dois números pode ser pensada como o produto de dois polinómios:

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

Uma vez que o coeficiente de ⁠${\displaystyle B^{k}}$⁠ no produto é $${\displaystyle z_{k}=\sum _{(i,j):i+j=k}{x_{i}y_{j}}=\sum _{i=0}^{k}{x_{i}y_{k-i}},}$$ tem-se uma convolução, pelo que se pode utilizar a transformada rápida de Fourier (FFT): $${\displaystyle {\hat {f}}(XY)={\hat {f}}\left(\sum _{i=0}^{k}{x_{i}y_{k-i}}\right)={\hat {f}}(X)\cdot {\hat {f}}(Y).}$$

Portanto, a multiplicação é reduzida a uma FFT, ⁠${\displaystyle N}$⁠ multiplicações e uma FFT inversa. Resulta numa complexidade de tempo de O(n log(n) log(log n)).

Em 2007, a complexidade assintótica da multiplicação de inteiros foi melhorada pelo matemático suíço Martin Fürer da Universidade Estadual da Pensilvânia para ${\textstyle O(n\log n\cdot {2}^{\Theta (\log ^{*}(n))})}$ utilizando transformadas de Fourier sobre números complexos,^[18] onde log^* denota o logaritmo iterado. Anindya De, Chandan Saha, Piyush Kurur e Ramprasad Saptharishi apresentaram um algoritmo semelhante utilizando aritmética modular em 2008, alcançando o mesmo tempo de execução.^[19] No contexto do material acima referido, o que estes últimos autores conseguiram foi encontrar um N muito inferior a 2^3k + 1, de modo a que Z/NZ tenha uma (2m)-ésima raiz da unidade. Isto acelera o cálculo e reduz a complexidade de tempo. No entanto, estes algoritmos mais recentes só são mais rápidos do que o de Schönhage-Strassen para entradas de um tamanho impraticavelmente grande.

Em 2014, Harvey, Joris van der Hoeven e Lecerf^[20] apresentaram um novo algoritmo que atinge um tempo de execução de ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$, explicitando a constante implícita no expoente de ${\displaystyle O(\log ^{*}n)}$. Eles também propuseram uma variante do seu algoritmo que alcança ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$, mas cuja validade se baseia em conjeturas padrão sobre a distribuição dos primos de Mersenne. Em 2016, Covanov e Thomé propuseram um algoritmo de multiplicação de inteiros baseado numa generalização dos primos de Fermat que conjeturalmente atinge um limite de complexidade de ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$. Isto iguala o resultado condicional de 2015 de Harvey, van der Hoeven e Lecerf, mas utiliza um algoritmo diferente e baseia-se numa conjetura diferente.^[21] Em 2018, Harvey e van der Hoeven utilizaram uma abordagem baseada na existência de vetores curtos de reticulado garantidos pelo teorema de Minkowski para provar um limite de complexidade incondicional de ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$.^[22]

Em março de 2019, David Harvey e Joris van der Hoeven anunciaram a sua descoberta de um algoritmo de multiplicação de O(n log n).^[23] Foi publicado nos Annals of Mathematics em 2021.^[24] Pelo fato de Schönhage e Strassen terem previsto que n log(n) seria o "melhor resultado possível", Harvey disse: "... espera-se que o nosso trabalho seja o fim da linha para este problema, embora ainda não saibamos como o provar com rigor."^[25]

Existe um limite inferior trivial de Ω(n) para multiplicar dois números de n bits num único processador; não é conhecido nenhum algoritmo correspondente (em máquinas convencionais, isto é, em máquinas equivalentes a Turing), nem qualquer limite inferior mais estrito. A conjetura de Hartmanis-Stearns implicaria que ${\displaystyle O(n)}$ não pode ser alcançado. A multiplicação encontra-se fora de AC⁰[p] para qualquer primo p, o que significa que não existe nenhuma família de circuitos de profundidade constante e de tamanho polinomial (ou mesmo subexponencial) a utilizar portas AND, OR, NOT e MOD_p que consiga calcular um produto. Isto resulta de uma redução de profundidade constante de MOD_q à multiplicação.^[26] Limites inferiores para a multiplicação também são conhecidos para algumas classes de programas de ramificação (branching programs).^[27]