Vai al contenuto principale

Informatica · Algoritmi

Karatsuba ibrido con caso base quadratico su 64 cifre

Una variante pratica di Karatsuba funziona così: se $n \le 4$ usa il metodo scolastico, che costa $n^{2}$ moltiplicazioni elementari; se n > 4 (con n potenza di 2) esegue 3 chiamate ricorsive su numeri di $\frac{n}{2}$ cifre. Quante moltiplicazioni elementari esegue in totale su due numeri di 64 cifre?

La tua risposta

Vanno bene sia 3,14 sia 3.14.