Mondo Java: Algoritmo della settimana: Moltiplicazione Karatsuba veloce

Introduzione

Tipicamente moltiplicando due numeri di n cifre richiedono moltiplicazioni n2. Che in realtà è come noi, esseri umani, moltiplicare i numeri. Diamo uno sguardo di un esempio nel caso in cui abbiamo a moltiplicare due numeri a 2 cifre.

1.= 12 x 15?

OK, sappiamo che la risposta è 180 e ci sono molti metodi intuitivi che ci aiutano a ottenere la risposta giusta. Infatti 12 x 15 è solo un po 'più difficile da calcolare a 10 x 15, perché moltiplicando per 10' davvero facile - basta aggiungere uno 0 alla fine del numero. Così 15 x 10 è uguale a 150. Ma ora di nuovo il 12 x 15 - sappiamo che questo è uguale a 10 x 15 (che è 150) e 2 x 15, che è anche molto facile da calcolare ed è 30. Il risultato di 12 × 15 sarà di 150 + 30, che per fortuna non è difficile da ottenere e pari a 180.

E 'stato facile, ma in alcuni casi i calcoli sono un po' più difficile e abbiamo bisogno di un algoritmo strutturato per ottenere la risposta giusta. Che cosa circa 65 x 97? Non è così facile come 12 x 15, giusto?

L'algoritmo che conosciamo dalla scuola primaria, descritta nello schema qui sotto, è ben strutturato e ci aiutano a moltiplicare due numeri.

Vediamo che anche per i numeri a due cifre è molto difficile - ci sono 4 moltiplicazioni e alcune aggiunte.

Abbiamo bisogno di 4 moltiplicazioni per calcolare il prodotto di due numeri a 2 cifre!

Tuttavia fino ad ora sappiamo come moltiplicare i numeri, l'unico problema è che il nostro compito diventa molto difficile in quanto i numeri crescono. Se moltiplicando 65 del 97 fosse in qualche modo facile, per quanto riguarda

374.773.294.776.321

x

222.384.759.707.982

Sembra quasi impossibile.

Storia

Andrey Kolmogorov è uno dei più brillanti matematici russi del 20 ° secolo. Nel 1960, durante un seminario, Kolmogorov ha dichiarato che due n-cifre non possono essere moltiplicate con meno di moltiplicazioni n2!
Solo una settimana più tardi di 23 anni giovane studente chiamato Anatolii Alexeevitch Karatsubadimostrato che la moltiplicazione di due numeri di n cifre possono essere calcolati con n * lg (3) moltiplicazioni con un ingegnoso divide et impera approccio.

Panoramica

Fondamentalmente Karatsuba dichiarato che se abbiamo moltiplicare due cifre n-x ed y, questo può essere fatto con le seguenti operazioni, supponendo che B è la base e di m <n.

Prima sia x numeri e y può essere rappresentato come x1, x2 e y1, y2 con la seguente formulavisualizzare il cod

x = x1 * B ^ m + x2

y = y1 * B ^ m + y2

Ovviamente ora xy diventerà come il seguente prodotto.

xy = (x1 * B ^ m + x2) (y1 * B ^ m + y2) = & gt ;

 

a = x1 * y1

b = x1 * y2 + x2 * y1

c = x2 * y2

Infine xy diventerà:

1.xy = a * B ^ 2m + b * B ^ m + c

Tuttavia a, b, c possono essere calcolati con almeno quattro moltiplicazione, che non è un grande ottimizzazione. Questo è il motivo Karatsuba si avvicinò con la brillante idea di calcolare b con la seguente formula:

1.b = (x1 + x2) (y1 + y2) - a - c

Che fanno uso di soli tre moltiplicazioni per ottenere xy.

Vediamo questa formula con l'esempio.

47 x 78

 

x = 47

x = 4 * 10 + 7

 

x1 = 4

x2 = 7

 

y = 78

y = 7 * 10 + 8

 

y1 = 7

y2 = 8

 

a = x1 * y1 = 4 * 7 = 28

c = x2 * y2 = 7 * 8 = 56

b = (x1 + x2) (y1 + y2) - a - b = 11 * 15 - 28-56

