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

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

a(x) =  31x^2+415x+926
b(x) = 123x^2+456x+789

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:

w4=c(1/0)=a(1/0)*b(1/0)=   31           *   123           =             3813
w3=c(-2) =a(-2) *b(-2) =(4*31-2*415+926)*(4*123-2*456+789)= 220*369 =  81180
w2=c(-1) =a(-1) *b(-1) =  (31-  415+926)*  (123-  456+789)= 542*456 = 247152
w1=c(1)  =a(1)  *b(1)  =  (31+  415+926)*  (123+  456+789)=1372*1368=1876896
w0=c(0)  =a(0)  *b(0)  =            926 *             789 =           730614

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

w3 <- (w3 - w1)/3        = -598572
w1 <- (w1 - w2)/2        =  814872
w2 <-  w2 - w0           = -483462
w3 <- (w2 - w3)/2 + 2*w4 =   65181 
w2 <-  w2 + w1 - w4      =  327597
w1 <-  w1 - w3           =  749691

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

c(x) = w4 x4 + w3 x3 + w2 x2 + w1 x + w0 =
C = c(1.000) = 
 3.813
    65.181
       327.597
           749.691
               730.614
----------------------
 3.878.509.347.421.614

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

a(x) = 59x3+737x2+383x+289
b(x) =           64x +926

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:

w4=c(1/0)=a(1/0)*b(1/0)=    59                 *    64     =            3776
w3=c(-2) =a(-2) *b(-2) =(-8*59+4*737-2*383+289)*(-2*64+926)=1999*789=1595202
w2=c(-1) =a(-1) *b(-1) =  (-59+  737-  383+289)*  (-64+926)= 584*862= 503408
w1=c(1)  =a(1)  *b(1)  =   (59+  737+  383+289)*   (64+926)=1468*990=1453320
w0=c(0)  =a(0)  *b(0)  =                   289 *       926 =          267614

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

w3 <- (w3 - w1)/3        =  47294
w1 <- (w1 - w2)/2        = 474956
w2 <-  w2 - w0           = 235794
w3 <- (w2 - w3)/2 + 2*w4 = 101802 
w2 <-  w2 + w1 - w4      = 706974
w1 <-  w1 - w3           = 373154

Uguale è anche la fase di ricomposizione:

 3.776
   101.802
       706.974
           373.154
               267.614
----------------------
 3.878.509.347.421.614

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.

Collegamenti esterni

• Articolo originale in Russo Тоом Андрей Леонович, О сложности схемы из функциональных элементов, реализующей умножение целых чисел, Доклады Академии Наук СССР, T.150, N°3, pagg.496-498
• Descrizione della moltiplicazione Toom-3 nella documentazione di GMP, su gmplib.org.
• Articoli in inglese sull'ottimalità degli algoritmi Toom, su bodrato.it.