Algoritmo di kartsuba
Ciao,leggendo in giro non riesco a capire la logica di tale algoritmo...Capisco che usa divid et impera,ma mica tanto la logica e ho già letto su wikipedia ecc...Mi potete spiegare semplicemente ad alto livello il funzionamento?
Risposte
Che cosa non capisci esattamente?
Siccome dovresti aver già visto la descrizione, provo a farti un esempio. Supponi di saper calcolare direttamente il prodotto tra due cifre decimali, e di voler calcolare per esempio il prodotto tra \(1234\) e \(327\). Per prima cosa riscrivi i numeri nella forma \(1234 = 12 \times 10^2 + 34 \) e \( 327 = 3 \times 10^2 + 27. \) A questo punto sai che il tuo prodotto sarà nella forma \( a \times 10^4 + b \times 10^2 + c \) dove \( a = 12 \times 3, \) \( c = 34 \times 27 ,\) \(b = (12 + 34) \times (3 + 27) - a - c. \) Iniziamo quindi a calcolare \(a\) riscrivendo i due numeri del prodotto come in precedenza: \( 12 = 1 \times 10 + 2 \) e \( 3 = 0 \times 10 + 3. \) Per ottenere il risultato calcoliamo quindi per prima cosa \( 1 \times 0 = 0 \) e \( 2 \times 3 = 6 \) per ottenere i due numeri da usare nel terzo coefficiente della somma \( (1 + 2) \times (0 + 3) - 0 - 6 = 3. \) Abbiamo quindi ottenuto \( a = 0 \times 10^2 + 3 \times 10 + 6 = 36. \) Stesso discorso per \(c\) dove otteniamo \( 3 \times 2 = 6, \) \( 4 \times 7 = 28 \) e \( (3 + 4)\times(2 + 7) - 6 - 28 = 29. \) Abbiamo quindi che \( c = 6 \times 10^2 + 29 \times 10 + 28 = 918\) A questo punto, per calcolare \(c\) è necessario calcolare il prodotto \( 46 \times 30 \) applicando l'algoritmo ricorsivamente due volte ottenendo \( b = 426. \) Il risultato si calcola a questo punto come
\[ 36 \times 10^4 + 426 \times 10^2 + 918 = 403518 = 1234 \times 327. \]
Fammi sapere se ancora non capisci qualcosa..
Siccome dovresti aver già visto la descrizione, provo a farti un esempio. Supponi di saper calcolare direttamente il prodotto tra due cifre decimali, e di voler calcolare per esempio il prodotto tra \(1234\) e \(327\). Per prima cosa riscrivi i numeri nella forma \(1234 = 12 \times 10^2 + 34 \) e \( 327 = 3 \times 10^2 + 27. \) A questo punto sai che il tuo prodotto sarà nella forma \( a \times 10^4 + b \times 10^2 + c \) dove \( a = 12 \times 3, \) \( c = 34 \times 27 ,\) \(b = (12 + 34) \times (3 + 27) - a - c. \) Iniziamo quindi a calcolare \(a\) riscrivendo i due numeri del prodotto come in precedenza: \( 12 = 1 \times 10 + 2 \) e \( 3 = 0 \times 10 + 3. \) Per ottenere il risultato calcoliamo quindi per prima cosa \( 1 \times 0 = 0 \) e \( 2 \times 3 = 6 \) per ottenere i due numeri da usare nel terzo coefficiente della somma \( (1 + 2) \times (0 + 3) - 0 - 6 = 3. \) Abbiamo quindi ottenuto \( a = 0 \times 10^2 + 3 \times 10 + 6 = 36. \) Stesso discorso per \(c\) dove otteniamo \( 3 \times 2 = 6, \) \( 4 \times 7 = 28 \) e \( (3 + 4)\times(2 + 7) - 6 - 28 = 29. \) Abbiamo quindi che \( c = 6 \times 10^2 + 29 \times 10 + 28 = 918\) A questo punto, per calcolare \(c\) è necessario calcolare il prodotto \( 46 \times 30 \) applicando l'algoritmo ricorsivamente due volte ottenendo \( b = 426. \) Il risultato si calcola a questo punto come
\[ 36 \times 10^4 + 426 \times 10^2 + 918 = 403518 = 1234 \times 327. \]
Fammi sapere se ancora non capisci qualcosa..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo