Toom-Cook, por vezes conhecido como Toom-3, nomeado em homenagem a Andrei Toom, que introduziu o novo algoritmo com a sua baixa complexidade, e a Stephen Cook, que clarificou a sua descrição, é um algoritmo de multiplicação para inteiros grandes.
Dados dois inteiros grandes, a e b, o algoritmo de Toom-Cook divide a e b em k partes menores, cada uma de comprimento l, e executa operações nessas partes. À medida que k cresce, é possível combinar muitas das suboperações de multiplicação, reduzindo assim a complexidade computacional global do algoritmo. As suboperações de multiplicação podem então ser calculadas recursivamente usando novamente a multiplicação de Toom-Cook, e assim por diante. Embora os termos "Toom-3" e "Toom-Cook" sejam por vezes incorretamente utilizados de forma intercambiável, o Toom-3 é apenas uma instância única do algoritmo de Toom-Cook, em que k = 3.
O Toom-3 reduz nove multiplicações para cinco, e é executado num tempo de Θ(nlog(5)/log(3)) ≈ Θ(n1.46). Em geral, o Toom-k é executado em , onde , ne é o tempo gasto nas submultiplicações, e c é o tempo despendido nas adições e nas multiplicações por pequenas constantes.Knuth, p. 296 O algoritmo de Karatsuba é equivalente ao Toom-2, onde o número é dividido em duas partes menores. Este reduz quatro multiplicações para três e, portanto, opera em Θ(nlog(3)/log(2)) ≈ Θ(n1.58).
Embora o expoente e possa ser definido para um valor arbitrariamente próximo de 1 através do aumento de k, o termo constante na função cresce muito rapidamente.Crandall & Pomerance, p. 474 A taxa de crescimento para esquemas Toom-Cook de nível misto ainda era um problema de investigação em aberto em 2005.Crandall & Pomerance, p. 536 Uma implementação descrita por Donald Knuth atinge a complexidade de tempo .Knuth, p. 302
Devido à sua sobrecarga (overhead), o algoritmo de Toom-Cook é mais lento do que a multiplicação longa para números pequenos, sendo por isso tipicamente utilizado para multiplicações de tamanho intermédio, antes que o algoritmo de Schönhage-Strassen (com complexidade ), que é assintoticamente mais rápido, se torne prático.
Toom descreveu este algoritmo pela primeira vez em 1963, e Cook publicou um algoritmo melhorado (assintoticamente equivalente) na sua tese de doutoramento em 1966.Positive Results, capítulo III de Stephen A. Cook: On the Minimum Computation Time of Functions.
Detalhes Esta seção discute exatamente como executar o Toom-k para qualquer valor dado de k, e consiste numa simplificação da descrição da multiplicação de polinómios de Toom-Cook apresentada por Marco Bodrato.Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In WAIFI'07 proceedings, volume 4547 of LNCS, pages 116–133. June 21–22, 2007. author website O algoritmo possui cinco passos principais: Divisão (Splitting) Avaliação (Evaluation) Multiplicação pontual (Pointwise multiplication) Interpolação (Interpolation) Recomposição (Recomposition)
Numa implementação típica de inteiros grandes, cada número inteiro é representado como uma sequência de dígitos em notação posicional, com a base (radix) definida para um valor b (tipicamente grande); para este exemplo, utilizamos , de modo a que cada dígito corresponda a um grupo de quatro dígitos decimais (numa implementação de computador, b seria tipicamente uma potência de 2). Suponhamos que os dois números inteiros a serem multiplicados são:
m = 1234567890123456789012n =987654321987654321098.
Estes são muito mais pequenos do que os que seriam normalmente processados com o algoritmo Toom-Cook (a multiplicação escolar seria mais rápida), mas servirão perfeitamente para ilustrar o algoritmo.
Divisão No Toom-k, queremos dividir os fatores em k partes.
O primeiro passo consiste em selecionar a base , de tal forma que o número de dígitos de tanto m quanto n na base B seja, no máximo, k (por exemplo, 3 no Toom-3). Uma escolha típica para i é dada por:
No nosso exemplo, faremos o Toom-3, pelo que escolhemos . De seguida, separamos m e n nos seus dígitos de base B, e :
Usamos então estes dígitos como coeficientes em polinómios p e q de grau , com a propriedade de que e :
O objetivo de definir estes polinómios é que, se conseguirmos calcular o seu produto , a nossa resposta final será .
No caso em que os números a serem multiplicados são de tamanhos diferentes, é útil utilizar valores diferentes de k para m e n, que chamaremos de e . Por exemplo, o algoritmo "Toom-2.5" refere-se ao Toom-Cook com e . Neste caso, o i em é tipicamente escolhido por:
Avaliação A abordagem de Toom-Cook para calcular o produto polinomial é bastante comum. Note que um polinómio de grau d é determinado de forma única por pontos (por exemplo, uma reta - que é um polinómio de grau um - é especificada por dois pontos). A ideia é avaliar e em vários pontos. Depois, multiplicam-se os seus valores nesses pontos para obter pontos no polinómio produto. Finalmente, interpola-se para encontrar os seus coeficientes.
Uma vez que , necessitaremos de pontos para determinar o resultado final. Designemos este valor por d. No caso do Toom-3, . O algoritmo funcionará independentemente dos pontos que forem escolhidos (com algumas pequenas exceções; veja o requisito de invertibilidade da matriz na secção Interpolação), mas para simplificar o algoritmo, é preferível escolher valores inteiros pequenos como 0, 1, −1 e −2.
Um valor de ponto invulgar que é frequentemente utilizado é o infinito, escrito como ou . "Avaliar" um polinómio p no infinito significa, na verdade, calcular o limite de quando x tende para o infinito. Consequentemente, é sempre o valor do seu coeficiente de maior grau (no exemplo acima, o coeficiente ).
No nosso exemplo do Toom-3, usaremos os pontos 0, 1, −1, −2 e . Estas escolhas simplificam a avaliação, produzindo as fórmulas:
e de forma análoga para q. No nosso exemplo, os valores que obtemos são:
p(0) = = 56789012 = 56789012p(1) = = 56789012 + 78901234 + 123456 = 135813702p(−1) = = 56789012 − 78901234 + 123456 = −21988766p(−2) = = 56789012 − 2 × 78901234 + 4 × 123456 = −100519632p(∞) = = 123456 = 123456q(0) = = 54321098 = 54321098q(1) = = 54321098 + 43219876 + 98765 = 97639739q(−1) = = 54321098 − 43219876 + 98765 = 11199987q(−2) = = 54321098 − 2 × 43219876 + 4 × 98765 = −31723594q(∞) = = 98765 = 98765.
Como demonstrado, estes valores podem ser negativos.
Para efeitos de explicação posterior, será útil considerar este processo de avaliação como uma multiplicação matriz-vetor, em que cada linha da matriz contém as potências de um dos pontos de avaliação, e o vetor contém os coeficientes do polinómio:
As dimensões da matriz são d por para p, e d por para q. A linha referente ao infinito é sempre constituída apenas por zeros, com a exceção de um 1 na última coluna.
Avaliação mais rápida A avaliação multiponto pode ser obtida de forma mais rápida do que recorrendo às fórmulas acima. O número de operações elementares (adição/subtração) pode ser reduzido. A sequência fornecida por Bodrato para o Toom-3, executada aqui sobre o primeiro operando (polinómio p) do nosso exemplo, é a seguinte:
← = 56789012 + 123456 = 56912468p(0) = = 56789012 = 56789012p(1) = = 56912468 + 78901234 = 135813702p(−1) = = 56912468 − 78901234 = −21988766p(−2) = = (− 21988766 + 123456 ) × 2 − 56789012 = − 100519632p(∞) = = 123456 = 123456.
Esta sequência requer cinco operações de adição/subtração, uma a menos do que na avaliação direta. Além disso, poupou-se a multiplicação por 4 que ocorreria no cálculo de p(−2).
Multiplicação pontual Ao contrário da multiplicação dos polinómios e , a multiplicação dos valores avaliados e envolve unicamente a multiplicação de números inteiros — consistindo numa instância mais pequena do problema original. Nós invocamos recursivamente o nosso procedimento de multiplicação para multiplicar cada par de pontos avaliados. Em implementações práticas, à medida que os operandos se tornam mais pequenos, o algoritmo muda para a multiplicação longa escolar. Fazendo de r o polinómio produto, no nosso exemplo temos:
r(0) = = 56789012 × 54321098 = 3084841486175176r(1) = = 135813702 × 97639739 = 13260814415903778r(−1) = = −21988766 × 11199987 = −246273893346042r(−2) = = −100519632 × −31723594 = 3188843994597408r(∞) = = 123456 × 98765 = 12193131840.
Como ilustrado, estes resultados também podem ser negativos. Para números suficientemente grandes, este é o passo mais computacionalmente dispendioso, e o único passo que não é linear em relação ao tamanho de m e n.
Interpolação Este é o passo mais complexo, atuando como o inverso do passo de avaliação: dados os nossos d pontos no polinómio produto , precisamos de determinar os seus coeficientes. Dito de outra forma, queremos resolver esta equação matricial para encontrar o vetor do lado direito:
Esta matriz é construída da mesma maneira que a do passo de avaliação, exceto que as suas dimensões são . Poderíamos resolver esta equação recorrendo a uma técnica como a eliminação de Gauss, mas isso seria demasiado pesado. Em alternativa, utilizamos o facto de que, desde que os pontos de avaliação tenham sido escolhidos adequadamente, esta matriz é invertível (veja também a Matriz de Vandermonde), resultando assim em:
Tudo o que resta é calcular este produto matriz-vetor. Embora a matriz possua frações, os coeficientes resultantes serão sempre números inteiros — logo, tudo isto pode ser executado apenas com aritmética inteira, recorrendo apenas a adições, subtrações e multiplicações/divisões por pequenas constantes. Um dos maiores desafios de conceção no algoritmo Toom-Cook é encontrar uma sequência eficiente de operações para calcular este produto; uma sequência descrita por Bodrato para o Toom-3 é a seguinte, executada aqui com os valores do nosso exemplo:
← = 3084841486175176 ← = 12193131840 ← = (3188843994597408 − 13260814415903778)/3 = −3357323473768790 ← = (13260814415903778 − (−246273893346042))/2 = 6753544154624910 ← = −246273893346042 − 3084841486175176 = −3331115379521218 ← = (−3331115379521218 − (−3357323473768790))/2 + 2 × 12193131840 = 13128433387466 ← = −3331115379521218 + 6753544154624910 − 12193131840 = 3422416581971852 ← = 6753544154624910 − 13128433387466 = 6740415721237444.
Neste momento, conhecemos os coeficientes do nosso polinómio produto r:
Se tivéssemos usado valores diferentes para , ou pontos de avaliação, a matriz e a nossa estratégia de interpolação mudariam; contudo, ela não depende dos valores de entrada, podendo assim ser pré-programada (hard-coded) para qualquer conjunto específico de parâmetros.
Recomposição
Por fim, avaliamos para extrair a nossa resposta final. Esta operação é simples e direta porque é uma potência de b, e portanto as multiplicações por potências de correspondem todas a deslocamentos (shifts) de um número inteiro de dígitos na base b. No exemplo que seguimos, e .
3084841486175176 6740415721237444 3422416581971852 13128433387466 + 12193131840 1219326312467611632493760095208585886175176
E este é exatamente o produto de 1234567890123456789012 e 987654321987654321098.
Divisão assimétrica
A etapa de interpolação depende do grau do polinômio produto, que é a soma dos graus dos polinômios fatores, mas não dos graus individuais. Embora o Toom-3 básico divida cada fator em 3 partes (polinômios quadráticos), se os fatores diferirem em tamanho, pode ser benéfico dividir um em 2 partes (um polinômio linear) e o outro em 4 partes (um cúbico) com coeficientes de tamanho mais equilibrado. Assim, a mesma etapa de interpolação pode produzir um polinômio produto quártico.
Para o Toom-3, esta é a única divisão alternativa interessante (o caso degenerado de dividir qualquer um dos fatores em apenas 1 parte não oferece economia de tempo), mas o Toom-Cook de grau mais elevado permite possibilidades adicionais.