Ora il fatto è che 11 * 15 è di nuovo una moltiplicazione tra i numeri a 2 cifre, ma per fortuna possiamo applicare le stesse regole due di loro. Questo rende l'algoritmo di Karatsuba un perfetto esempio l'algoritmo "divide et impera".

Implementazione

Moltiplicazione standard

In genere l'implementazione standard di moltiplicazione di n-cifre richiedono moltiplicazioni n2 come si può vedere dalla seguente PHP attuazione.

$ x = array (1,2,3,4);

$ y = array (5,6,7,8);

 

funzione multiply ($ x, $ y)

{  

$ len_x = count ($ x);

$ len_y = count ($ y);

$ half_x = ceil ($ len_x / 2);

$ half_y = ceil ($ len_y / 2);

$ base = 10;

 

/ / inferiore della ricorsione

se ($ len_x == 1 && $ len_y == 1) {

tornare $ x [0] * $ y [0];

}

 

dollari x_chunks = array_chunk ($ x, $ half_x);

dollari y_chunks = array_chunk ($ y, $ half_y);

 

/ / predefiniscono aliases

$ x1 = $ x_chunks [0];

$ x2 = $ x_chunks [1];

$ y1 = $ y_chunks [0];

$ y2 = $ y_chunks [1];

 

di ritorno   si moltiplicano ($ x1, $ y1) * pow ($ base, $ half_x * 2) / / a

+ (multiply ($ x1, $ y2) si moltiplicano + ($ x2, $ y1)) * pow ($ base, $ half_x) / / b

si moltiplicano + ($ x2, $ y2); / / c

}

 

/ / 7 006 652

echo multiply ($ x, $ y);

Karatsuba Moltiplicazione

Karatsuba sostituisce due delle moltiplicazioni - questa di x1 * y2 + x2 * y1 con un solo - (x1 + x2) (y1 + y2) e questo rende più veloce l'algoritmo.

$ x = array (1,2,3,4);

$ y = array (5,6,7,8);

 

funzione karatsuba ($ x, $ y)

{

$ len_x = count ($ x);

$ len_y = count ($ y);

 

/ / inferiore della ricorsione

se ($ len_x == 1 && $ len_y == 1) {

tornare $ x [0] * $ y [0];

}

se ($ len_x == 1 | | $ len_y == 1) {

$ t1 = implode ('', $ x);

$ t2 = implode ('', $ y);

return (int) $ t1 * $ t2;

}

 

$ a = array_chunk ($ x, ceil ($ len_x / 2));

$ b = array_chunk ($ y, ceil ($ len_y / 2));

 

° piano = $ ($ len_x / 2);

 

$ x1 = $ a [0]; / / 1

$ x2 = $ a [1]; / / 2

$ y1 = $ b [0]; / / 1

$ y2 = $ b [1]; / / 2

 

return   ($ a = karatsuba ($ x1, $ y1)) * pow (10, 2 * $ deg)

+ ($ c = karatsuba ($ x2, y2 $))

+ (karatsuba ( somma ($ x1, $ x2), sum ($ y1, $ y2)) - $ a - $ c) * pow (10, $ deg);

}

 

/ / 7 006 652

echo karatsuba ($ x, $ y);

Complessità

Supponendo che sostituire due delle moltiplicazioni con un solo rende il programma più veloce. La domanda è quanto velocemente. Karatsuba migliora il processo di moltiplicazione sostituendo la complessità iniziale di O (n2) di O (nlg3), che come potete vedere nello schema qui sotto è molto più veloce per grandi n.

O (n ^ 2) cresce molto più velocemente di O (n ^ LG3)

Applicazione

È ovvio in cui l'algoritmo Karatsuba può essere utilizzato. È molto efficace quando si tratta di moltiplicazione intera, ma che non è il suo unico vantaggio. E 'spesso usato per moltiplicazioni polinomiali.

Corso Java - Corsi Java - Corsi programmazione Java

Corso programmazione Android - Certificazione Android

Mondo Java

mercoledì 16 maggio 2012

Algoritmo della settimana: Moltiplicazione Karatsuba veloce