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à è Θ $(n^{\log _{2}3})$ , questo la rende più rapida della moltiplicazione ingenua che ha complessità Θ(n²) ( $\log _{2}3\approx 1.585$ ).

Enunciato modifica

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 n² prodotti di due cifre ciascuno ovvero, detto in termini più rigorosi, la complessità dell'algoritmo è O(n²).

Nel 1962, Karatsuba trovò che il calcolo di (a × 10^k + b)(c × 10^k + d), che sviluppando il polinomio in ac × 10^2k + (ad + bc) × 10^k + 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:

(a × 10^k + b)(c × 10^k + d) = ac × 10^2k + (ac + bd – (a – b)(c – d)) × 10^k + bd

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 modifica

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:

$x=x_{1}\cdot B^{m}+x_{2}$

$y=y_{1}\cdot B^{m}+y_{2}$

con x₂ e y₂ minori di B^m; si vede facilmente che è univocamente rappresentabile. La moltiplicazione di $x$ e $y$ risulterà dunque:

$xy=(x_{1}B^{m}+x_{2})\cdot (y_{1}B^{m}+y_{2})=x_{1}y_{1}\cdot B^{2m}+(x_{1}y_{2}+x_{2}y_{1})\cdot B^{m}+x_{2}y_{2}$

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(n²) 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:

$X=x_{1}\cdot y_{1}$

$Y=x_{2}\cdot y_{2}$

$Z=(x_{1}+x_{2})\cdot (y_{1}+y_{2})-X-Y$

Notiamo che per il calcolo del valore di $Z$ sia necessaria solamente una moltiplicazione, ma al fine del calcolo del risultato finale riesce a sostituirne due:

$Z=(x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}+x_{2}y_{2})-x_{1}y_{1}-x_{2}y_{2}=x_{1}\cdot y_{2}+x_{2}\cdot y_{1}$

$xy=X\cdot B^{2m}+Z\cdot B^{m}+Y$

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 modifica

Supponiamo che si voglia calcolare il prodotto di 1234 e 5678. Scelto B = 10 e m = 2, otteniamo

12 34 = 12 ⋅ 10² + 34

56 78 = 56 ⋅ 10² + 78

X = 12 ⋅ 56 = 672

Y = 34 ⋅ 78 = 2652

Z = (12 + 34)(56 + 78) - X - Y = 46 ⋅ 134 - 672 - 2652 = 2840

X 10^2⋅2 + Y + Z 10² = 672 0000 + 2652 + 2840 00 = 7006652 = 1234 ⋅ 5678

Complessità modifica

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 Θ(n^{log(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 2³²⁰ 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(n²) per il metodo normale diventa così O(n^1+ε) dove ε è un reale positivo arbitrario.

Esempio modifica

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 × 100² + (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 × 10000² + (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, $n^{\ln(3)/\ln(2)}$ le operazioni sono nell'ordine di 50 000 mentre con n² = 1 000 000.

Bibliografia modifica

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 modifica

Karatsuba Multiplication on MathWorld, su mathworld.wolfram.com.
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.