Algoritmo di Karatsuba
L'algoritmo di Karatsuba (1960) è un algoritmo di moltiplicazione rapida (subquadratica) per moltiplicare grandi numeri interi o polinomi. È stata proposta da Anatolii Alexeevich Karatsuba in un articolo scritto insieme a Yuri Ofman nel 1962. La sua complessità è Θ, questo la rende più rapida della moltiplicazione ingenua che ha complessità Θ(n2) ().
Enunciato
Per moltiplicare due numeri di n cifre, il metodo comune consiste nel moltiplicare ogni cifra del moltiplicatore per ogni cifra del moltiplicando. Ciò implica dunque n2 prodotti di due cifre ciascuno ovvero, detto in termini più rigorosi, la complessità dell'algoritmo è O(n2).
Nel 1962, Karatsuba trovò che il calcolo di (a × 10k + b)(c × 10k + d), che sviluppando il polinomio in ac × 102k + (ad + bc) × 10k + bd richiederebbe apparentemente i quattro prodotti ac, ad, bc e bd, può in effetti essere effettuato con i soli tre prodotti ac, bd e (a – b)(c – d). Infatti, raggruppando i calcoli nel modo seguente, otteniamo:
Ad esempio, per calcolare 26 × 34, basta fare:
- 2 × 3 = 6
- 6 × 4 = 24
- (2 – 6) × (3 – 4) = 4
Il risultato finale è dunque 6 × 100 + (6 + 24 – 4) × 10 + 24 = 600 + 260 + 24 = 884.
La moltiplicazione per la base di numerazione (normalmente 10, ma nel caso dei calcolatori 2), corrispondente al cambio di cifra, e le restanti addizioni sono relativamente poco costose in termini di tempo. Per quanto riguarda numeri più grandi, il metodo per il calcolo di ac, bd e (a – b)(c – d) può essere reiterato separando a loro volta a, b, c e d in due ulteriori termini.
Algoritmo
Questo algoritmo si ispira al paradigma di programmazione divide et impera, cioè nella riduzione di un problema in altri di taglia minore. La velocità dell'algoritmo risiede dunque nel minor numero di sotto-moltiplicazioni rispetto all'algoritmo ingenuo a scapito di un maggior numero di operazioni di complessità lineari (somme, sottrazioni) rendendolo però asintoticamente più veloce.
Siano x e y due numeri a n cifre in base B (solitamente 2). Preso un numero m minore di n, possiamo scrivere:
con x2 e y2 minori di Bm; si vede facilmente che è univocamente rappresentabile. La moltiplicazione di e risulterà dunque:
L'algoritmo standard prevederebbe di effettuare le quattro moltiplicazioni separatamente, e sommare tra loro i risultati parziali dopo opportuni shift. La complessità diventa quindi O(n2) a causa delle quattro chiamate ricorsive per ognuna delle sotto-moltiplicazioni. Il metodo di Karatsuba riesce invece a diminuire a tre il numero delle moltiplicazioni necessarie. Poniamo quindi:
Notiamo che per il calcolo del valore di sia necessaria solamente una moltiplicazione, ma al fine del calcolo del risultato finale riesce a sostituirne due:
Per calcolare queste tre moltiplicazioni di numeri di m-cifre, possiamo richiamare ricorsivamente l'algoritmo di Karatsuba. Da notare come addizioni e shift siano computabili in tempo lineare, e siano quindi trascurabili.
La moltiplicazione di Karatsuba lavora meglio con operandi di taglia simile; per ottenere il tempo ottimale occorre che i sottoprodotti siano bilanciati, e ciò avviene scegliendo m pari a n/2.
Esempio
Supponiamo che si voglia calcolare il prodotto di 1234 e 5678. Scelto B = 10 e m = 2, otteniamo
- 12 34 = 12 ⋅ 102 + 34
- 56 78 = 56 ⋅ 102 + 78
- X = 12 ⋅ 56 = 672
- Y = 34 ⋅ 78 = 2652
- Z = (12 + 34)(56 + 78) - X - Y = 46 ⋅ 134 - 672 - 2652 = 2840
- X 102⋅2 + Y + Z 102 = 672 0000 + 2652 + 2840 00 = 7006652 = 1234 ⋅ 5678
Complessità
Sia T(n) il tempo necessario per moltiplicare due numeri a n-cifre con l'algoritmo di Karatsuba, allora possiamo scrivere
- T(n) = 3 T(n/2) + cn + d
per una qualche costante c e d. Questa equazione di ricorsione può esser risolta tramite il master theorem, ottenendo una complessità di Θ(nlog(3)/log(2)). La quantità log(3)/log(2) è all'incirca 1.585, che implica che questo metodo è significativamente più veloce della moltiplicazione sequenziale per n grandi. A causa dell'overhead della ricorsione, la moltiplicazione di Karatsuba è tipicamente lenta che la moltiplicazione lunga per piccoli valori di n; la tipica implementazione tuttavia passa alla moltiplicazione lunga se n è al di sotto di una certa soglia nel calcolare i sottoprodotti.
Le implementazioni differiscono grandemente su quale sia il punto in cui la moltiplicazione di Karatsuba si più veloce dell'algoritmo classico, ma in generale per numeri superiori a 2320 Karatsuba diviene l'algoritmo di riferimento.[1][2]
La moltiplicazione Toom-Cook è la generalizzazione più veloce dell'algoritmo di Karatsuba ed è ulteriormente superata dall'algoritmo attualmente più veloce, l'algoritmo di Schönhage-Strassen.
Toom e Cook migliorarono questo metodo dividendo i numeri in r blocchi (invece di 2). Il tempo di calcolo in O(n2) per il metodo normale diventa così O(n1+ε) dove ε è un reale positivo arbitrario.
Esempio
Così, 12378456 × 25874215 sarà calcolato come segue :
- 1237 × 2587
- 8456 × 4215
- (1237 – 8456) × (2587 – 4215) = 7219 × 1628
Il prodotto 1237 × 2587 sarà calcolato come segue :
- 12 × 25
- 37 × 87
- (12 – 37) × (25 – 87) = 25 × 62
Il prodotto 12 × 25 sarà calcolato come:
- 1 × 2 = 2
- 2 × 5 = 10
- (1 – 2) × (2 – 5) = 1 × 3 = 3
per ottenere 12 × 25 = 2 × 100 + (2 + 10 – 3) × 10 + 10 = 300. Si otterrà quindi :
- 12 × 25 = 300
- 37 × 87 = 3219
- 25 × 62 = 1550
da cui 1237 × 2587 = 300 × 1002 + (300 + 3219 – 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119. Si procederà allo stesso modo per i prodotti 8456 × 4215 et 7219 × 1628, ottenendo finalmente :
- 1237 × 2587 = 3200119
- 8456 × 4215 = 35642040
- 7219 × 1628 = 11752532
Da cui infine : 12378456 × 25874215 = 3200119 × 100002 + (3200119 + 35642040 – 11752532) × 10000 + 35652040
- = 320011900000000 + 270896270000 + 35642040
- = 320282831912040
Il calcolo completo richiede solo 27 prodotti a due cifre invece dei 64 del metodo normalmente usato. Ben compreso, questo metodo, fastidioso a mano, rivela tutta la sua potenza fatto da una macchina. Per n = 1000, le operazioni sono nell'ordine di 50 000 mentre con n2 = 1 000 000.
Bibliografia
- A. Karatsuba and Yu Ofman, Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR Vol. 145 (1962), pp. 293–294. Traduzione in Physics-Doklady 7 (1963), pp. 595–596.
- Karacuba A. A. Berechnungen und die Kompliziertheit von Beziehungen (German) // Elektron. Inform.-verarb. Kybernetik, 11, 603–606 (1975).
- Karatsuba A. A. The complexity of computations // Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
- Knuth D. E. The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp., Reading (1969).
Collegamenti esterni
- (EN) Eric W. Weisstein, Algoritmo di Karatsuba, su MathWorld, Wolfram Research.
- Algorithme de Karatsuba pour la multiplication Rapide, su gersoo.free.fr. URL consultato il 13 settembre 2007 (archiviato dall'url originale il 31 ottobre 2007).
- Karatsuba Multiplication on Fast Algorithms and the FEE, su ccas.ru.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)