Algoritmos de multiplicação
Um algoritmo de multiplicação é um algoritmo para multiplicar dois números. Dependendo do tamanho dos números, diferentes algoritmos são mais eficientes do que outros. Inúmeros algoritmos são conhecidos e tem havido muita investigação sobre o tópico.
Se for utilizado um sistema de numeração posicional, uma forma natural de multiplicar números é ensinada nas escolas como multiplicação longa, por vezes chamada de multiplicação escolar, ou ainda algoritmo padrão: multiplica-se o multiplicando por cada dígito do multiplicador e, em seguida, somam-se todos os resultados devidamente deslocados. Este processo requer a memorização da tabuada para dígitos únicos. Este é o algoritmo habitual para multiplicar números maiores à mão na base 10. Uma pessoa que faça a multiplicação longa em papel irá escrever todos os produtos e, depois, somá-los; um utilizador de ábaco irá somar os produtos assim que cada um deles for calculado.
Exemplo
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). Nalguns países, como a Alemanha, a multiplicação acima é descrita de forma semelhante, mas o produto original é mantido na horizontal e o cálculo começa com o primeiro dígito do multiplicador: O pseudocódigo abaixo descreve o processo da multiplicação demonstrada acima. Mantém apenas uma linha para preservar a soma que, no final, se torna o resultado. Note que o operador '+=' é usado para denotar a soma ao valor existente e a operação de armazenamento (à semelhança de linguagens como Java e C) por uma questão de compactação.
Utilização em computadores
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 2w, 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 n2 operações. Mais formalmente, multiplicar dois números de n dígitos utilizando a multiplicação longa requer Θ ( n 2 ) {\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.
Para além da multiplicação longa padrão, existem vários outros métodos utilizados para efetuar multiplicações à mão. Estes algoritmos podem ser concebidos tendo em vista a rapidez, a facilidade de cálculo ou o seu valor educativo, em especial quando não se dispõe de computadores ou de tabuadas.
Método da grelha
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. 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.
Multiplicação em treliça
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. 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.
Multiplicação camponesa russa
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.Predefinição:Falhou a verificação O algoritmo já estava em uso no antigo Egipto. 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.
Multiplicação de um quarto de quadrado
Esta fórmula pode, em alguns casos, ser usada para tornar as tarefas de multiplicação mais fáceis de completar: ( x + y ) 2 4 − ( x − y ) 2 4 = ( x + y 2 ) 2 − ( x − y 2 ) 2 = x y {\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 x {\displaystyle x} e y {\displaystyle y} são números inteiros, temos que ( x + y ) 2 ≡ ( x − y ) 2 mod 4 {\displaystyle (x+y)^{2}\equiv (x-y)^{2}{\bmod {4}}} uma vez que x + y {\displaystyle x+y} e x − y {\displaystyle x-y} são ambos pares ou ambos ímpares. Isto significa que x y = 1 4 ( x + y ) 2 − 1 4 ( x − y ) 2 = ( ( x + y ) 2 div 4 ) − ( ( x − y ) 2 div 4 ) {\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.
Uma linha de investigação na ciência da computação teórica centra-se no número de operações aritméticas de bit único necessárias para multiplicar dois inteiros de n {\displaystyle n} bits. Isto é conhecido como a complexidade computacional da multiplicação. Os algoritmos habituais efetuados à mão possuem uma complexidade assintótica de O ( n 2 ) {\displaystyle O(n^{2})} , mas em 1960 Anatoly Karatsuba descobriu que era possível obter uma complexidade melhor (com o Algoritmo de Karatsuba). Atualmente, o algoritmo com a melhor complexidade computacional é um algoritmo de 2019 de David Harvey e Joris van der Hoeven, que utiliza as estratégias de usar transformadas teóricas dos números introduzidas pelo Algoritmo de Schönhage-Strassen para multiplicar inteiros usando apenas O ( n log n ) {\displaystyle O(n\log n)} operações. Conjetura-se que este seja o melhor algoritmo possível, mas os limites inferiores de Ω ( n log n ) {\displaystyle \Omega (n\log n)} não são conhecidos.
Multiplicação de Karatsuba
A multiplicação de Karatsuba é um algoritmo de divisão e conquista de O ( n log 2 3 ) ≈ O ( n 1.585 ) {\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 x {\displaystyle x} e y {\displaystyle y} representados como cadeias de n {\displaystyle n} dígitos numa determinada base B {\displaystyle B} . Para qualquer inteiro positivo m {\displaystyle m} menor que n {\displaystyle n} , pode-se escrever os dois números dados como onde x 0 {\displaystyle x_{0}} e y 0 {\displaystyle y_{0}} são menores que B m {\displaystyle B^{m}} . O produto é então
Toom-Cook
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.
Schönhage-Strassen
Todo o número na base B pode ser escrito como um polinómio: X = ∑ i = 0 N x i B i {\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: X Y = ( ∑ i = 0 N x i B i ) ( ∑ j = 0 N y i B j ) {\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 B k {\displaystyle B^{k}} no produto é z k = ∑ ( i , j ) : i + j = k x i y j = ∑ i = 0 k x i y k − i , {\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): f ^ ( X Y ) = f ^ ( ∑ i = 0 k x i y k − i ) = f ^ ( X ) ⋅ f ^ ( Y ) . {\displaystyle {\hat {f}}(XY)={\hat {f}}\left(\sum _{i=0}^{k}{x_{i}y_{k-i}}\right)={\hat {f}}(X)\cdot {\hat {f}}(Y).}
Melhorias adicionais
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 O ( n log n ⋅ 2 Θ ( log ∗ ( n ) ) ) {\textstyle O(n\log n\cdot {2}^{\Theta (\log ^{*}(n))})} utilizando transformadas de Fourier sobre números complexos, 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. No contexto do material acima referido, o que estes últimos autores conseguiram foi encontrar um N muito inferior a 23k + 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.
Limites inferiores
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 O ( n ) {\displaystyle O(n)} não pode ser alcançado. A multiplicação encontra-se fora de AC0[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 MODp que consiga calcular um produto. Isto resulta de uma redução de profundidade constante de MODq à multiplicação. Limites inferiores para a multiplicação também são conhecidos para algumas classes de programas de ramificação (branching programs).
A multiplicação complexa envolve normalmente quatro multiplicações e duas adições. ( a + b i ) ( c + d i ) = ( a c − b d ) + ( b c + a d ) i . {\displaystyle (a+bi)(c+di)=(ac-bd)+(bc+ad)i.} × a b i c a c b c i d i a d i − b d {\displaystyle {\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}} Como observado por Peter Ungar em 1963, é possível reduzir o número de multiplicações para três, utilizando essencialmente o mesmo cálculo que o Algoritmo de Karatsuba. O produto ( a + b i ) ⋅ ( c + d i ) {\displaystyle (a+bi)\cdot (c+di)} pode ser calculado da seguinte forma: Este algoritmo utiliza apenas três multiplicações, em vez de quatro, e cinco adições ou subtrações, em vez de duas. Se uma multiplicação for mais dispendiosa do que três adições ou subtrações, como quando se calcula à mão, então existe um ganho de velocidade. Nos computadores modernos, uma multiplicação e uma adição podem demorar sensivelmente o mesmo tempo, pelo que pode não haver ganho de velocidade. Existe um compromisso (trade-off), uma vez que pode haver alguma perda de precisão ao utilizar cálculos em ponto flutuante.
Todos os algoritmos de multiplicação acima também podem ser expandidos para multiplicar polinómios. Alternativamente, a técnica de substituição de Kronecker pode ser usada para converter o problema de multiplicação de polinómios numa única multiplicação binária. Os métodos de multiplicação longa podem ser generalizados para permitir a multiplicação de fórmulas algébricas: Como outro exemplo de multiplicação baseada em colunas, considere a multiplicação de 23 toneladas longas (t), 12 quintais americanos/britânicos (cwt) e 2 quartos (qtr) por 47. Este exemplo utiliza medidas do sistema avoirdupois: 1 t = 20 cwt, 1 cwt = 4 qtr. A mesma disposição e métodos podem ser usados para quaisquer medidas tradicionais e moedas não decimais, como o antigo sistema britânico £sd (libras, xelins e pence).
