Moltiplicazione Toom-Cook
# Moltiplicazione Toom-Cook

Toom-Cook è stato, assieme all'algoritmo di Karatsuba, il primo algoritmo per la moltiplicazione di interi ad avere complessità meno che quadratica. Proposto nel 1963 da Andrei Toom in una forma involuta passante per il computo di due quadrati; è stato successivamente sistematizzato da Stephen Cook senza cambiarne la complessità asintotica, che è merito esclusivo del primo autore. È attualmente un algoritmo assestato ed ampiamente utilizzato per il prodotto di numeri interi grandi o polinomi.

## Idea

Dati due interi grandi, A e B, il metodo Toom-Cook consiste nel suddividerli in k parti, lunghe ognuna l cifre, quindi operare sulle parti. Ovvero scrivere i due numeri A e B in una opportuna base X in modo che entrambi consistano in k parti. Quindi i due numeri vengono visti come due polinomi in X con k coefficienti, il loro prodotto sarà dunque un polinomio sempre in X ma di grado doppio, quindi con 2k-1 parti. Per calcolare il polinomio prodotto si procede non con le canoniche moltiplicazioni coefficiente per coefficiente, ma valutandolo in 2k-1 punti e quindi interpolando per trovare i coefficienti. Le valutazioni stesse richiedono la valutazione dei due operandi, quindi una moltiplicazione.

## Toom-3

La più diffusa istanza dell'idea di cui sopra, è l'algoritmo Toom-3. Spesso considerato come l'unico algoritmo Toom-Cook, non ne è in realtà che una possibilità, con k = 3.

Toom-3 riduce una moltiplicazione di due interi lunghi a 5 moltiplicazioni di interi lunghi un terzo. Se per queste moltiplicazioni più corte si usa nuovamente Toom-3 e così via ricorsivamente, la complessità totale dell'algoritmo risulterà $O(n^{log(5)/log(3)}),$ ovvero circa $O(n^{1,465...}).$ La complessità generale di ogni Toom-k risulta essere O(c(k) $n^e),$ dove e = log(2k-1) / log(k), $n^e$ è dato dal numero di moltiplicazioni di base da effettuare, mentre c tiene conto delle addizioni, sottrazioni, piccole moltiplicazioni necessarie per la valutazione e l'interpolazione. Lo stesso algoritmo di Karatsuba può esser visto come un caso particolare, i due operandi vengono spezzati in due parti, quindi Toom-2; Infatti ha una complessità dell'ordine di $O(n^{log(3)/log(2)}),$ circa $O(n^{1,585...}).$ La moltiplicazione ordinaria in cui ogni cifra viene moltiplicata per ogni altra ha la complessità limite di Toom-1 $O(n^2).$

Quindi, asintoticamente, ogni Toom-n+1 è migliore del Toom-n precedente, ma tutti i Toom vengono battuti dagli algoritmi di moltiplicazione basati sulla FFT, ad esempio, l'algoritmo di Schönhage-Strassen, di complessità O(n log n log log n).

Il punto interessante son le costanti che la complessità asintotica nasconde, così che per numeri piccoli la moltiplicazione ordinaria è la più veloce. Al crescere di dimensione degli operandi, questa lascia il passo a Karatsuba, quindi Toom-3, Toom-4, probabilmente qualche altro Toom-k. La libreria GMP, ad esempio, per la moltiplicazione di interi usa algoritmi fino al Toom-8½ prima di ricorrere alle trasformate di Fourier.

## Esempio

Un esempio di Toom-3 con una sequenza di inversione ottimale. Supponiamo si vogliano moltiplicare A=31.415.926 e B=123.456.789

In primo luogo questi andrebbero visti come polinomi

dove A=a(1.000) e B=b(1.000).

Per calcolare c(x) = a(x) * b(x), si valutano i due polinomi a e b in cinque punti, moltiplicando quindi i risultati ottenuti, come segue:

Risulta quindi necessario risolvere il problema di interpolazione, con le seguenti operazioni

Infine il risultato può essere ricostruito dal polinomio c valutato in 1.000

...mentre tutte le operazioni qui sopra possono essere facilmente verificate con una calcolatrice tascabile, per verificare direttamente la correttezza del prodotto abbiamo bisogno di un calcolatore con maggiore precisione...

Un altro interessante esempio può essere fatto sull'uso dell'algoritmo per prodotti sbilanciati, in particolare per il caso in cui uno degli operandi abbia all'incirca il doppio delle cifre dell'altro.

Supponiamo quindi che si vogliano moltiplicare A = 59.737.383.289 e B = 64.926.

Nuovamente scriveremo i polinomi associati:

ottenendo ancora A=a(1.000) e B=b(1.000).

Quindi si calcola c(x) = a(x) * b(x), valutando i polinomi a e b come segue:

La sequenza è la stessa di prima, pur con numeri diversi:

Uguale è anche la fase di ricomposizione:

Il risultato è lo stesso della moltiplicazione precedente, ma è interessante osservare che il polinomio c(x) non lo è. Mentre i polinomi a e b vengono tipicamente scelti in modo da avere tutti i coefficienti minori della base prescelta (1.000 negli esempi), ovvero in modo univoco, il polinomio c che si ottiene ha normalmente coefficienti dell'ordine del quadrato di tale base, dunque non è univocamente determinato dal valore del risultato della moltiplicazione.

