Moltiplicazione Toom-Cook

Da Wikipedia, l'enciclopedia libera.

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

Indice 1 Idea 2 Toom-3 3 Esempio 4 Collegamenti esterni

[modifica] 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.

[modifica] 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, 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 ed infine qualche algoritmo basato sulle trasformate di Fourier.

[modifica] 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 calcola

w4=c(oo)=a(oo)*b(oo)=   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

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

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

[modifica] Collegamenti esterni

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