Algoritmos de multiplicação

Um algoritmo de multiplicação é um algoritmo (ou método) 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.

O método mais antigo e simples, conhecido desde a antiguidade como multiplicação longa ou multiplicação escolar, consiste em multiplicar cada dígito do primeiro número por cada dígito do segundo e somar os resultados. Este método tem uma complexidade de tempo de , onde é o número de dígitos. Quando feita à mão, esta operação também pode ser reformulada como o método da grelha ou a multiplicação em treliça. Em software, isto pode ser chamado de "deslocar e adicionar" (shift and add) devido aos deslocamentos de bits e à adição serem as duas únicas operações necessárias.

Em 1960, Anatoly Karatsuba descobriu a multiplicação de Karatsuba, desencadeando uma onda de investigação em algoritmos de multiplicação rápida. Este método usa três multiplicações em vez de quatro para multiplicar dois números de dois dígitos. (Uma variante disto também pode ser usada para multiplicar números complexos rapidamente.) Feito recursivamente, este método tem uma complexidade de tempo de . Dividir os números em mais de duas partes resulta na multiplicação de Toom-Cook; por exemplo, usar três partes resulta no algoritmo Toom-3. O uso de muitas partes pode definir o expoente arbitrariamente próximo de 1, mas o fator constante também cresce, tornando-o impraticável.

Em 1968, foi descoberto o algoritmo de Schönhage-Strassen, que faz uso de uma transformada de Fourier sobre um módulo. Este tem uma complexidade de tempo de . Em 2007, Martin Fürer propôs um algoritmo com complexidade . Em 2014, Harvey, Joris van der Hoeven e Lecerf propuseram um com complexidade , tornando assim explícita a constante implícita; isto foi melhorado para em 2018. Por fim, em 2019, Harvey e van der Hoeven apresentaram um algoritmo galáctico com complexidade . Isto corresponde a um palpite de Schönhage e Strassen de que este seria o limite ideal, embora isso ainda hoje permaneça como uma conjetura.

Os algoritmos de multiplicação de inteiros também podem ser usados para multiplicar polinómios por meio do método de substituição de Kronecker.

Multiplicação longa 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). 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)

Outras notações 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:

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

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.

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

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

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. 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 ou pode, muitas vezes, ser convertida para uma dessas sequências curtas.

Algoritmos para multiplicação à mão

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.

O cálculo de 34 × 13, por exemplo, poderia ser efetuado utilizando a grelha: 300 40 90 + 12 ———— 442 × 30 4 1030040 39012

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

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.

Multiplicação em treliça

thumb|right|Em primeiro lugar, monte a grelha marcando as suas linhas e colunas com os números a multiplicar. Depois, preencha as caixas com os dígitos das dezenas nos triângulos superiores e os dígitos das unidades nos inferiores thumb|right|Por fim, some ao longo dos caminhos diagonais e faça os transportes (carries) conforme necessário para obter a resposta

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.

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.

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.

Exemplo